A robust randomized algorithm to perform independent tasks

DOI10.1016/j.jda.2008.03.001zbMath1154.90429OpenAlexW2025553694MaRDI QIDQ1002110

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

randomizationmessage passingdistributed algorithmcrash failureRamanujan graphsscheduling tasks

Mathematics Subject Classification ID

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

Related Items (4)

$$\epsilon $$-Almost Selectors and Their Applications ⋮ Emulating shared-memory do-all algorithms in asynchronous message-passing systems ⋮ Doing-it-all with bounded work and communication ⋮ Randomization helps to perform independent tasks reliably

Cites Work

• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• Tolerating a linear number of faults in networks of bounded degree
• The Do-All problem with Byzantine processor failures
• Performing work in broadcast networks
• Efficient gossip and robust distributed computation
• Performing work with asynchronous processors: Message-delay-sensitive bounds
• Performing Work Efficiently in the Presence of Faults
• Randomization helps to perform independent tasks reliably
• Performing tasks on synchronous restartable message-passing processors
• The complexity of synchronous iterative Do-All with crashes
• Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups
• Time-optimal message-efficient work performance in the presence of faults
• Probability and Computing

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