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 Nov 6, 2018

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
0
Citations as of Nov 16, 2018

Page view(s)

76
Last Week
0
Last month
Citations as of Nov 12, 2018

Google ScholarTM

Check

Altmetric


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