Chasing the Weakest System Model for Implementing Ω and Consensus

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