Abstract
The Do-All problem is about scheduling t similar and independent tasks to be performed by p processors prone to crashes. We assume that the distributed system is synchronous with processors communicating by message passing. Crashes are determined by a fully adaptive adversary that is restricted only by an upper bound f on the number of crashes. The complexity of algorithms is measured by work and communication, where work is defined as the number of available-processor steps, and communication as the number of point-to-point messages. We develop a randomized algorithm with W = O (t + p ṡ frac(log2 p, log log p)) expected work and O ((frac(p, p - f))3.4 W) expected communication, for an arbitrary number f < p of crashes.
Original language | English (US) |
---|---|
Article number | 4 |
Pages (from-to) | 651-665 |
Number of pages | 15 |
Journal | Journal of Discrete Algorithms |
Volume | 6 |
Issue number | 4 |
DOIs | |
State | Published - 2008 |
Externally published | Yes |
Keywords
- Crash failure
- Distributed algorithm
- Message passing
- Ramanujan graphs
- Randomization
- Scheduling tasks
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics