Article

Free access

Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony

Author:

Eli GafniAuthors Info & Claims

PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing

Pages 143 - 152

https://doi.org/10.1145/277697.277724

Published: 01 June 1998 Publication History

PDF eReader

References

[1]

T. E. Elrad and N. Francez. Decomposition of distributed programs into communication-closed layers. Science of Computer Programming, Vol. 2(3). 1982.

Google Scholar

[2]

Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2): 130-143, November 1987.

Digital Library

Google Scholar

[3]

Brian Coan. A compiler that increases the faulttolerance of asynchronous protocols. IEEE Transactions on Computers, Vol. 37, No.12, pages 1541-1553. IEEE press, Dec. 1988.

Digital Library

Google Scholar

[4]

Elizabeth Borowsky and Eli Gafni. A Simple Algorithmically Reason Characterization of Wait- Free Computations. Proceedings of the 16th ACM Symposium on Principles of Distributed Computing, pages 189-198. ACM press, Aug. 1997.

Digital Library

Google Scholar

[5]

Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. Journal of the ACM, 43(4):685- 722, July 1996.

Digital Library

Google Scholar

[6]

Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for asynchronous systems. Journal of the ACM, 43(2):225-267, March 1996.

Digital Library

Google Scholar

[7]

Wai-Kau Lo and Vassos Hadzilacos. Using failure detectors to solve consensus in asynchronous shared-memory systems. In Gerard Tel and Paul Vitfinyi, editors, Proceedings of the Eighth International Workshop on Distributed Algorithms, number 857 in Lecture Notes on Computer Science, pages 280-295. Spfinger-Vefiag, September 1994.

Digital Library

Google Scholar

[8]

Gil Neiger. Failure detectors and the wait-free hierarchy. In Proceedings of the Fourteenth ACM Symposium on Principles of Distributed Computing, pages 100-109. ACM Press, August 1995.

Digital Library

Google Scholar

[9]

Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing, pages 91-100. ACM Press, May 1993.

Digital Library

Google Scholar

[10]

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985.

Digital Library

Google Scholar

[11]

Maurice Hefiihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the Twenty-Fifth ACM Symposium on Theory of Computing, pages 111- 120. ACM Press, May 1993.

Digital Library

Google Scholar

[12]

Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the Twenty- Fifth A CM Symposium on Theory of Computing, pages I01-110. ACM Press, May 1993.

Digital Library

Google Scholar

[13]

Soma Chaudhuri, Maurice Herlihy, Nancy Lynch, and Mark R. Tuttle. A tight lower bound for k-set agreement. In Proceedings of the Thirty-Fourth Symposium on Foundations of Computer Science, pages 206-215. IEEE Computer Society Press, November 1993.

Digital Library

Google Scholar

[14]

Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14:183- 186, 1982.

Crossref

Google Scholar

[15]

Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34( 1):77-97, January 1987.

Digital Library

Google Scholar

[16]

Gil Neiger and Sam Toueg. Automatically Increasing the Fault-Tolerance of Distributed Algorithms. Journal of Algorithms, Vol. 11, No. 3, pages 374-419, Sep. 1990.

Digital Library

Google Scholar

[17]

Jiong Yang, Gil Neiger, and Eli Gafni. Structured Derivations of Consensus Algorithms for Failure Detectors. In Proceedings of the Seventeenth ACM Symposium on Principles of Distributed Computing (this volume). ACM Press, 1998. To appear.

Digital Library

Google Scholar

[18]

Baruch Awerbuch. Complexity of Network Synchronization. Journal of the ACM, Vol. 32, No.4, pages 804-82, Oct. 1985.

Digital Library

Google Scholar

[19]

Maurice Herlihy, Sergio Rajsbaum, and Mark R. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proceedings of the Seventeenth ACM Symposium on Principles of Distributed Computing (this volume). ACM Press, 1998. To appear.

Digital Library

Google Scholar

[20]

Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Journal of the ACM 41 (1): 122-152, Jan 1994.

Digital Library

Google Scholar

[21]

Ching-Tsun Chou and Eli Gafni. Understanding and verifying distributed algorithms using Stratified decomposition. In Proceedings of the Seventh ACM Symposium on Principles of Distributed Computing, pages 44-65. ACM Press, August 1988.

Digital Library

Google Scholar

[22]

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873-890, September 1993.

Digital Library

Google Scholar

[23]

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. journal of the ACM, 42(1):124-142, January 1995.

Digital Library

Google Scholar

[24]

Soma Chaudhuri. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems, information and Computation, 103(1):132-158, July 1993.

Digital Library

Google Scholar

Cited By

View all

