skip to main content
10.1145/1146381.1146406acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Irreducibility and additivity of set agreement-oriented failure detector classes

Published: 23 July 2006 Publication History

Abstract

Solving agreement problems (such as consensus and k-set agreement) in asynchronous distributed systems prone to process failures has been shown to be impossible. To circumvent this impossibility, distributed oracles (also called unreliable failure detectors) have been introduced. A failure detector provides information on failures, and a failure detector class is defined by a set of abstract properties that encapsulate (and hide) synchrony assumptions. Some failure detector classes have been shown to be the weakest to solve some agreement problems (e.g., Ω is the weakest class of failure detectors that allow solving the consensus problem in asynchronous systems where a majority of processes do not crash).This paper considers several failure detector classes and focuses on their additivity or their irreducibility. It mainly investigates two families of failure detector classes (denoted ◊ Sx and ◊ φy, 0≤ x, yn), shows that they can be "added" to provide a failure detector of the class Ωz (a generalization of Ω). It also characterizes the power of such an "addition", namely, ◊ Sx + ◊ φy ➝ Ωzx+y+z>t+1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while ◊ St allows solving 2-set agreement (and not consensus) and ◊ φ1 allows solving t-set agreement (but not (t-1)-set agreement), their "addition" allows solving consensus. More generally, the paper studies the failure detector classes ◊ Sx, ◊ φy and Ωz, and shows which reductions among these classes are possible and which are not. The paper presents also an Ωk-based k-set agreement protocol. In that sense, it can be seen as a step toward the characterization of the weakest failure detector that allows solving the k-set agreement problem.

References

