Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks

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.