73/2006 : Brief Announcement: Chasing the Weakest System Model for Implementing Omega and Consensus

RR Number

73/2006

Conference

Eighth International Symposium on Stabilization, Safety, and Security of Distributed Systems (formerly Symposium on Self-stabilizing Systems) (SSS 2006) November 17th-19th, 2006, Dallas, Texas, USA

Author(s)

Martin Hutle, Dahlia Malkhi, Ulrich Schmid, Lidong Zhou

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 Omega can be implemented and thus also consensus can be solved. The former model assumes 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 the further relaxation of synchrony properties.

Bibtex

@inproceedings{HMSZ06:SSS,
  author =       "Martin Hutle and Dahlia Malkhi and Ulrich Schmid and Lidong Zhou",
  title =        "Brief Announcement: Chasing the Weakest System Model for Implementing Omega and Consensus",
  booktitle =      "Proceedings Eighth International Symposium on Stabilization, Safety, and Security of Distributed Systems (formerly Symposium on Self-stabilizing Systems) (SSS 2006)",   
  location = "Dallas, Texas, USA",
  year =         "2006",
  month =        "Nov."
}

Download

Get HMSZ06.pdf - Adobe PDF-format, (50.56 KB; posted at September 08 2006)