Self-stabilizing Space Optimal Synchronization Algorithms on Trees

  • Doina Bein
  • Ajoy K. Datta
  • Lawrence L. Larmore
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


We present a space and (asymptotically) time optimal self-stabilizing algorithm for simultaneously activating non-adjacent processes in a rooted tree (Algorithm \(\mathcal{SSDST}\)). We then give two applications of the proposed algorithm: a time and space optimal solution to the local mutual exclusion problem (Algorithm \(\mathcal{LMET}\)) and a space and (asymptotically) time optimal distributed algorithm to place the values in min-heap order (Algorithm \({\mathcal{HEAP}}\)). All algorithms are self-stabilizing and uniform, and they work under any unfair distributed daemon. In proving the time complexity of the heap construction, we use the notion of pseudo-time. Pseudo-time is similar to logical time introduced by Lamport [12].


heap local mutual exclusion self-stabilization 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Alima, L.: Self-stabilizing max-heap. In: Proceedings of the ICDCS Workshop on Self-stabilizing Systems, pp. 94–101 (1999)Google Scholar
  2. 2.
    Alima, L., Beauquier, J., Datta, A., Tixeuil, S.: Self-stabilization with global rooted synchronizers. In: Proceedings of the 18-th ICDCS, pp. 102–109 (1998)Google Scholar
  3. 3.
    Arora, A., Nesterenko, M.: Stabilization-preserving atomicity refinement. Journal of Parallel and Distributed Computing 62, 766–791 (2002)zbMATHCrossRefGoogle Scholar
  4. 4.
    Bein, D., Datta, A., Villain, V.: Snap-stabilizing optimal binary-search-tree. In: Proceedings of the 7th International Symposium on Self-Stabilizing Systems (2005)Google Scholar
  5. 5.
    Bourgon, B., Datta, A.: A self-stabilizing distributed heap maintenance protocol. In: Proceedings of the Second Workshop on Self-stabilizing Systems (1995)Google Scholar
  6. 6.
    Bui, A., Datta, A., Petit, F., Villain, V.: State-optimal snap-stabilizing PIF in tree networks. In: Proceedings of the Third Workshop on Self-Stabilizing Systems, pp. 78–85. IEEE Computer Society Press, Los Alamitos (1999)Google Scholar
  7. 7.
    Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)zbMATHGoogle Scholar
  8. 8.
    Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17, 643–644 (1974)zbMATHGoogle Scholar
  9. 9.
    Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel and Distributed Systems 8(4), 424–440 (1997)CrossRefGoogle Scholar
  10. 10.
    Herman, T., Masuzawa, T.: Available stabilizing heaps. Information Processing Letters 77, 115–121 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Johnen, C., Alima, L., Datta, A., Tixeuil, S.: Self-stabilizing neighborhood synchronizer in tree networks. Parallel Processing Letters 12(3 & 4), 327–340 (2002)CrossRefMathSciNetGoogle Scholar
  12. 12.
    Lamport, L.: Time, clocks and the ordering of events in a distributed systems. Communications of the ACM 21, 558–565 (1978)zbMATHCrossRefGoogle Scholar
  13. 13.
    Ukena, S., Hasegawa, M., Katayama, Y., Masuzawa, T., Fujiwara, H.: A self-stabilizing max-heap protocol in tree networks. Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi) 86(9), 63–72 (2003)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Doina Bein
    • 1
  • Ajoy K. Datta
    • 1
  • Lawrence L. Larmore
    • 1
  1. 1.University of NevadaLas VegasUSA

Personalised recommendations