research-article

Distributed computability in Byzantine asynchronous systems

Authors:

Hammurabi Mendes,

Christine Tasson,

Maurice HerlihyAuthors Info & Claims

STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

Pages 704 - 713

https://doi.org/10.1145/2591796.2591853

Published: 31 May 2014 Publication History

Abstract

In this work, we extend the topology-based approach for characterizing computability in asynchronous crash-failure distributed systems to asynchronous Byzantine systems. We give the first theorem with necessary and sufficient conditions to solve arbitrary tasks in asynchronous Byzantine systems where an adversary chooses faulty processes. For colorless tasks, an important subclass of distributed problems, the general result reduces to an elegant model that effectively captures the relation between the number of processes, the number of failures, as well as the topological structure of the task's simplicial complexes.

Supplementary Material

MP4 File (p704-sidebyside.mp4)

Download
248.63 MB

References

[1]

H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524--548, July 1990.

Digital Library

[2]

H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, March 2004.

[3]

E. Borowsky, E. Gafni, N. Lynch, and S. Rajsbaum. The BG distributed simulation algorithm. Distributed Computing, 14(3):127--146, 2001.

Digital Library

[4]

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

Digital Library

[5]

C. Cachin, R. Guerraoui, and L. Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer, 2 edition, February 2011.

[6]

S. Chaudhuri. More choices allow more faults: set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132--158, July 1993.

Digital Library

[7]

R. de Prisco, D. Malkhi, and M. Reiter. On k-set consensus problems in asynchronous systems. IEEE Transactions on Parallel and Distributed Systems, 12(1):7--21, January 2001.

Digital Library

[8]

D. Dolev, N. Lynch, S. Pinter, E. Stark, and W. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):499--516, May 1986.

Digital Library

[9]

M. Fischer, N. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, 1985.

Digital Library

[10]

M. J. Fischer. The consensus problem in unreliable distributed systems (a brief survey). Technical Report YALEU/DCS/TR-273, Yale University, Department of Computer Science, 2000.

[11]

M. Herlihy and S. Rajsbaum. Concurrent computing and shellable complexes. In N. Lynch and A. Shvartsman, editors, Distributed Computing, volume 6343 of Lecture Notes in Computer Science, pages 109--123. Springer Berlin Heidelberg, 2010.

Digital Library

[12]

M. Herlihy and S. Rajsbaum. The topology of shared-memory adversaries. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on principles of distributed computing, PODC '10, pages 105--113, New York, NY, USA, 2010.

Digital Library

[13]

M. Herlihy and S. Rajsbaum. Simulations and reductions for colorless tasks. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, PODC '12, pages 253--260, New York, NY, USA, 2012. ACM.

Digital Library

[14]

M. Herlihy, S. Rajsbaum, and M. Tuttle. An axiomatic approach to computing the connectivity of synchronous and asynchronous systems. Electronic Notes in Theoretical Computer Science, 230(0):79--102, 2009.

Digital Library

[15]

M. Herlihy and N. Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858--923, 1999.

Digital Library

[16]

F. Junqueira and K. Marzullo. Designing algorithms for dependent process failures. In A. Schiper, A. Shvartsman, H. Weatherspoon, and B. Zhao, editors, Future Directions in Distributed Computing, volume 2584 of Lecture Notes in Computer Science, pages 24--28. Springer Berlin Heidelberg, 2003.

Digital Library

[17]

D. N. Kozlov. Combinatorial Algebraic Topology, volume 21 of Algorithms and Computation in Mathematics. Springer, 1 edition, October 2007.

[18]

L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transaction on Programming Languages and Systems, 4(3):382--401, July 1982.

Digital Library

[19]

N. A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.

Digital Library

[20]

D. Malkhi, M. Merritt, M. K. Reiter, and G. Taubenfeld. Objects shared by Byzantine processes. Distributed Computing, 16(1):37--48, February 2003.

Digital Library

[21]

H. Mendes and M. Herlihy. Multidimensional approximate agreement in Byzantine asynchronous systems. In Proceedings of the 45th annual ACM Symposium on Theory of Computing, STOC'13, pages 391--400, New York, NY, USA, 2013. ACM.

Digital Library

[22]

J. Munkres. Elements of Algebraic Topology. Prentice Hall, 2 edition, January 1984.

