On the Strongest Message Adversary for Consensus in Directed Dynamic Networks

摘要

Inspired by the successful chase for the weakest failure detector in asynchronous message passing systems with crash failures and surprising relations to synchronous directed dynamic networks with message adversaries established by Raynal and Stainer [PODCT3], we introduce the concept of message adversary simulations and use it for defining a notion for strongest message adversary for solving distributed computing problems like consensus and fc-set agreement. We prove that every message adversary that admits all graph sequences consisting of perpetual star graphs and is strong enough for solving multi-valued consensus is a strongest one. We elaborate on seemingly paradoxical consequences of our results, which also shed some light on the fundamental difference between crash-prone asynchronous systems with failure detectors and synchronous dynamic networks with message adversaries.