The Complexity of Distributed Cooperation in the Presence of Failures.
Chryssis Georgiou, Alexander C. Russell, Alexander A. Shvartsman · 2000
Abstract. We consider the problem of performing N tasks in a distributed system of P processors that are subject to failures. An optimal solution would have the system perform Θ(N) tasks, however extant results show that this is impossible (when N = P) in the presence of an omniscient failure-inducing adversary. In this work we present complexity results for this problem for the case when the processors are assisted by a perfect load-balancing oracle in an attempt to foil the adversary. We generalize several existing results for this setting and we present new bounds for this problem that shed light on the behavior of deterministic distributed cooperation algorithms for the cases when the adversary imposes comparatively few failures. When a solution for the cooperation problem is implemented using a global load-balancing strategy, our results can be used to explain the work complexity of the solution. In particular, if the complexity of implementing the load-balancing oracle is known for a given model of computation, then our results can be directly translated into complexity results for that model.