Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks Academic Article

abstract

• In a mobile ad hoc network, nodes that are geographically close may need to compete for exclusive access to a shared resource. This paper proposes an abstraction of this problem, called local mutual exclusion; it is an extension to mobile networks of the dining philosophers problem, which has been well studied in static networks. The desirable feature of an algorithm for this problem is having response time and failure locality independent of the total number of nodes, thus providing a scalable and robust solution. The paper presents two algorithms, exhibiting trade-offs between simplicity, failure locality and response time. The first algorithm has two variations, one of which has response time that depends very weakly on the number of nodes in the entire system and is polynomial in the maximum number of neighboring nodes; the failure locality, although not optimal, is small and grows very slowly with system size. The second algorithm has optimal failure locality and response time that is quadratic in the number of nodes. A pleasing aspect of the latter algorithm is that when nodes do not move, it has linear response time, improving on previous results for static algorithms with optimal failure locality. 2010 IEEE.

authors

• Welch, Jennifer

published proceedings

• IEEE TRANSACTIONS ON MOBILE COMPUTING

author list (cited authors)

• Attiya, H., Kogan, A., & Welch, J. L.

citation count

• 21

complete list of authors

• Attiya, Hagit||Kogan, Alex||Welch, Jennifer L

publication date

• March 2010

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE Transactions on Mobile Computing  Journal

keywords

• Dining Philosophers
• Failure Locality
• Mobile Ad Hoc Networks

Digital Object Identifier (DOI)

• 10.1109/TMC.2009.137

start page

• 361

end page

• 375

volume

• 9

issue

• 3

URL

• http%3A%2F%2Fdx.doi.org%2F10.1109%2Ftmc.2009.137