Abstract
This paper is about algorithms that schedule tasks to be performed in a distributed failure-prone environment, when processors communicate by message-passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly-bounded adversaries may fail up to a constant fraction of the processors. Weakly-adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure-prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point-to-point messages. A randomized algorithm is developed, that attains both script O sign(n log*n) expected work and script O sign(n log*n) expected communication, against weakly-adaptive linearly-bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly-adaptive linearly-bounded adversaries, which has to be Ω(n log n/log log n) in terms of work.
Original language | English (US) |
---|---|
Pages (from-to) | 11-41 |
Number of pages | 31 |
Journal | Random Structures and Algorithms |
Volume | 24 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2004 |
Externally published | Yes |
Keywords
- Adaptive adversary
- Distributed algorithm
- Independent tasks
- Load balancing
- Lower bound
- Message passing: crash failures
- Randomized algorithm
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics