Byzantine Agreement with Unknown Participants and Failures
Authors:
- 1 May 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 952-961
Abstract
A set of mutually distrusting participants that want to agree on a common opinion must solve an instance of a Byzantine agreement problem. These problems have been extensively studied in the literature. However, most of the existing solutions assume that the participants are aware of n — the total number of participants in the system — and f — an upper bound on the number of Byzantine participants. In this paper, we show that most of the fundamental agreement problems can be solved without affecting resiliency even if the participants do not know the values of(possibly changing) n and f. Specifically, we consider a synchronous system where the participants have unique but not necessarily consecutive identifiers, and give Byzantine agreement algorithms for reliable broadcast, approximate agreement, rotor-coordinator, early terminating consensus and total ordering in static and dynamic systems, all with the optimal resiliency of n>3f. Moreover, we show that some synchrony is necessary as an agreement with probabilistic termination is impossible in a semi-synchronous or asynchronous system if the participants are unaware of n and f.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Multidimensional agreement in Byzantine systemsDistributed Computing, 2015
- Byzantine Consensus with Unknown ParticipantsLecture Notes in Computer Science, 2008
- Self-stabilizing clock synchronization in the presence of Byzantine faultsJournal of the ACM, 2004
- Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 RoundsSIAM Journal on Computing, 1998
- Reaching (and maintaining) agreement in the presence of mobile faults1994
- Optimal early stopping in distributed consensus1992
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Simulating authenticated broadcasts to derive simple fault-tolerant algorithmsDistributed Computing, 1987
- Reaching approximate agreement in the presence of faultsJournal of the ACM, 1986
- A lower bound for the time to assure interactive consistencyInformation Processing Letters, 1982