Paper Info
Title
The Power and Limit of Adding Synchronization Messages for Synchronous Agreement
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
Year
DOI
Venue
2006
10.1109/ICPP.2006.69
ICPP
Keywords
Field
DocType
synchronous system.,early-stopping,synchronous agreement,two-step,additional synchronization message,lower,round-based message-passing synchronous systems,round-based computation,round-based message-passing synchronous system,traditional synchronous model,synchronous system,uniform consensus algorithm,synchronous computation model,bound,uniform consensus,proposed algorithm,traditional round-based synchronous model,synchronization messages,message passing,lower bound,synchronization message,rotating coordinator paradigm,message-passing,distributed system,local area networks,synchronisation,local area network,early stopping,communication channels,algorithm design
Early stopping,Synchronization,Upper and lower bounds,Computer science,Retransmission,Parallel computing,Computer network,Communication channel,Uniform consensus,Message passing,Computation,Distributed computing
Conference
ISSN
ISBN
Citations 
0190-3918
0-7695-2636-5
0
PageRank 
References 
Authors
0.34
13
4
Name
Order
Citations
PageRank
Jiannong Cao15226425.12
Michel Raynal24078349.46
Xianbing Wang3909.98
Wei-Gang Wu442548.87