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

Self-stabilizing byzantine agreement

Published: 23 July 2006 Publication History

Abstract

Byzantine agreement algorithms typically assume implicit initial state consistency and synchronization among the correct nodes and then operate in coordinated rounds of information exchange to reach agreement based on the input values. The implicit initial assumptions enable correct nodes to infer about the progression of the algorithm at other nodes from their local state. This paper considers a more severe fault model than permanent Byzantine failures, one in which the system can in addition be subject to severe transient failures that can temporarily throw the system out of its assumption boundaries. When the system eventually returns to behave according to the presumed assumptions it may be in an arbitrary state in which any synchronization among the nodes might be lost, and each node may be at an arbitrary state. We present a self-stabilizing Byzantine agreement algorithm that reaches agreement among the correct nodes in optimal time, by using only the assumption of bounded message transmission delay. In the process of solving the problem, two additional important and challenging building blocks were developed: a unique self-stabilizing protocol for assigning consistent relative times to protocol initialization and a Reliable Broadcast primitive that progresses at the speed of actual message delivery time.

References

[1]
J. Beauquier, S. Kekkonen-Moneta, "Fault-tolerance and Self-stabilization: Impossibility Results and Solutions Using Failure Detectors", Int. J of Systems Science, Vol. 28(11) pp. 1177--1187, 1997.
[2]
B. Coan, D. Dolev, C. Dwork and L. Stockmeyer, "The distributed firing squad problem", Proc. of the 7th Annual ACM Symposium on Theory of Computing, pp. 335--345, Providence, Rhode Island, May 1985.
[3]
A. Daliot, D. Dolev and H. Parnas, "Self-stabilizing Pulse Synchronization Inspired by Biological Pacemaker Networks", Proc. of the 6th Symposium on Self-Stabilizing Systems (SSS'03 San-Francisco), pp. 32--48, 2003.
[4]
A. Daliot and D. Dolev, "Self-stabilization of Byzantine Protocols", Proc. of the 7th Symposium on Self-Stabilizing Systems (SSS'05 Barcelona), pp. 48--67, 2005.
[5]
A. Daliot, D. Dolev and H. Parnas, "Linear Time Byzantine Self-Stabilizing Clock Synchronization", Proc. of 7th Int. Conference on Principles of Distributed Systems (OPODIS'03 La Martinique), France, Dec. 2003.
[6]
A. Daliot and D. Dolev, "Making Order in Chaos: Self-stabilizing Byzantine Pulse Synchronization", unpublished manuscript July 2006.
[7]
S. Dolev, and J. L. Welch, "Self-Stabilizing Clock Synchronization in the presence of Byzantine faults", Journal of the ACM, Vol. 51, Issue 5, pp. 780 -- 799, 2004.
[8]
D. Dolev, H. R. Strong, "Polynomial Algorithms for Multiple Processor Agreement", In Proceedings, the 14th ACM SIGACT Symposium on Theory of Computing (STOC-82), pp. 401--407, May 1982.
[9]
P. Dutta, R. Guerraoui, L. Lamport, "How Fast Can Eventual Synchrony Lead to Consensus?", Proc. of the 2005 Int. Conf. on Dependable Systems and Networks (DSN'05 Yokohama), Japan, June 2005.
[10]
L. Lamport, R. Shostak, M. Pease, "The Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems, 4(3):382--301, 1982.
[11]
M. Pease, R. Shostak, L. Lamport, "Reaching Agreement in the Presence of Faults", Journal of the ACM, Vol. 27, No. 2. pp. 228--234, Apr. 1980.
[12]
S. Toueg, K. J. Perry, T. K. Srikanth, "Fast Distributed Agreement", SIAM Journal on Computing, 16(3):445--457, June 1987.
[13]
J. Widder, "Booting clock synchronization in partially synchronous systems", In Proc. the 17th Int. Symposium on Distributed Computing (DISC'03 Sorrento), Oct. 2003.

Cited By

View all
  • (2022)Reaching Efficient Byzantine Agreements in Bipartite NetworksIEEE Access10.1109/ACCESS.2022.317599810(53578-53600)Online publication date: 2022
  • (2021)Simulating Authenticated Broadcast in Networks of Bounded Degree2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00098(739-746)Online publication date: Dec-2021
  • (2021)Efficient Two-Dimensional Self-Stabilizing Byzantine Clock Synchronization in WALDEN2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00096(723-730)Online publication date: Dec-2021
  • 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. byzantine agreement
  2. byzantine faults
  3. pulse synchronization
  4. reliable broadcast
  5. self-stabilization
  6. transient failures

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)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Reaching Efficient Byzantine Agreements in Bipartite NetworksIEEE Access10.1109/ACCESS.2022.317599810(53578-53600)Online publication date: 2022
  • (2021)Simulating Authenticated Broadcast in Networks of Bounded Degree2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00098(739-746)Online publication date: Dec-2021
  • (2021)Efficient Two-Dimensional Self-Stabilizing Byzantine Clock Synchronization in WALDEN2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00096(723-730)Online publication date: Dec-2021
  • (2021)Reaching self-stabilising distributed synchronisation with COTS Ethernet components: the WALDEN approachReal-Time Systems10.1007/s11241-020-09356-xOnline publication date: 2-Jan-2021
  • (2019)Near-optimal self-stabilising counting and firing squadsDistributed Computing10.1007/s00446-018-0342-632:4(339-360)Online publication date: 1-Aug-2019
  • (2019)Self-Stabilizing Byzantine Clock Synchronization with Optimal PrecisionTheory of Computing Systems10.1007/s00224-017-9840-363:2(261-305)Online publication date: 1-Feb-2019
  • (2016)Self-stabilizing Byzantine Clock Synchronization with Optimal PrecisionStabilization, Safety, and Security of Distributed Systems10.1007/978-3-319-49259-9_18(213-230)Online publication date: 3-Nov-2016
  • (2014)Fault-tolerant algorithms for tick-generation in asynchronous logicJournal of the ACM10.1145/256056161:5(1-74)Online publication date: 8-Sep-2014
  • (2014)Rigorously modeling self-stabilizing fault-tolerant circuitsJournal of Computer and System Sciences10.1016/j.jcss.2014.01.00180:4(860-900)Online publication date: 1-Jun-2014
  • (2014)Tight Bound on Mobile Byzantine AgreementDistributed Computing10.1007/978-3-662-45174-8_6(76-90)Online publication date: 2014
  • Show More Cited By

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