A bivalency proof of the lower bound for uniform consensus |
| |
Authors: | Xianbing Wang Yong Meng Teo Jiannong Cao |
| |
Affiliation: | a Singapore-Massachusetts Institute of Technology Alliance, 117576 Singapore b Department of Computer Science, National University of Singapore, 117543 Singapore c Department of Computing, Hong Kong Polytechnic University, Hong Kong |
| |
Abstract: | Bivalency argument is a widely-used technique that employs forward induction to show impossibility results and lower bounds related to consensus. However, for a synchronous distributed system of n processes with up to t potential and f actual crash failures, applying bivalency argument to prove the lower bound for reaching uniform consensus is still an open problem. In this paper, we address this problem by presenting a bivalency proof that the lower bound for reaching uniform consensus is (f+2)-rounds where 0?f?t−2. |
| |
Keywords: | Uniform consensus Bivalency argument Synchronous distributed systems Distributed computing |
本文献已被 ScienceDirect 等数据库收录! |