Chasing the Weakest System Model for Implementing Omega and Consensus (Brief Announcement)

The chase for the weakest system model that allows to solve consensus has long been an active branch of research in distributed algorithms. To circumvent the FLP impossibility in asynchronous systems, many models in between synchrony and asynchrony have been proposed over the years. Of specific interest is the chase for the weakest system model that allows the implementation of an eventual leader oracle Ω, and thus also enables consensus to be solved. Recently, Aguilera et al. [ADGFT04] and Malkhi et al. [MOZ05] presented two system models which are weaker than all previously proposed models where Ω can be implemented. The former model assumes unicast steps and at least one correct process with f outgoing eventually timely links. The latter assumes broadcast steps and at least one correct process with f bidirectional but moving eventually timely links. Consequently, those models are incomparable. Our main result in the full paper [HMSZ05:TR] shows that Ω can be implemented in a system with at least one process with f outgoing moving eventually timely links, assuming either unicast or broadcast steps. Our construction seems to solve consensus (via Ω) in the weakest system model known so far.