Randomization Helps to Perform Independent Tasks Reliably

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 languageEnglish (US)
Pages (from-to)11-41
Number of pages31
JournalRandom Structures and Algorithms
Volume24
Issue number1
DOIs
StatePublished - Jan 2004
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Randomization Helps to Perform Independent Tasks Reliably'. Together they form a unique fingerprint.

Cite this