2020 · 47 citations · 16 references
ComputingComputer ScienceComputer SystemsFault ToleranceFault-tolerant ComputingFault-tolerant SystemsConcurrency ControlDistributed ConsensusDistributed TransactionsFault Tolerance In CommunicationFault-tolerant CommunicationReliable Distributed SystemsBroadcastByzantine BroadcastCommitCommit ProtocolsFault-tolerant ConsensusFault-tolerant Consensus ProtocolsSynchronous Communication ProtocolsUpper Bounds
Synchronous consensus protocols, by definition, have a worst-case commit latency that depends on the bounded network delay. The notion of optimistic responsiveness was recently introduced to allow synchronous protocols to commit instantaneously when some optimistic conditions are met. In this work, we revisit this notion of optimistic responsiveness and present optimal latency results. We present a lower bound for Byzantine Broadcast that relates the latency of optimistic and synchronous commits when the designated sender is honest and while the optimistic commit can tolerate some faults. We then present two matching upper bounds for tolerating f faults out of $n = 2f+1$ parties. Our first upper bound result achieves optimal optimistic and synchronous commit latency when the designated sender is honest and the optimistic commit can tolerate at least one fault. We experimentally evaluate this protocol and show that it achieves throughput comparable to state-of-the-art synchronous and partially synchronous protocols and under optimistic conditions achieves latency better than the state-of-the-art. Our second upper bound result achieves optimal optimistic and synchronous commit latency when the designated sender is honest but the optimistic commit does not tolerate any faults. The presence of matching lower and upper bound results make both of the results tight for $n = 2f+1$. Our upper bound results are presented in a state machine replication setting with a steady-state leader who is replaced with a view-change protocol when they do not make progress. For this setting, we also present an optimistically responsive protocol where the view-change protocol is optimistically responsive too.
16
Yossi Gilad, Rotem Hemo, Silvio Micali et al. · 2017 · 1.5K citations · Full text
Maofan Yin, Dahlia Malkhi, Michael K. Reiter et al. · 2019 · 944 citations · Full text
Authenticated Algorithms for Byzantine Agreement
Danny Dolev, H. Raymond Strong · SIAM Journal on Computing · 1983 · 641 citations