@article{hutle2009chasing,
author = {Hutle, Martin and Malkhi, Dahlia and Schmid, Ulrich and Zhou, Lidong},
title = {Chasing the Weakest System Model for Implementing $Omega$ and Consensus},
year = {2009},
month = {January},
abstract = {Aguilera et al. and Malkhi et al. have presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Ω can be implemented and thus also consensus can 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 Ω 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 Ω-based algorithms known so far. We also provide matching lower bounds for the communication complexity of Ω 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 the further relaxation of synchrony properties.},
publisher = {IEEE Computer Society},
url = {http://approjects.co.za/?big=en-us/research/publication/chasing-the-weakest-system-model-for-implementing-omega-and-consensus/},
journal = {IEEE Transactions on Dependable and Secure Computing (TDSC)},
edition = {IEEE Transactions on Dependable and Secure Computing (TDSC)},
}