ComputingComputer ScienceComputer SystemsDistributed SystemsFault-tolerant ComputingFault-tolerant SystemsDistributed ComputingFault Tolerance DesignReliable Distributed SystemsReliable System DesignFault Tolerance In MultiprocessorsFault Tolerant AlgorithmsFault-tolerant Computation ModelsFault-tolerant Distributed AlgorithmsFault-tolerant Distributed SystemsPaxosProcessor Systems
Asynchronous algorithms for implementing a fault-tolerant distributed system, which can make progress despite the failure of any F processors, require 2F + 1 processors. Cheap Paxos, a variant of the Paxos algorithm, guarantees liveness under the additional assumption that the set of nonfaulty processors does not "jump around" too fast, but uses only F + 1 main processors that actually execute the system and F auxiliary processors that are used only to handle the failure of a main processor. The auxiliary processors take part in reconfiguring the system to remove the failed processor, after which they can remain idle until another main processor fails.
8
Leslie Lamport · ACM Transactions on Computer Systems · 1998 · 2.7K citations · Full text
Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer · Journal of the ACM · 1988 · 1.9K citations · Full text
Replication in the harp file system
Barbara Liskov, Sanjay Ghemawat, Robert Gruber et al. · 1991 · 274 citations · Full text