Skip to Main content Skip to Navigation
New interface
Journal articles

Signature-free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, and Constant Time *

Abstract : This paper presents a new algorithm that reduces multivalued consensus to binary consensus in an asynchronous message-passing system made up of n processes where up to t may commit Byzantine failures. This algorithm has the following noteworthy properties: it assumes t < n/3 (and is consequently optimal from a resilience point of view), uses O(n 2) messages, has a constant time complexity, and uses neither signatures nor additional computational power (such as random numbers, failure detectors, additional sheduling assumption, or additional synchrony assumption). The design of this reduction algorithm relies on two new all-to-all communication abstractions. The first one allows the non-faulty processes to reduce the number of proposed values to c, where c is a small constant. The second communication abstraction allows each non-faulty process to compute a set of (proposed) values satisfying the following property: if the set of a non-faulty process is a singleton containing value v, the set of any non-faulty process contains v. Both communication abstractions have an O(n 2) message complexity and a constant time complexity. The reduction of multivalued Byzantine consensus to binary Byzantine consensus is then a simple sequential use of these communication abstractions. To the best of our knowledge, this is the first asynchronous message-passing algorithm that reduces multivalued consensus to binary consensus with O(n 2) messages and constant time complexity (measured with the longest causal chain of messages) in the presence of up to t < n/3 Byzantine processes, and without using cryptography techniques. Moreover, this reduction algorithm uses a single instance of the underlying binary consensus, and tolerates message reordering by Byzantine processes.
Complete list of metadata

https://hal.inria.fr/hal-03427171
Contributor : Achour Mostefaoui Connect in order to contact the contributor
Submitted on : Friday, November 12, 2021 - 11:08:04 PM
Last modification on : Thursday, November 17, 2022 - 4:48:10 PM
Long-term archiving on: : Monday, February 14, 2022 - 12:58:02 AM

File

Final-Acta-Informatica-17-apri...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03427171, version 1

Citation

Achour Mostefaoui, Michel Raynal. Signature-free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, and Constant Time *. Acta Informatica, 2016. ⟨hal-03427171⟩

Share

Metrics

Record views

11

Files downloads

74