Solving Agreement Problems with Weak Ordering Oracles | SpringerLink
Skip to main content
Springer Nature Link
Log in

Solving Agreement Problems with Weak Ordering Oracles

  • Conference paper
  • First Online:
Dependable Computing EDCC-4 (EDCC 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2485))

Included in the following conference series:

Abstract

Agreement problems, such as consensus, atomic broadcast, and group membership, are central to the implementation of fault-tolerant distributed systems. Despite the diversity of algorithms that have been proposed for solving agreement problems in the past years, almost all solutions are Crash-Detection Based (CDB). We say that an algorithm is CDB if it uses some information about the status crashed/not crashed of processes. In this paper, we revisit the issue of non-CDB algorithms considering ordering oracles. Ordering oracles have a theoretical interest as well as a practical interest. To illustrate their use, we present solutions to consensus and atomic broadcast, and evaluate the performance of the atomic broadcast algorithm in a cluster of workstations.

Research partially supported by the CSEM - Swiss Center for Electronics and Microtechnology Inc., Neuchâtel, and the Swiss National Science Foundation NCCR MICS project.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. M. K. Aguilera, W. Chen, and S. Toueg. Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks. Theoretical Computer Science, 220(1):3–30, June 1999.

    Google Scholar 

  2. M. K. Aguilera, C. Delporte-Gallet, H. Fauconnier, and S. Toueg. Thrifty generic broadcast. In Proceedings of the 14th International Symposium on Distributed Computing (DISC’2000), October 2000.

    Google Scholar 

  3. E. Anceaume. A Lightweight Solution to Uniform Atomic Broadcast for Asynchronous Systems. In IEEE 27th Int Symp on Fault-Tolerant Computing (FTCS-27), pages 292–301, June 1997.

    Google Scholar 

  4. H. Attiya and J. Welch. Distributed Computing. McGraw Hill, 1998.

    Google Scholar 

  5. M. Ben-Or. Another advantage of free choice: completely asynchronous agreement protocols. In proc. 2nd annual ACM Symposium on Principles of Distributed Computing, pages 27–30, 1983.

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  7. F. Cristian and C. Fetzer. The timed asynchronous distributed system model. IEEE Transactions on Parallel & Distributed Systems, 10(6):642–657, June 1999.

    Google Scholar 

  8. D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchrony needed for distributed consensus. Journal of ACM, 34(1):77–97, January 1987.

    Google Scholar 

  9. C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of ACM, 35(2):288–323, April 1988.

    Google Scholar 

  10. M. Fischer, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of ACM, 32:374–382, April 1985.

    Google Scholar 

  11. R. Guerraoui and A. Schiper. Consensus: the Big Misunderstanding. In IEEE Proc of the Sixth Workshop on Future Trends of Distributed Computing Systems, pages 183–188, October 1997.

    Google Scholar 

  12. V. Hadzilacos and S. Toueg. Fault-Tolerant Broadcasts and Related Problems. Technical Report 94-1425, Department of Computer Science, Cornell University, May 1994.

    Google Scholar 

  13. N. A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.

    Google Scholar 

  14. A. Mostefaoui and M. Raynal. Solving Consensus using Chandra-Toueg’s Unreliable Failure Detectors: A Synthetic Approach. In 13th. Intl. Symposium on Distributed Computing (DISC’99). Springer Verlag, LNCS 1693, September 1999.

    Google Scholar 

  15. A. Mostefaoui and M. Raynal. Leader-based consensus. Parallel Processing Letters, 11:95–107, 2001.

    Article  MathSciNet  Google Scholar 

  16. F. Pedone and A. Schiper. Generic Broadcast. In 13th. Intl. Symposium on Distributed Computing (DISC’99), pages 94–108. Springer Verlag, LNCS 1693, September 1999.

    Google Scholar 

  17. F. Pedone, A. Schiper, P. Urban, and D. Cavin. Solving Agreement Problems with Weak Ordering Oracles. TR IC/2002/010, EPFL, March 2002. Appears also as Technical Report HPL-2002-44, Hewlett-Packard Laboratories, March 2002.

    Google Scholar 

  18. M. Rabin. Randomized Byzantine Generals. In Proc. 24th Annual ACM Symposium on Foundations of Computer Science, pages 403–409, 1983.

    Google Scholar 

  19. A. Schiper. Early consensus in an asynchronous system with a weak failure detector. Distributed Computing, 10(3):149–157, April 1997.

    Google Scholar 

  20. Péter Urbán, Xavier Défago, and André Schiper. Neko: A single environment to simulate and prototype distributed algorithms. In Proc. of the 15th Int’l Conf. on Information Networking (ICOIN-15), Beppu City, Japan, February 2001.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Hewlett-Packard Laboratories, Software Technology Laboratory, Palo Alto, CA, 94304, USA

    Fernando Pedone

  2. Ecole Polytechnique Fédérale de Lausanne (EPFL) Faculté Informatique & Communications, CH-1015, Lausanne, Switzerland

    Fernando Pedone, André Schiper, Péter Urbán & David Cavin

Authors
  1. Fernando Pedone
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. André Schiper
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Péter Urbán
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. David Cavin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dipartimento di Sistemi e Informatica, Universitá di Firenze, Via Lombroso 6/17, 50134, Firenze, Italy

    Andrea Bondavalli

  2. LAAS-CNRS, 7 Avenue du Colonel Roche, Toulouse Cedex 4, France

    Pascale Thevenod-Fosse

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Pedone, F., Schiper, A., Urbán, P., Cavin, D. (2002). Solving Agreement Problems with Weak Ordering Oracles. In: Bondavalli, A., Thevenod-Fosse, P. (eds) Dependable Computing EDCC-4. EDCC 2002. Lecture Notes in Computer Science, vol 2485. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36080-8_5

Download citation

  • DOI: https://doi.org/10.1007/3-540-36080-8_5

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00012-9

  • Online ISBN: 978-3-540-36080-3

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation