[Zurück]

S. Sastry, L. Welch, J. Widder:
"Wait-Free Stabilizing Dining Using Regular Registers";
Vortrag: International Conference On Principles Of Distributed Systems (OPODIS), Rom; 17.12.2012 - 20.12.2012; in: "OPODIS", LNCS / Springer, 7702 (2012), ISBN: 978-3-642-35475-5; S. 284 - 299.

Dining philosophers is a scheduling paradigm that determines when processes in a distributed system should execute certain sections of their code so that processes do not execute `conflicting´ code sections concurrently, for some application-dependent notion of a `conflict´. Designing a stabilizing dining algorithm for shared-memory systems subject to process crashes presents an interesting challenge: classic stabilization relies on all processes continuing to execute actions forever, an assumption which is violated when crash failures are considered. We present a dining algorithm that is both wait-free (tolerates any number of crashes) and is pseudo-stabilizing. Our algorithm works in an asynchronous system in which processes communicate via shared regular registers and have access to the eventually perfect failure detector $\diamondsuit \mathcal{P}$ . Furthermore, with a stronger failure detector, the solution becomes wait-free and self-stabilizing. To our knowledge, this is the first such algorithm. Prior results show that $\diamondsuit \mathcal{P}$ is necessary for wait-freedom.

http://dx.doi.org/10.1007/978-3-642-35476-2_20