Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/814
Title: The power and limit of adding synchronization messages for synchronous agreement
Authors: Cao, J 
Raynal, M
Wang, X
Wu, W
Keywords: Distributed system
Early-stopping
Lower bound
Message-passing
Round-based computation
Two-step
Uniform consensus
Synchronous system
Issue Date: 2006
Publisher: IEEE Computer Society
Source: Proceedings of the 2006 International Conference on Parallel Processing : 14-18 August 2006, Columbus, Ohio, [p. 1-8] How to cite?
Abstract: This paper investigates the use of additional synchronization messages in round-based message-passing synchronous systems. It first presents a synchronous computation model allowing a process to send such messages. The difference with respect to the traditional round-based synchronous model lies in the sending phase, where a process can first send a data message to each other process, and then, without a break, a synchronization message (their sendings can be pipelined). This model is suited to the class of local area networks where communication channels are reliable. (It is not for networks where unreliable communication requires message retransmission.)
To illustrate the model, the paper presents a uniform consensus algorithm suited to this model. This algorithm, based on the rotating coordinator paradigm, allows the processes to decide in at most f + 1 rounds where f is the actual number of processes that crash in the corresponding run. (This improves the f + 2 lower bound of the traditional synchronous model.) In addition to its efficiency, the algorithm enjoys another first class property, namely, design simplicity. The paper focuses also on lower bound results, and shows that any uniform consensus algorithm designed for the proposed model, requires at least f + 1 rounds in the worst case. The proposed algorithm is consequently optimal. In that sense the paper has to be seen as an investigation of both the power and the limit of adding synchronization messages to synchronous systems built on top of local networks with reliable communication.
URI: http://hdl.handle.net/10397/814
ISBN: 0-7695-2636-5
0-7695-2637-3
Rights: © 2006 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Appears in Collections:Conference Paper

Files in This Item:
File Description SizeFormat 
synchronous-agreement_06.pdf191.3 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

273
Last Week
1
Last month
Checked on Aug 13, 2017

Download(s)

291
Checked on Aug 13, 2017

Google ScholarTM

Check



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