Efficient parallel algorithms can be made robust

DOI10.1007/BF02277667zbMath0744.68060MaRDI QIDQ1189859

Paris C. Kanellakis, Alexander A. Schwarzmann

Publication date: 27 September 1992

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

zbMATH Keywords

fault tolerancelower boundsrobust algorithmsCRCW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Related Items

Locality-preserving hash functions for general purpose parallel computation, Performing work in broadcast networks, Fault-tolerant sequential scan, Efficient parallel computing with memory faults, Efficient execution of nondeterministic parallel programs on asynchronous systems, Fast deterministic simulation of computations on faulty parallel machines, Performing tasks on synchronous restartable message-passing processors, An algorithm for the asynchronous Write-All problem based on process collision, Hundreds of impossibility results for distributed computing, The complexity of synchronous iterative Do-All with crashes, Achieving optimal CRCW PRAM fault-tolerance, The assignment problem, Reliable computations on faulty EREW PRAM, Doing-it-all with bounded work and communication, Ordered and delayed adversaries and how to work against them on a shared channel, A tight analysis and near-optimal instances of the algorithm of Anderson and Woll, Efficient gossip and robust distributed computation

Cites Work

• Unnamed Item
• Unnamed Item
• How to emulate shared memory
• A lower bound for the time to assure interactive consistency
• Achieving optimal CRCW PRAM fault-tolerance
• The expected advantage of asynchrony
• A Robust Sorting Network
• Probabilistic analysis of a network resource allocation algorithm
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus
• Constructing two-writer atomic registers
• Reaching Agreement in the Presence of Faults
• Local management of a global resource in a communication network
• Optimal bounds for decision problems on the CRCW PRAM
• Efficient parallel algorithms on restartable fail-stop processors
• Parallelism in random access machines