Technical Report CS0624

Authors: B. Awerbuch, O. Goldreich, A. Herzberg
Abstract: We present a quantitative approach to dynamic networks. Dynamic networks, extensively studied in the last decade, are asynchronous networks in which links (and processors) repeatedly fail and recover. Loosely speaking, we quantify the reliability of a link at some event e in an execution by the longest sequence of events preceding e during which the link was operating. Fault tolerant (and efficient) protocols may require connectivity via sufficiently reliable links. We believe that this quantitative concept of reliability will contribute to the modelling of dynamic networks. The benefits of our approach are demonstrated in the development offault tolerant and efficient broadcast protocols for dynamic networks. We present a broadcast protocol which delivers messages from the source to every processor from which there is a sufficiently reliable path to the source. Messages are delivered in the order sent by the source and with no duplications.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion