The Driving Philosophers

We introduce a new synchronization problem in mobile ad-hoc systems: the Driving Philosophers. In this problem, an unbounded number of driving philosophers (processes) access a round-about (set of shared resources organized along a logical ring). The crux of the problem is to ensure, beside traditional mutual exclusion and starvation freedom at each particular resource, gridlock freedom (i.e., cyclic waiting chain amongst processes). The problem captures explicitly the very notion of process mobility and the underlying model does not involve any assumption on the total number of (participating) processes or the use of shared memory, i.e., the model conveys the ad-hoc environment. We present a generic algorithm that solves the problem in a synchronous model. Instances of this algorithm can be fair but not concurrent, or concurrent but not fair. We derive the impossibility of achieving fairness and concurrency at the same time as well as the impossibility of solving the problem in an asynchronous model. We also conjecture the impossibility of solving the problem in an ad-hoc network model with limited-range communication.


Published in:
Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science
Year:
2004
Keywords:
Laboratories:




 Record created 2006-01-25, last modified 2018-01-27

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)