Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks Conference Paper uri icon


  • This paper presents two algorithms for the local mutual exclusion problem, an extension of the dining philosophers problem for mobile ad hoc networks. A solution to this problem allows nodes that are currently geographically close to obtain exclusive access to a resource. The algorithms exhibit different tradeoffs between response time and failure locality (the size of the neighborhood adversely affected by a node crash). 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 this algorithm is that, when run in a system with no node movement, it has linear response time, improving on previous results for static algorithms with optimal failure locality. 2008 IEEE.

name of conference

  • 2008 28th IEEE International Conference on Distributed Computing Systems (ICDCS)

published proceedings

  • 2008 The 28th International Conference on Distributed Computing Systems

author list (cited authors)

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

citation count

  • 2

complete list of authors

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

publication date

  • June 2008