A robust randomized algorithm to perform independent tasks

Bogdan S. Chlebus; Leszek Ga̧sieniec; Dariusz R. Kowalski; Alex A. Shvartsman

doi:10.1016/j.jda.2008.03.001

A robust randomized algorithm to perform independent tasks

Research output: Contribution to journal › Article › peer-review

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(log² 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	https://doi.org/10.1016/j.jda.2008.03.001 https://doi.org/10.1016/j.jda.2008.03.001
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

Access to Document

https://dblp.org/db/journals/jda/jda6.html#ChlebusGKS08

Cite this

@article{283703fa4f284ecf89558cdd4b747bf1,

title = "A robust randomized algorithm to perform independent tasks",

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.",

keywords = "Crash failure, Distributed algorithm, Message passing, Ramanujan graphs, Randomization, Scheduling tasks",

author = "Chlebus, \{Bogdan S.\} and Leszek G{\c a}sieniec and Kowalski, \{Dariusz R.\} and Shvartsman, \{Alex A.\}",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2008",

doi = "10.1016/j.jda.2008.03.001",

language = "English (US)",

volume = "6",

pages = "651--665",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - A robust randomized algorithm to perform independent tasks

AU - Chlebus, Bogdan S.

AU - Ga̧sieniec, Leszek

AU - Kowalski, Dariusz R.

AU - Shvartsman, Alex A.

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Crash failure

KW - Distributed algorithm

KW - Message passing

KW - Ramanujan graphs

KW - Randomization

KW - Scheduling tasks

UR - https://www.scopus.com/pages/publications/54449084777

UR - https://www.scopus.com/pages/publications/54449084777#tab=citedBy

U2 - 10.1016/j.jda.2008.03.001

DO - 10.1016/j.jda.2008.03.001

M3 - Article

AN - SCOPUS:54449084777

SN - 1570-8667

VL - 6

SP - 651

EP - 665

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 4

M1 - 4

ER -

A robust randomized algorithm to perform independent tasks

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this