Talks and Poster Presentations (with Proceedings-Entry):
S. Sastry, L. Welch, J. Widder:
"Wait-Free Stabilizing Dining Using Regular Registers";
Talk: International Conference On Principles Of Distributed Systems (OPODIS),
Rom;
2012-12-17
- 2012-12-20; in: "OPODIS",
LNCS / Springer,
7702
(2012),
ISBN: 978-3-642-35475-5;
284
- 299.
English abstract:
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-642-35476-2_20
Created from the Publication Database of the Vienna University of Technology.