M.Sc Thesis | |

M.Sc Student | Kogan Alex |
---|---|

Subject | Efficient and Robust Local Mutual Exclusion in Mobile Ad- Hoc Networks |

Department | Department of Computer Science |

Supervisor | PROF. 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 .