Published in Volume XVIII, 2008, pages 13-34

Authors: D. Bein, A.K. Datta and L.L. Larmore


We present a space- and time-optimal self-stabilizing algorithm, SSDS,
for a given synchronization problem on asynchronous oriented chains.
SSDS is uniform and works under the unfair distributed daemon.
From SSDS we derive solutions for the local mutual
exclusion and distributed sorting.
Algorithm SSDS can also be used to obtain optimal space solutions
for other problems such as broadcasting, leader election, and
mutual exclusion.

Full Text (PDF)


  title={Synchronization Algorithms on Oriented Chains},
  author={D. Bein and A.K. Datta and L.L. Larmore},
  journal={Scientific Annals of Computer Science},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  publisher={``A.I. Cuza'' University Press}