Malkhi DStathakopoulou CYin M(2025)BBCA-Chain: Low Latency, High Throughput BFT Consensus on a DAGFinancial Cryptography and Data Security10.1007/978-3-031-78676-1_4(51-73)Online publication date: 22-Feb-2025
https://doi.org/10.1007/978-3-031-78676-1_4
Mostefaoui APerrin MWeibel JKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Randomized Consensus: Common Coins Are not the Holy Grail!Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662824(36-39)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662824
Winkler KPaz AGaleana HSchmid SSchmid U(2024)The Time Complexity of Consensus Under Oblivious Message AdversariesAlgorithmica10.1007/s00453-024-01209-486:6(1830-1861)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00453-024-01209-4
Show More Cited By

Index Terms

Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony

Recommendations

Transient fault detectors

We present fault detectors for transient faults, (i.e., corruptions of the memory of the processors, but not of the code of the processors). We distinguish fault detectors for tasks (i.e., the problem to be solved) from failure detectors for ...
Fail-aware failure detectors
SRDS '96: Proceedings of the 15th Symposium on Reliable Distributed Systems

In existing asynchronous distributed systems it is impossible to implement failure detectors which are perfect, i.e. they only suspect crashed processes and eventually suspect all crashed processes. Some recent research has however proposed that any "...
The expressive powers of the logic programming semantics (extended abstract)
PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

We compare the expressive powers of three semantics for deductive databases and logic programming: the 3-valued program completion semantics, the well-founded semantics, and the stable semantics, We identify the expressive power of the stable semantics, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing

June 1998

334 pages

ISBN:0897919777

DOI:10.1145/277697

Chairmen:
Brian Coan
Bellcore
,
Yehuda Afek
Tel-Aviv Univ.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC98

Sponsor:

PODC98: Seventeenth Annual ACM Symposium on Principles of Distributed Computing

June 28 - July 2, 1998

Puerto Vallarta, Mexico

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

129
Total Citations
View Citations
931
Total Downloads

Downloads (Last 12 months)123
Downloads (Last 6 weeks)19

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Malkhi DStathakopoulou CYin M(2025)BBCA-Chain: Low Latency, High Throughput BFT Consensus on a DAGFinancial Cryptography and Data Security10.1007/978-3-031-78676-1_4(51-73)Online publication date: 22-Feb-2025
https://doi.org/10.1007/978-3-031-78676-1_4
Mostefaoui APerrin MWeibel JKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Randomized Consensus: Common Coins Are not the Holy Grail!Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662824(36-39)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662824
Winkler KPaz AGaleana HSchmid SSchmid U(2024)The Time Complexity of Consensus Under Oblivious Message AdversariesAlgorithmica10.1007/s00453-024-01209-486:6(1830-1861)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00453-024-01209-4
Naor OKeidar I(2024)Expected linear round synchronization: the missing link for linear Byzantine SMRDistributed Computing10.1007/s00446-023-00459-937:1(19-33)Online publication date: 8-Jan-2024
https://doi.org/10.1007/s00446-023-00459-9
Durand ARaynal MTaubenfeld G(2024)Better Sooner Rather Than LaterStructural Information and Communication Complexity10.1007/978-3-031-60603-8_13(226-237)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_13
Malkhi DYin MLiu YSchiller E(2023)Invited Paper: Lessons from HotStuffProceedings of the 5th workshop on Advanced tools, programming languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3584684.3597268(1-8)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3584684.3597268
Alistarh DEllen FRybicki J(2023)Wait-free approximate agreement on graphsTheoretical Computer Science10.1016/j.tcs.2023.113733948:COnline publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113733
Civit PDzulfikar MGilbert SGramoli VGuerraoui RKomatovic JVidigueira M(2023)Byzantine consensus is $$\Theta (n^2)$$: the Dolev-Reischuk bound is tight even in partial synchrony!Distributed Computing10.1007/s00446-023-00458-w37:2(89-119)Online publication date: 11-Dec-2023
https://doi.org/10.1007/s00446-023-00458-w
Jahanian MRamakrishnan K(2022)CoNICE: Consensus in Intermittently-Connected Environments by Exploiting Naming With Application to Emergency ResponseIEEE/ACM Transactions on Networking10.1109/TNET.2022.315610130:5(1926-1939)Online publication date: Oct-2022
https://doi.org/10.1109/TNET.2022.3156101
Bouzid ZSutra PTravers C(2022)Agreeing within a few writesTheoretical Computer Science10.1016/j.tcs.2022.04.030922:C(283-299)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.04.030
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Transient fault detectors

Fail-aware failure detectors

The expressive powers of the logic programming semantics (extended abstract)