The Failure Discovery problem |
| |
Authors: | Vassos Hadzilacos Joseph Y. Halpern |
| |
Affiliation: | (1) Computer Systems Research Institute, University of Toronto, 6 King's College Road, M5S 1A1 Toronto, Ontario, Canada;(2) Department K53/802, IBM Almaden Research Center, 650 Harry Road, 95120-6099 San Jose, CA, USA |
| |
Abstract: | We define a simple variant of the Byzantine agreement (BA) problem, called the Failure Discovery (FD) problem, that roughly speaking, amounts to reaching BA provided that no failures are discovered. We show how a protocol for FD can be extended to one for BA, with no message overhead in the failure-free runs. We also show that, for so-calledbenign failures, if the FD protocol satisfies an additional property, the message-preserving extension to a BA protocol can be accomplished with minimal time overhead in the failure-free runs. Our results show that FD is a useful building block for BA; indeed, it has been used in this way in a companion paper (Hadzilacos and Halpern, 1993).The work of V. Hadzilacos was supported, in part, by a grant from the Natural Sciences and Engineering Research Council of Canada. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|