Reaching Agreement in the Presence of Faults

Summary

It is shown that the problem is solvable for, and only for, n ≥ 3m + 1, where m is the number of faulty processors and n is the total number and this weaker assumption can be approximated in practice using cryptographic methods.

Keywords

Relay, Value (mathematics), Computer science, Set (abstract data type), Arithmetic

References

SIFT: Design and analysis of a fault-tolerant computer for aircraft controlJohn H. Wensley, Leslie Lamport, Jack Goldberg — 1978
Synchronization and Matching in Redundant SystemsDavies, Wakerly — 1978
A method for obtaining digital signatures and public-key cryptosystemsRonald L. Rivest, Adi Shamir, Leonard M. Adleman — 1978
New Directions in CryptographyWhitfield Diffie, Martin E. Hellman — 1976

Cited by

Communication-efficient randomized consensusDan Alistarh, James Aspnes, Valerie King — 2014
Multicast survivability in hierarchical broadcast networksAzad Azadmanesh, Axel Krings, Daryush Laqab — 2008
Quantum Byzantine Agreement via Hardy correlations and entanglement swappingRamij Rahaman, Marcin Wieśniak, Marek Żukowski — 2014
Programming Model and Protocols for Reconfigurable Distributed SystemsCosmin Arad — 2013
A Fault Model for Survivable ApplicationsJohn McDermott — 2002
A Scalable Byzantine Fault Tolerant Service in Grid SystemXiu-Qun Wang, Honglun Hou, Yueting Zhuang — 2006
Faults and fault-tolerance in distributed computing systems: the election problemByungho Yi — 1994
FAULT TOLERANCE BY A DISTRIBUTED SOFTWARE CONTROL FOR A HIGH RELIABILITYEmmanuelle Renaux, Cran Lara — 1992
Towards dual fallible agreement in a virtual subnet networkShu-Ching Wang, Kuo-Qin Yan, Guang-Yan Zheng — 2007
Distributed Encryption and Decryption AlgorithmsA.J. Postma, Willem de Boer, Arne Helme — 1996
The "Engineering" of Fault-Tolerant Distributed Computing SystemsÖzalp Babaoğlu — 1986
Capacity of Byzantine Agreement: Tight Bound for the Four Node NetworkGuanfeng Liang, Nitin H. Vaidya — 2010
Petri Nets for Systems EngineeringClaude Girault, Rüdiger Valk — 2003
Optimized Self-synchronizing Byzantine Agreement ProtocolsF.M. Postma, T. Krol, Egbert Molenkamp — 1997
Mutual Informational Coordination in Incompletely Connected Multicomputer SystemsI.V. Asharina, A. V. Lobanov, I. G. Mishenko — 2003
Claiming security properties in a service oriented architectureS. L. C. Verberkt — 2012
Evolution vs. Intelligent Design in Consensus ProtocolsYingjie Song, Robbert van Renesse, Fred B. Schneider — 2007
A Logic of Finite Syntactic Epistemic StatesThomas Ågotnes — 2004
Byzantine Fault Isolation in the Farsite Distributed File SystemJohn R. Douceur, Jon Howell — 2006
Fault-tolerate Multiparty Electronic Contract Signing ProtocolDongyao Ji, Dengguo Feng — 2006

Related papers

A total power minimization approach to relay selection for two-way relay networksSaurabh Talwar, Shahram Shahbazpanahi — 2012
A unified relay framework with both D-F and C-F relay nodesXiugang Wu, Liang‐Liang Xie — 2012
Dynamic Selection Scheme for Cooperative Relay under High Mobility Environment赵军辉, Du, Jiajiao — 2014
Analyzing Selection and Application of a RelayYun Li — 2004
A New Modification on Relay Selection by Considering the Effect of Relay OccupancyShahriar Shirvani Moghaddam, Fahimeh Baramaki Yazdi — 2015
Detectability of Symbol Manipulation by an Amplify-and-Forward RelayEric Graves, Tan F. Wong — 2012
On relay selection to maximize coverage region for cooperative cellular networks with multiple fixed and unfixed relaysNiloofar Okati, Behrooz Razeghi, M. R. Mosavi — 2015
A Unified Relay Framework With Both D-F and C-F Relay NodesXiugang Wu, Liang‐Liang Xie — 2014