arXiv (Cornell University) · 2017 · 45 citations · 38 references
Open access
ComputingComputer EngineeringComputer ScienceAlgorithmsCryptographyDistributed SystemsConsensus AlgorithmsConsensus ProtocolsDistributed AlgorithmsDistributed ComputingDistributed ConsensusSecure Multi-party ComputationBlockchain Consensus
This paper presents a new Byzantine consensus algorithm targeting consortium blockchains. To this end, it first revisits the consensus validity property by requiring that the decided value satisfies a predefined predicate, which does not systematically exclude a value proposed only by Byzantine processes, thereby generalizing the validity properties found in the literature. Then, the paper presents a simple and modular Byzantine consensus algorithm that relies neither on a leader, nor on signatures, nor on randomization. It features the fastest multivalued reduction to binary consensus we know of and a time optimal binary Byzantine consensus algorithm. The multivalued reduction runs multiple instances of binary consensus concurrently, which result in a bitmask that is then applied to a vector of multivalued proposals to filter out a valid proposed value that is decided. To ensure eventual decision deterministically, the underlying binary consensus algorithm assumes eventual synchrony.
38
Unreliable failure detectors for reliable distributed systems
Tushar Chandra, Sam Toueg · Journal of the ACM · 1996 · 2.5K citations · Full text