Published in Volume XVIII, 2008, pages 13-34

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

Abstract

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)

References

[1] EW Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the ACM, 17:643-644, 1974.

[2] S Dolev, A Israeli, and S Moran. Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel & Distributed Systems, 8(4):424-440, 1997.

[3] P Flocchini, E Kranakis, D Krizanc, F Luccio, and N Santoro. Sorting and election in anonymous asynchronous rings. Journal of Parallel & Distributed Computing, 64:254-265, 2004.

[4] A Sasaki. A time-optimal distributed sorting algorithm on a line network. Information Processing Letters, 83:21-26, 2002.

[5] A Sasaki. A time- and communication-optimal distributed sorting algorithm in a line network and its extension to the dynamic sorting problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, pages 444-453, 2004.

[6] C Boulinier, F Petit, and V Villain. When graph theory helps selfstabilization. ACM Symposium on Principles of Distributed Computing, pages 150-159, 2004.

[7] D Bein, AK Datta, and LL Larmore. Self-stabilizing space optimal synchronization algorithms on trees. In Colloquium on Structural Information and Communication Complexity, LNCS 4056, pages 334-348, 2006.

[8] A Bui, AK Datta, F Petit, and V Villain. State-optimal snap-stabilizing PIF in tree networks. In Workshop on Self-Stabilizing Systems, pages 78-85, 1999.

[9] A Cournier, AK Datta, F Petit, and V Villain. Enabling snapstabilization. In International Conference on Distributed Computing Systems, pages 78-85, 2003.

[10] C Johnen, LO Alima, AK Datta, and S Tixeuil. Self-stabilizing neighborhood synchronizer in tree networks. International Conference on Distributed Computing Systems (ICDCS), pages 487-494, 1999.

[11] A Arora and M Nesterenko. Stabilization-preserving atomicity refinement. Journal of Parallel & Distributed Computing, 62:766-791, 2002.

[12] S Dolev, A Israeli, and S Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7:3-16, 1993.

Bibtex

@article{sacscuza:bein2008saooc,
  title={Synchronization Algorithms on Oriented Chains},
  author={D. Bein and A.K. Datta and L.L. Larmore},
  journal={Scientific Annals of Computer Science},
  volume={18},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2008},
  pages={13--34},
  publisher={``A.I. Cuza'' University Press}
}