The Perfectly-Synchronized Round-based Model of Distributed Computing

• Published in: Information & Computation, vol. 205, num. 5, p. 783-815
• Publication date: 2007

The perfectly-synchronized round-based model provides the powerful abstraction of crash-stop failures with atomic and synchronous message delivery. This abstraction makes distributed programming very easy.We describe a technique to automatically transform protocols devised in the perfectly-synchronized round-based model into protocols for the crash, send omission, general omission or Byzantine models. Our transformation is achieved using a round shifting technique with a constant time complexity overhead. The overhead depends on the target model: crashes, send omissions, general omissions or Byzantine failures. Rather surprisingly, we show that no other automatic non-uniform transformation from a weaker model, say from the traditional crash-stop model (with no atomic message delivery), onto an even stronger model than the general-omission one, say the send-omission model, can provide a better time complexity performance in a failure-free execution.

Reference

• LPD-ARTICLE-2007-005
• doi:NA
• View record in Web of Science

Record created on 2007-06-25, modified on 2012-03-21