Performing work efficiently in the presence of faults
| dc.creator | Dwork, Cynthia | |
| dc.creator | Halpern, Joseph Y. | |
| dc.creator | Waarts, O. | |
| dc.date | 2000-06-02 | |
| dc.date.accessioned | 2026-07-07T03:16:16Z | |
| dc.date.available | 2026-07-07T03:16:16Z | |
| dc.description | 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\sqrt{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 (exponential in n and 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0006008 | |
| dc.identifier | http://arxiv.org/abs/cs/0006008 | |
| dc.identifier | SIAM Journal on Computing 27:5, 1998, pp. 1457--1491 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30285 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | C.2.4 | |
| dc.title | Performing work efficiently in the presence of faults | |
| dc.type | text |