A robust randomized algorithm to perform independent tasks

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

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

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

randomization; message passing; distributed algorithm; crash failure; Ramanujan graphs; scheduling tasks

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

Related Items

Randomization helps to perform independent tasks reliably, Emulating shared-memory do-all algorithms in asynchronous message-passing systems

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