Chasing the Weakest System Model for Implementing Ω and Consensus

doi:10.1109/TDSC.2008.24

Chasing the Weakest System Model for Implementing Ω and Consensus

2009-10-01

19

PRE

AI

DOI：10.1109/TDSC.2008.24

Original

Original request for help

Save

Abstract

En 中文

Aguilera et al. and Malkhi et al. presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Omega can be implemented, and thus, consensus can also be solved. The former model assumes unicast steps and at least one correct process with f outgoing eventually timely links, whereas the latter assumes broadcast steps and at least one correct process with f bidirectional but moving eventually timely links. Consequently, those models are incomparable. In this paper, we show that Omega can also be implemented in a system with at least one process with f outgoing moving eventually timely links, assuming either unicast or broadcast steps. It seems to be the weakest system model that allows to solve consensus via Omega-based algorithms known so far. We also provide matching lower bounds for the communication complexity of Omega in this model, which are based on an interesting stabilization property of infinite runs. Those results reveal a fairly high price to be paid for this further relaxation of synchrony properties.

Keywords:

Distributed systems

failure detectors

fault-tolerant distributed consensus

system modeling

partial synchrony

Chasing the Weakest System Model for Implementing Ω and Consensus

Abstract

AI Summary

Journal

Organization