Thomas M. Cover
IEEE Trans. Inf. Theory
The paper deals with the problem of managing a fault-tolerant critical section in a completely asynchronous distributed network. The existence of a solution to this problem should be contrasted with a basic result of Fischer, Lynch, and Paterson, proving that in a completely asynchronous network, "nontrivial agreement" cannot be achieved even when only a single "benign" processor failure is possible. We present solutions to several versions of the critical section problem in this model. Denote by t the maximum number of possible faulty processors. Processors are allowed to fail while in the critical section, and therefore the critical section must have at least t + 1 slots. In the case where the slots are identical we present two algorithms which require t + 1 slots. The first is very simple, but requires every non-faulty processor to use the critical section infinitely often. The second solution allows non-faulty processors to quit. For distinct slots we present an algorithm that requires 2t + 1 slots. © 1991.
Thomas M. Cover
IEEE Trans. Inf. Theory
Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007