Abstract
Most existing consensus protocols for synchronous distributed systems are designed to tolerate crash failures of processes. It has been proved that there is no n-process stopping consensus protocol for synchronous distributed systems that tolerates up to t crash failures, in which all non-faulty processes always decide by the end of round t, where t < n-1 and n is the total number of processes, t is the maximum number of failures that can occur. Furthermore, the well-known lower bound, min (t+1, f+2), has been proved for early stopping synchronous consensus protocols, where f ≤ t, and f is the number of failures that actually occur in the system. In this paper, we propose a consensus protocol for synchronous distributed systems with orderly crash failures [4], which is both time and message efficient than those existing protocols applied in this failure model. The proposed protocol achieves uniform consensus and tolerates up to t failures, in which all non-faulty processes always make decision and stop immediately by the end of f+1 rounds, where t < n, f ≤ t. When there is no failure, the protocol can achieve uniform consensus and stop within one round. We prove that the lower bounds of early stopping protocols for both consensus and uniform consensus in orderly crash failure model are f+1 rounds, which ensure our proposed protocol is optimal.
Original language | English |
---|---|
Title of host publication | Proceedings - 23rd International Conference on Distributed Computing Systems Workshops, ICDCSW 2003 |
Publisher | IEEE |
Pages | 76-81 |
Number of pages | 6 |
ISBN (Electronic) | 0769519210, 9780769519210 |
DOIs | |
Publication status | Published - 1 Jan 2003 |
Event | 23rd International Conference on Distributed Computing Systems Workshops, ICDCSW 2003 - Providence, United States Duration: 19 May 2003 → 22 May 2003 |
Conference
Conference | 23rd International Conference on Distributed Computing Systems Workshops, ICDCSW 2003 |
---|---|
Country/Territory | United States |
City | Providence |
Period | 19/05/03 → 22/05/03 |
Keywords
- Clocks
- Computer crashes
- Distributed computing
- Internet
- Mobile computing
- Protocols
ASJC Scopus subject areas
- Computer Networks and Communications
- Hardware and Architecture
- Signal Processing