Adapting to Point Contention with Long-Lived Safe Agreement

  • Hagit Attiya
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


Algorithms with step complexity that depends only on the point contention—the number of simultaneously active processes—are very attractive for distributed systems with varying degree of concurrency. Designing shared-memory algorithms that adapt to point contention, using only read and write operations, is however, a challenging task.

The paper specifies the long-lived safe agreement object, extending an object of Borowsky et al. [1], and describes an implementation whose step complexity is adaptive to point contention. Then, we illustrate how this object is used to solve other problems, like renaming and information collection, in an adaptive manner.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distributed Computing 14(3), 127–146 (2001)CrossRefGoogle Scholar
  2. 2.
    Attiya, H., Zach, I.: Fully adaptive algorithms for atomic and immediate snapshots. (2003)
  3. 3.
    Attiya, H., Fouren, A.: Algorithms adaptive to point contention. Journal of the ACM 50(4), 444–468 (2003)CrossRefMathSciNetGoogle Scholar
  4. 4.
    Afek, Y., Attiya, H., Fouren, A., Stupp, G., Touitou, D.: Adaptive long-lived renaming using bounded memory (1999),
  5. 5.
    Inoue, M., Umetani, S., Masuzawa, T., Fujiwara, H.: Adaptive long-lived O(k 2)-renaming with O(k 2) steps. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 123–135. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  6. 6.
    Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. Journal of the ACM 37(3), 524–548 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Moir, M., Anderson, J.H.: Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming 25(1), 1–39 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Afek, Y., Stupp, G., Touitou, D.: Long-lived and adaptive collect with applications. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, Phoenix, pp. 262–272. IEEE Computer Society Press, Los Alamitos (1999)Google Scholar
  9. 9.
    Afek, Y., Stupp, G., Touitou, D.: Long-lived and adaptive atomic snapshot and immediate snapshot. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 71–80. ACM Press, New York (2000)Google Scholar
  10. 10.
    Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems 13(1), 124–149 (1991)CrossRefGoogle Scholar
  11. 11.
    Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. Journal of the ACM 40(4), 873–890 (1993)zbMATHCrossRefGoogle Scholar
  12. 12.
    Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM Journal on Computing 31(2), 642–664 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Stupp, G.: Long Lived and Adaptive Shared Memory Implementations. PhD thesis, Department of Computer Science, Tel-Aviv University (2001)Google Scholar
  14. 14.
    Afek, Y., Boxer, P., Touitou, D.: Bounds on the shared memory requirements for long-lived adaptive objects. In: Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, pp. 81–89. ACM Press, New York (2000)Google Scholar
  15. 15.
    Attiya, H., Fich, F., Kaplan, Y.: Lower bounds for adaptive collect and related problems. In: Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, pp. 60–69 (2004)Google Scholar
  16. 16.
    Afek, Y., Dauber, D., Touitou, D.: Wait-free made fast. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 538–547. ACM Press, New York (1995)Google Scholar
  17. 17.
    Herlihy, M., Luchangco, V., Moir, M.: Space- and time-adaptive non-blocking algorithms. In: Electronic Notes in Theoretical Computer Science, vol. 78, Elsevier, Amsterdam (2003)Google Scholar
  18. 18.
    Afek, Y., Stupp, G., Touitou, D.: Long-lived adaptive splitter and applications. Distributed Computing 15(2), 67–86 (2002)CrossRefGoogle Scholar
  19. 19.
    Attiya, H., Fouren, A., Gafni, E.: An adaptive collect algorithm with applications. Distributed Computing 15(2), 87–96 (2002)CrossRefGoogle Scholar
  20. 20.
    Anderson, J., Kim, Y.J.: Adaptive mutual exclusion with local spinning. In: Proceedings of the 14th International Conference on Distributed Computing (2000)Google Scholar
  21. 21.
    Attiya, H., Bortnikov, V.: Adaptive and efficient mutual exclusion. Distributed Computing 15(3), 177–189 (2002)CrossRefGoogle Scholar
  22. 22.
    Choy, M., Singh, A.K.: Adaptive solutions to the mutual exclusion problem. Distributed Computing 8(1), 1–17 (1994)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Hagit Attiya
    • 1
  1. 1.Department of Computer ScienceTechnion 

Personalised recommendations