The complexity of synchronous iterative Do-All with crashes

DOI10.1007/S00446-003-0099-3zbMath1448.68100OpenAlexW1966796751MaRDI QIDQ5138503

Alexander Russell, Chryssis Georgiou, Alexander A. Schwarzmann

Publication date: 4 December 2020

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-003-0099-3

zbMATH Keywords

lower boundsfault-tolerancedistributed algorithmswork complexity

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items (6)

Doing-it-all with bounded work and communication ⋮ The Do-All problem with Byzantine processor failures ⋮ A robust randomized algorithm to perform independent tasks ⋮ Algebraic topology and distributed computing ⋮ Efficient gossip and robust distributed computation ⋮ Online parallel scheduling of non-uniform tasks: trading failures for energy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic load balancing with group communication
• Achieving optimal CRCW PRAM fault-tolerance
• Efficient parallel algorithms can be made robust
• Work-Optimal Asynchronous Algorithms for Shared Memory Parallel Computers
• On the Complexity of Certified Write-All Algorithms
• Algorithms for the Certified Write-All Problem
• Parallel Algorithms with Processor Failures and Delays
• Performing tasks on synchronous restartable message-passing processors
• An algorithm for the asynchronous Write-All problem based on process collision
• Performing work efficiently in the presence of faults
• Time-optimal message-efficient work performance in the presence of faults
• Parallelism in random access machines

This page was built for publication: The complexity of synchronous iterative Do-All with crashes