Wait-Free Stabilizing Dining Using Regular Registers Conference Paper uri icon


  • 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 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 P is necessary for wait-freedom. 2012 Springer-Verlag.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Sastry, S., Welch, J. L., & Widder, J.

citation count

  • 1

complete list of authors

  • Sastry, Srikanth||Welch, Jennifer L||Widder, Josef

publication date

  • December 2012