Paper Info
Title
Structured derivation of semi-synchronous algorithms
Abstract
The semi-synchronous model is an important middle ground between the synchronous and the asynchronous models of distributed computing. In this model, processes can detect (timeout) when other processes fail. However, since detection is done by timing out, it incurs a cost much higher than the typical delay of messages. The paper presents a new communication primitive, TimelyAnnounced Broadcast (TAB), and uses it in algorithms for consensus and set consensus in the semi-synchronous model. Separate implementations of TAB, withstanding different types of failures, allow to derive algorithms for consensus and set consensus under crash and omission failures. The time bounds obtained by our algorithms asymptotically match, or improve, the previously known bounds.
Year
DOI
Venue
2011
10.1007/978-3-642-24100-0_37
DISC
Keywords
Field
DocType
important middle ground,timelyannounced broadcast,typical delay,asynchronous model,structured derivation,different type,separate implementation,semi-synchronous model,new communication,semi-synchronous algorithm,omission failure,terminating reliable broadcast
Asynchronous communication,Broadcasting,Crash,Computer science,Terminating Reliable Broadcast,Algorithm,Implementation,Real-time computing,Timeout,Distributed computing
Conference
Volume
ISSN
Citations 
6950
0302-9743
2
PageRank 
References 
Authors
0.37
17
5
Name
Order
Citations
PageRank
Hagit Attiya12475199.24
Fatemeh Borran2102.23
Martin Hutle314110.14
Zarko Milosevic45610.35
André Schiper53537275.09