|
|||||
|
|
A simple proof of the uniform consensus synchronous lower bound |
|
| Authors: | Idit Keidar Sergio Rajsbaum |
| Affiliation: | a MIT Lab for Computer Science, Cambridge, MA, USA b Technion Department of Electrical Engineering, Haifa, Israel c Compaq Cambridge Research Laboratory, One Cambridge Center, Cambridge, MA 02142-1612, USA |
| Abstract: | We give a simple and intuitive proof of an f+2 round lower bound for uniform consensus. That is, we show that for every uniform consensus algorithm tolerating t failures, and for every f?t−2, there is an execution with f failures that requires f+2 rounds. |
| Keywords: | Distributed computing Fault tolerance Lower bounds Consensus |
| 本文献已被 ScienceDirect 等数据库收录！ | |