@inproceedings{aa4e84efb7874681a13ea0141cf5f972,
title = "The complexity of synchronous iterative do-all with crashes",
abstract = "Do-All is the problem of performing N tasks in a distributed system of P failure-prone processors [8]. Many distributed and parallel algorithms have been developed for this problem and several algorithm simulations have been developed by iterating Do-All algorithms. The efficiency of the solutions for Do-All is measured in terms of work complexity where all processing steps taken by the processors are counted. We present the first non-trivial lower bounds for Do-All that capture the dependence of work on N, P and f, the number of processor crashes. For the model of computation where processors are able to make perfect load-balancing decisions locally, we also present matching upper bounds. We define the r-iterative Do-All problem that abstracts the repeated use of Do-All such as found in algorithm simulations. Our f-sensitive analysis enables us to derive a tight bound for r-iterative Do-All work (that is stronger than the r-fold work complexity of a single Do-All). Our approach that models perfect load-balancing allows for the analysis of specific algorithms to be divided into two parts: (i) the analysis of the cost of tolerating failures while performing work, and (ii) the analysis of the cost of implementing load-balancing. We demonstrate the utility and generality of this approach by improving the analysis of two known efficient algorithms. Finally we present a new upper bound on simulations of synchronous shared-memory algorithms on crash-prone processors.",
author = "Chryssis Georgiou and Alexander Russell and Shvartsman, {Alex A.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 15th International Conference on DIStributed Computing, DISC 2001 ; Conference date: 03-10-2001 Through 05-10-2001",
year = "2001",
doi = "10.1007/3-540-45414-4_11",
language = "English (US)",
isbn = "3540426051",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "151--165",
editor = "Jennifer Welch",
booktitle = "Distributed Computing - 15th International Conference, DISC 2001, Proceedings",
}