Efficient parallel algorithms can be made robust

DOI10.1007/BF02277667MaRDI QIDQ1189859zbMATH OpenFDO

Authors Paris C. Kanellakis, Alexander A. Schwarzmann

Publication date 27 September 1992

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02277667

zbMATH Keywords

lower boundsfault tolerancerobust 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)

Recommendations

• Parallel Algorithms with Processor Failures and Delays
• Reliable computations on faulty EREW PRAM
• scientific article; zbMATH DE number 794259
• scientific article; zbMATH DE number 1033646
• An efficient write-all algorithm for fail-stop PRAM without initialized memory

Cites work

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

Cited in

(20)

• Achieving optimal CRCW PRAM fault-tolerance
• An efficient write-all algorithm for fail-stop PRAM without initialized memory
• Robust parallel computations through randomization
• Fault-tolerant sequential scan
• A tight analysis and near-optimal instances of the algorithm of Anderson and Woll
• Ordered and delayed adversaries and how to work against them on a shared channel
• Hundreds of impossibility results for distributed computing
• The complexity of synchronous iterative do-all with crashes
• Efficient execution of nondeterministic parallel programs on asynchronous systems
• An algorithm for the asynchronous \textit{Write-All} problem based on process collision
• Performing work in broadcast networks
• The assignment problem
• Efficient gossip and robust distributed computation
• scientific article; zbMATH DE number 599176 (Why is no real title available?)
• Fast deterministic simulation of computations on faulty parallel machines
• Efficient parallel computing with memory faults
• Locality-preserving hash functions for general purpose parallel computation
• Reliable computations on faulty EREW PRAM
• Performing tasks on synchronous restartable message-passing processors
• Doing-it-all with bounded work and communication

This page was built for publication: Efficient parallel algorithms can be made robust

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