Michael Ben-Or
ABSTRACT
Recently, Fischer, Lynch and Paterson [3] proved that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We exhibit here a probabilistic solution for this problem, which guarantees that as long as a majority of the processes continues to operate, a decision will be made (Theorem 1). Our solution is completely asynchronous and is rather strong: As in [4], it is guaranteed to work with probability 1 even against an adversary scheduler who knows all about the system.
- 1.Dolev, D. and Strong, R. Polynomial Algorithms for Byzantine Agreement. Proc. 14th ACM Symp. on Theory of Computing (1982), 401-407. Google Scholar
Digital Library
- 2.Fischer, M. and Lynch, N. A Lower Bound for the Time to Assure Interactive Consistency. Information Processing Letters 14, 4 (1982), 182-186.Google ScholarCross Ref
- 3.Fischer, M., Lynch, N. and Paterson, M. Impossibility of Distributed Consensus With One Faulty Process. MIT/LCS/TR-282. Google ScholarDigital Library
- 4.Lehman, D. and Rabin, M. On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. to appear.Google Scholar
Index Terms
- Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols
Recommendations
Perfectly-Secure Asynchronous MPC for General Adversaries (Extended Abstract)
Progress in Cryptology – INDOCRYPT 2020AbstractWe study perfectly-secure Multiparty Computation (MPC) in the asynchronous communication setting, tolerating a generalized non-threshold adversary, characterized by an adversary structure. Ashwin Kumar et al. (ACISP2002) presented a condition ...
High Throughput Secure MPC over Small Population in Hybrid Networks (Extended Abstract)
Progress in Cryptology – INDOCRYPT 2020AbstractWe study secure multi-party computation (MPC) among small number of parties, in partially synchronous and completely asynchronous settings. Prior works have only considered the synchronous setting. The setting considered in this paper is that of
The Resiliency of MPC with Low Interaction: The Benefit of Making Errors (Extended Abstract)
Theory of CryptographyAbstractWe study information-theoretic secure multiparty protocols that achieve full security, including guaranteed output delivery, at the presence of an active adversary that corrupts a constant fraction of the parties. It is known that 2 rounds are ...
Comments