FAULT-TOLERANT ATOMIC BROADCAST METHODS

摘要

FAULT-TOLERANT ATOMIC BROADCAST METHODS of the Invention A method for reliably broadcasting information in a point-to-point network of processors in the presence of component faults provided that the network remains connnected using only an exchange of messages. The method possesses the properties (1) that every message broadcast by a fault-free processor is accepted exactly once by all fault-free processors within a bounded time, (2) that every message broadcast is either accepted by all faultfree processors or none of them, and (3) that all messages accepted by fault-free processors are accepted in the same order by all those processors. The method is based on a diffusion technique for broadcasting information and on special message validity tests for tolerating any number of component failures up to network partitioning or successful forgery.