M.Sc Thesis

M.Sc StudentKogan Alex
SubjectEfficient and Robust Local Mutual Exclusion in Mobile Ad-
Hoc Networks
DepartmentDepartment of Computer Science
Supervisor PROF. Hagit Attiya
Full Thesis textFull thesis text - English Version


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 .