[1]
Borowsky E. and Gafni E., Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations. Proc. 25th ACM Symp. on the Theory of Computing (STOC'93)ACM Press, pp. 91--100, 1993.]]
[2]
Chandra T., Hadzilacos V. and Toueg S., The Weakest Failure Detector for Solving Consensus. Journal of the ACM 43(4):685--722, 1996.]]
[3]
Chandra T. D. and Toueg S., Unreliable Failure Detectors for Reliable Distributed Systems. Journal of the ACM 43(2):225--267, 1996.]]
[4]
Chaudhuri S., More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Information and Computation, 105:132--158, 1993.]]
[5]
Chu F., Reducing Ω to ◊ ω. Information Processing Letters 76(6):293--298, 1998.]]
[6]
Delporte-Gallet C., Fauconnier H. and Guerraoui R., (Almost) All Objects are Universal in Message Passing Systems. Proc. 19th Symp. on Distributed Computing (DISC'05) Springer Verlag LNCS #3724, pp. 184--198, 2005.]]
[7]
Fischer M. J., Lynch N. and Paterson M. S., Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM 32(2):374--382, 1985.]]
[8]
Guerraoui R. and Raynal M., The Information Structure of Indulgent Consensus. IEEE Transactions on Computers. 53(4), 53(4):453--466, 2004.]]
[9]
Hadzilacos V. and Toueg S., Reliable Broadcast and Related Problems. In Distributed Systems acm Press, New-York, pp. 97--145, 1993.]]
[10]
Herlihy M. P. and Penso L. D., Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors. Distributed Computing 18(2):157--166, 2005.]]
[11]
Herlihy M. P. and Shavit N., The Topological Structure of Asynchronous Computability. Journal of the ACM 46(6):858--923, 1999.]]
[12]
Lamport L., The Part-Time Parliament. ACM Transactions On Computer Systems 16(2):133--169, 1998.]]
[13]
Mostefaoui A., Rajsbaum S. and Raynal M., Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems. Journal of the ACM, 50(6):922--954, 2003.]]
[14]
Mostefaoui A., Rajsbaum S. and Raynal M., The Combined Power of Conditions and Failure Detectors to Solve Asynchronous Set Agreement. Proc. 24th ACM Symp. on Principles of Distributed Computing (PODC'05) ACM Press, pp. 179--188, 2005.]]
[15]
Mostefaoui A., Rajsbaum S., Raynal M. and Travers C., From ◊ ω to Ω: a Simple Bounded Quiescent Reliable broadcast-based Transformation. Tech Report 1759 IRISA, University of Rennes 1 (France), 2005.]]
[16]
Mostefaoui A., Rajsbaum S., Raynal M. and Travers C., Irreducibility and Additivity of Set Agreement-oriented Failure Detector Classes. Tech Report 1758 IRISA, University of Rennes 1 (France), 2005. ftp://ftp. irisa. fr/techreports/2005/PI-1758. ps. gz.]]
[17]
Mostefaoui A. and Raynal M., Solving Consensus Using Chandra Toueg's Unreliable Failure Detectors: a General Quorum Based Approach. Proc. 13th Symp. on Distributed Computing (DISC'99) Springer Verlage LNCS #1693, pp. 49--63, 1999.]]
[18]
Mostefaoui A. and Raynal M., k-Set Agreement with Limited Accuracy Failure Detectors. Proc. 19th ACM Symp. on Principles of Distributed Computing (PODC'00) ACM Press, pp. 143--152, 2000.]]
[19]
Mostefaoui A. and Raynal M., Leader-Based Consensus. Parallel Processing Letters 11(1):95--107, 2001.]]
[20]
Neiger G., Failure Detectors and the Wait-free Hierarchy. Proc. 14th ACM Symp. on Principles of Distributed Computing (PODC'95) ACM Press, pp. 100--109, 1995.]]
[21]
Raynal M., A Short Introduction to Failure Detectors for Asynchronous Distributed Systems. ACM SIGACT News, Distributed Computing Column 36(1):53--70, 2005.]]
[22]
Saks M. and Zaharoglou F., Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge. SIAM Journal on Computing 29(5):1449--1483, 2000.]]
[23]
Schiper A., Early Consensus in an Asynchronous System with a Weak Failure Detector. Distributed Computing 10:149--157, 1997.]]
[24]
Yang J., Neiger G. and Gafni E., Structured Derivations of Consensus Algorithms for Failure Detectors. Proc. 17th ACM Symp. on Principles of Distributed Computing (PODC'98) pp. 297--308, 1998.]]

Cited By

View all
  • (2010)Iterated shared memory modelsProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_36(407-416)Online publication date: 19-Apr-2010
  • (2008)Sharing is harder than agreeingProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400764(85-94)Online publication date: 18-Aug-2008
  • (2008)On the computability power and the robustness of set agreement-oriented failure detector classesDistributed Computing10.1007/s00446-008-0064-221:3(201-222)Online publication date: 1-Sep-2008
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. asynchronous system
  2. fault-tolerance
  3. unreliable failure detector

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2010)Iterated shared memory modelsProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_36(407-416)Online publication date: 19-Apr-2010
  • (2008)Sharing is harder than agreeingProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400764(85-94)Online publication date: 18-Aug-2008
  • (2008)On the computability power and the robustness of set agreement-oriented failure detector classesDistributed Computing10.1007/s00446-008-0064-221:3(201-222)Online publication date: 1-Sep-2008
  • (2008)The Iterated Restricted Immediate Snapshot ModelProceedings of the 14th annual international conference on Computing and Combinatorics10.1007/978-3-540-69733-6_48(487-497)Online publication date: 27-Jun-2008
  • (2007)Failure detectors are schedulersProceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing10.1145/1281100.1281146(308-309)Online publication date: 12-Aug-2007
  • (2007)Partition approach to failure detectors for k-set agreementProceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing10.1145/1281100.1281145(306-307)Online publication date: 12-Aug-2007
  • (2007)Applied Self-HealingProceedings of the 13th Pacific Rim International Symposium on Dependable Computing10.1109/PRDC.2007.20(179-186)Online publication date: 17-Dec-2007
  • (2006)In search of the holy grailProceedings of the 10th international conference on Principles of Distributed Systems10.1007/11945529_2(3-19)Online publication date: 12-Dec-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media