A robust randomized algorithm to perform independent tasks

DOI10.1016/J.JDA.2008.03.001MaRDI QIDQ1002110zbMATH OpenOpenAlexFDO

Authors Bogdan S. Chlebus, Leszek Gaşsieniec, Dariusz R. Kowalski, Alexander A. Schwarzmann

Publication date 23 February 2009

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.03.001

zbMATH Keywords

randomizationdistributed algorithmcrash failureRamanujan graphsmessage passingscheduling tasks

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Doing-it-all with bounded work and communication
• Randomization helps to perform independent tasks reliably
• scientific article; zbMATH DE number 2013838
• The complexity of synchronous iterative do-all with crashes
• scientific article; zbMATH DE number 2006650

Cites work

• scientific article; zbMATH DE number 1306905 (Why is no real title available?)
• scientific article; zbMATH DE number 1979510 (Why is no real title available?)
• Efficient gossip and robust distributed computation
• Performing Work Efficiently in the Presence of Faults
• Performing tasks on synchronous restartable message-passing processors
• Performing work in broadcast networks
• Performing work with asynchronous processors: Message-delay-sensitive bounds
• Probability and Computing
• Ramanujan graphs
• Randomization helps to perform independent tasks reliably
• The Do-All problem with Byzantine processor failures
• The complexity of synchronous iterative do-all with crashes
• Time-optimal message-efficient work performance in the presence of faults
• Tolerating a linear number of faults in networks of bounded degree
• Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups

Cited in

(8)

• The complexity of synchronous iterative do-all with crashes
• \(\varepsilon \)-almost selectors and their applications
• Randomization helps to perform independent tasks reliably
• scientific article; zbMATH DE number 2013838 (Why is no real title available?)
• scientific article; zbMATH DE number 2006650 (Why is no real title available?)
• Work-competitive scheduling on task dependency graphs
• Emulating shared-memory do-all algorithms in asynchronous message-passing systems
• Doing-it-all with bounded work and communication

This page was built for publication: A robust randomized algorithm to perform independent tasks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1002110)