[23]

G. Neiger. Distributed consensus revisited. Information Processing Letters, 49(4):195--201, February 1994.

Digital Library

[24]

T. Srikanth and S. Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80--94, 1987.

Digital Library

Cited By

Liu XTheriault SWu JYue Y(2024)Algebraic topology and distributed computingFoundations of Data Science10.3934/fods.2024008(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024008
van Ditmarsch HFruzsa KKuznets RSchmid U(2024)A Logic for Repair and State Recovery in Byzantine Fault-Tolerant Multi-agent SystemsAutomated Reasoning10.1007/978-3-031-63501-4_7(114-134)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-63501-4_7
Rincon Galeana HSchmid U(2024)Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed SystemsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_29(501-506)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_29
Show More Cited By

Index Terms

Distributed computability in Byzantine asynchronous systems

Recommendations

Multidimensional approximate agreement in Byzantine asynchronous systems
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

The problem of ε-approximate agreement in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values that lie in R^m, for m ≥ 1, and present an optimal protocol in ...
Consensus in byzantine asynchronous systems

This paper presents a consensus protocol resilient to Byzantine failures. It uses signed and certified messages and is based on two underlying failure detection modules. The first is a muteness failure detection module of the class ♦M. The second is a ...
Access cost for asynchronous Byzantine quorum systems

Quorum systems have been used to implement many coordination problems in distributed systems. In this paper, we study the cost of accessing quorums in asynchronous systems. We formally define the asynchronous access cost of quorum systems and argue that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

May 2014

984 pages

ISBN:9781450327107

DOI:10.1145/2591796

Program Chair:
David Shmoys
Cornell University

Copyright © 2014 ACM.

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 the author(s) 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '14

Sponsor:

SIGACT

STOC '14: Symposium on Theory of Computing

May 31 - June 3, 2014

New York, New York

Acceptance Rates

STOC '14 Paper Acceptance Rate 91 of 319 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
234
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu XTheriault SWu JYue Y(2024)Algebraic topology and distributed computingFoundations of Data Science10.3934/fods.2024008(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024008
van Ditmarsch HFruzsa KKuznets RSchmid U(2024)A Logic for Repair and State Recovery in Byzantine Fault-Tolerant Multi-agent SystemsAutomated Reasoning10.1007/978-3-031-63501-4_7(114-134)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-63501-4_7
Rincon Galeana HSchmid U(2024)Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed SystemsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_29(501-506)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_29
Schlögl TSchmid U(2023)A Sufficient Condition for Gaining Belief in Byzantine Fault-Tolerant Distributed SystemsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.379.37379(487-506)Online publication date: 11-Jul-2023
https://doi.org/10.4204/EPTCS.379.37
Civit PGilbert SGuerraoui RKomatovic JVidigueira MOshman RNolin AHalldorsson MBalliu A(2023)On the Validity of ConsensusProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594567(332-343)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594567
Tawose OYang LZhao D(2023)TopoCommit: A Topological Commit Protocol for Cross-Ledger Transactions in Scientific Computing2023 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER52292.2023.00038(365-375)Online publication date: 31-Oct-2023
https://doi.org/10.1109/CLUSTER52292.2023.00038
Alistarh DEllen FRybicki J(2023)Wait-free approximate agreement on graphsTheoretical Computer Science10.1016/j.tcs.2023.113733(113733)Online publication date: Jan-2023
https://doi.org/10.1016/j.tcs.2023.113733
Fraigniaud PGelles RLotker Z(2023)The topology of randomized symmetry-breaking distributed computingJournal of Applied and Computational Topology10.1007/s41468-023-00150-9Online publication date: 13-Nov-2023
https://doi.org/10.1007/s41468-023-00150-9
Yue YLiu XLei FWu J(2022)A Topological Characterization to Arbitrary Resilient Asynchronous ComplexityMathematics10.3390/math1015272010:15(2720)Online publication date: 1-Aug-2022
https://doi.org/10.3390/math10152720
Xue YHerlihy M(2022)Invited Paper: Cross-Chain State Machine ReplicationStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_4(51-65)Online publication date: 9-Nov-2022
https://doi.org/10.1007/978-3-031-21017-4_4
Show More Cited By

View Options

Get Access

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents