Counterexample to theorems of Cox and Fine
Joseph Y. Halpern
aaai 1996
We consider a system of t synchronous processes that communicate only by sending messages to one another, and that together must perform n independent units of work. Processes may fail by crashing; we want to guarantee that in every execution of the protocol in which at least one process survives, all n units of work will be performed. We consider three parameters: the number of messages sent, the total number of units of work performed (including multiplicities), and time. We present three protocols for solving the problem. All three are work-optimal, doing O(n+t) work. The first has moderate costs in the remaining two parameters, sending O(t√t) messages, and taking O(n+t) time. This protocol can be easily modified to run in any completely asynchronous system equipped with a failure detection mechanism. The second sends only O(t log t) messages, but its running time is large (O(t2(n+t)2n+t)). The third is essentially time-optimal in the (usual) case in which there are no failures, and its time complexity degrades gracefully as the number of failures increases.
Joseph Y. Halpern
aaai 1996
Joseph Y. Halpern, Yoram Moses, et al.
PODC 1990
Ronald Fagin, Yoram Moses, et al.
aaai 1994
D. Dolev, Cynthia Dwork, et al.
IEEE Transactions on Industry Applications