Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Partial synchrony based on set timeliness

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

We introduce a new model of partial synchrony for read-write shared memory systems. This model is based on the simple notion of set timeliness—a natural generalization of the seminal concept of timeliness in the partially synchrony model of Dwork et al. (J. ACM 35(2):288–323, 1988). Despite its simplicity, the concept of set timeliness is powerful enough to define a family of partially synchronous systems that closely match individual instances of the t-resilient k-set agreement problem among n processes, henceforth denoted (t, k, n)-agreement. In particular, we use it to give a partially synchronous system that is synchronous enough for solving (t, k, n)-agreement, but not enough for solving two incrementally stronger problems, namely, (t + 1, k, n)-agreement, which has a slightly stronger resiliency requirement, and (t, k − 1, n)-agreement, which has a slightly stronger agreement requirement. This is the first partially synchronous system that separates these sub-consensus problems. The above results show that set timeliness can be used to study and compare the partial synchrony requirements of problems that are strictly weaker than consensus.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Communication-efficient leader election and consensus with limited link synchrony. In: ACM Symposium on Principles of Distributed Computing, pp. 328–337, July 2004

  2. Aguilera M.K., Delporte-Gallet C., Fauconnier H., Toueg S.: On implementing Omega in systems with weak reliability and synchrony assumptions. Distrib. Comput. 21(4), 285–314 (2008)

    Article  Google Scholar 

  3. Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Partial synchrony based on set timeliness. In: ACM Symposium on Principles of Distributed Computing, pp. 102–110, August 2009

  4. Aguilera M.K., Toueg S.: Adaptive progress: a gracefully-degrading liveness property. Distrib. Comput. 22(5–6), 303–334 (2010)

    Article  MATH  Google Scholar 

  5. Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: ACM Symposium on Theory of Computing, pp. 91–100, May 1993

  6. Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In: ACM Symposium on Principles of Distributed Computing, pp. 189–198, August 1997

  7. Borowsky E., Gafni E., Lynch N.A., Rajsbaum S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)

    Article  Google Scholar 

  8. Chandra T.D., Hadzilacos V., Toueg S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chandra T.D., Toueg S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chaudhuri S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)

    Article  MATH  Google Scholar 

  11. Cornejo, A., Rajsbaum, S., Raynal, M., Travers, C.: Brief announcement: failure detectors are schedulers. In: ACM Symposium on Principles of Distributed Computing, pp. 308–309, August 2007

  12. Dwork C., Lynch N.A., Stockmeyer L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)

    Article  MathSciNet  Google Scholar 

  13. Fernández A., Raynal M.: From an asynchronous intermittent rotating star to an eventual leader. IEEE Trans. Parallel Distrib. Syst. 21(9), 1290–1303 (2010)

    Article  Google Scholar 

  14. Gafni E., Kuznetsov P.: On set consensus numbers. Distrib. Comput. 24(3–4), 149–163 (2011)

    Article  MATH  Google Scholar 

  15. Herlihy M., Shavit N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hutle M., Malkhi D., Schmid U., Zhou L.: Chasing the weakest system model for implementing Ω and consensus. IEEE Trans. Dependable Secur. Comput. 6(4), 269–281 (2009)

    Article  Google Scholar 

  17. Jiménez E., Arévalo S., Fernández A.: Implementing unreliable failure detectors with unknown membership. Inf. Process. Lett. 100(2), 60–63 (2006)

    Article  MATH  Google Scholar 

  18. Malkhi, D., Oprea, F., Zhou, L.: Omega meets Paxos: leader election and stability without eventual timely links. In: International Conference on Distributed Computing. LNCS, vol. 3724, pp. 199–213. Springer, September 2005

  19. Mostéfaoui, A., Raynal, M.: k-set agreement with limited accuracy failure detectors. In: ACM Symposium on Principles of Distributed Computing, pp. 143–152, July 2000

  20. Mostefaoui A., Raynal M., Travers C.: Time-free and timer-based assumptions can be combined to obtain eventual leadership. IEEE Trans. Parallel Distrib. Syst. 17(7), 656–666 (2006)

    Article  Google Scholar 

  21. Neiger, G.: Failure detectors and the wait-free hierarchy. In: ACM Symposium on Principles of Distributed Computing, pp. 100–109, August 1995

  22. Pike, S.M., Sastry, S., Welch, J.L.: Failure detectors encapsulate fairness. In: International Conference on Principles of Distributed Systems. LNCS, vol. 6490, pp. 173–188. Springer, December 2010

  23. Rajsbaum, S., Raynal, M., Travers, C.: Failure detectors as schedulers (an algorithmically-reasoned characterization). Technical Report 1838, IRISA, Université de Rennes, France, March 2007

  24. Rajsbaum S., Raynal M., Travers C.: The iterated restricted immediate snapshot model. In: International Computing and Combinatorics Conference. LNCS, vol. 5092, pp. 487–497. Springer, June 2008

  25. Saks M.E., Zaharoglou F.: Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  26. Zielinski P.: Anti-Ω: the weakest failure detector for set agreement. Distrib. Comput. 22(5–6), 335–348 (2010)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Microsoft Research Silicon Valley, Mountain View, CA, USA

    Marcos K. Aguilera

  2. Université Paris-Diderot, Paris, France

    Carole Delporte-Gallet & Hugues Fauconnier

  3. University of Toronto, Toronto, ON, Canada

    Sam Toueg

Authors
  1. Marcos K. Aguilera
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carole Delporte-Gallet
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hugues Fauconnier
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sam Toueg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marcos K. Aguilera.

Additional information

A preliminary version of this paper appeared in [3].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H. et al. Partial synchrony based on set timeliness. Distrib. Comput. 25, 249–260 (2012). https://doi.org/10.1007/s00446-012-0158-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-012-0158-8

Keywords

Search

Navigation