Technical Report MSC-2008-14

Title: Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks
Authors: Alex Kogan
Supervisors: Hagit Attiya
Abstract: In a mobile ad hoc network, nodes that are geographically close may need to compete for exclusive access to a shared resource. This thesis studies an abstraction of this problem, called local mutual exclusion, an extension of the dining philosophers problem, well-studied in static networks, to mobile networks. A desirable feature of an algorithm for this problem is to limit the negative effect of a crashed node to a small neighborhood around the crash; the size of this neighborhood is called the failure locality. Another requirement from such algorithm is having the response time independent of the total number of nodes, thus providing a scalable solution.

The thesis presents two algorithms, exhibiting different tradeoffs 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 other variation has worse performance, but simpler implementation. 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2008
To the main CS technical reports page

Computer science department, Technion