|M.Sc Student||Kogan Alex|
|Subject||Efficient and Robust Local Mutual Exclusion in Mobile Ad-|
|Department||Department of Computer Science||Supervisor||Professor Hagit Attiya|
|Full Thesis text|
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 .