Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/32163
Title: Message and time efficient consensus protocols for synchronous distributed systems
Authors: Wang, X
Teo, YM
Cao, J 
Keywords: Consensus
Early stopping
Message efficient
Orderly crash failure
Synchronous distributed systems
Issue Date: 2008
Publisher: Academic Press
Source: Journal of parallel and distributed computing, 2008, v. 68, no. 5, p. 641-654 How to cite?
Journal: Journal of parallel and distributed computing 
Abstract: For a synchronous distributed system of n processes with up to t potential and f actual crash failures, where (t < n - 1, f ≤ t), the time lower bound for a protocol to achieve consensus is min (t + 1, f + 2) rounds. Currently, most researches in this field focus on the time efficiency of consensus protocols. This paper proposes consensus protocols for synchronous distributed systems that achieve both message and time efficiency. Based on an early stopping consensus protocol for synchronous distributed system with crash failures, we propose a rotating coordinator scheme that significantly reduces message complexity. However, this protocol is not time efficient because it requires min (t + 1, f + 3) rounds to reach consensus. Thus, to achieve both time and message efficiency, we propose another protocol in which (t + 1) coordinators are used to send messages in each round. Furthermore, we show that the proposed consensus protocol with crash failures can be revised to be more message-efficient with orderly crash failures. When a process is able to send more than one message to another in a round, we propose an optimal message efficient early stopping consensus protocol for synchronous distributed systems with orderly crash failures.
URI: http://hdl.handle.net/10397/32163
ISSN: 0743-7315
DOI: 10.1016/j.jpdc.2007.08.008
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Sep 24, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Sep 24, 2017

Page view(s)

38
Last Week
1
Last month
Checked on Sep 18, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.