Ordered and delayed adversaries and how to work against them on a shared channel

摘要

An execution of a distributed algorithm is often seen as a game between the algorithm and a conceptual adversary causing specific distractions to the computation. In this work we define a class of ordered adaptive adversaries, which cause distractions-in particular crashes-online according to some partial order of the participating stations, which is fixed by the adversary before the execution. We distinguish: Linearly-Ordered adversary, restricted by some pre-defined linear order of (potentially) crashing stations; Anti-Chain-Ordered adversary, previously known as the Weakly-Adaptive adversary, which is restricted by some pre-defined set of crash-prone stations (it can be seen as an ordered adversary with the order being an anti-chain, i.e., a collection of incomparable elements, consisting of these stations); k-Thick-Ordered adversary restricted by partial orders of stations with a maximum anti-chain of size k. We initiate a study of how they affect performance of algorithms. For this purpose, we focus on the well-known Do-All problem of performing t tasks by p synchronous crash-prone stations communicating on a shared channel. The channel restricts communication by the fact that no message is delivered to the operational stations if more than one station transmits at the same time. The question addressed in this work is how the ordered adversaries controlling crashes of stations influence work performance, defined as the total number of available processor steps during the whole execution and introduced by Kanellakis and Shvartsman (Distrib Comput 5(4):201-217, 1992) in the context of Write-All algorithms. The first presented algorithm solves the Do-All problem with work O proved in Chlebus et al. (Distrib Comput 18(6):435-451, 2006). Another algorithm is developed against the Weakly-Adaptive adversary. Work done by this algorithm is O(t+pt+pminp/(p-f),tlogp), which is close to the lower bound omega(t+pt+pminp/(p-f),t) proved in [11] and answers the open questions posed there. We generalize this result to the class of k-Thick-Ordered adversaries, in which case the work of the algorithm is bounded by O(t+pt+pminp/(p-f),k,tlogp). We complement this result by proving the almost matching lower bound omega(t+pt+pminp/(p-f),k,t). Independently from the results for the ordered adversaries, we consider a class of delayed adaptive adversaries, which could see random choices with some delay. We present an algorithm that works efficiently against the 1-RD adversary, which could see random choices of stations with one round delay, achieving close to optimal O(t+ptlog2p) work complexity. This shows that restricting the adversary by not allowing it to react on random decisions immediately makes it significantly weaker, in the sense that there is an algorithm achieving (almost) optimal work performance. We generalize this result to the class of k-Thick-Ordered adversaries, in which case the work of the algorithm is bounded by O(t + p root t + p min {p/(p - f), k, t} log p).