Technical Report CS0563

TR#:CS0563
Class:CS
Title: Source To Destination Communication in the Presence of Faults
Authors: O. Goldreich, A. Herzberg and Y. Mansour
PDFCS0563.pdf
Abstract: We present a protocol for reliable communication between two processors via an unreliable, and possibly even malicious, communication media. Reliable communication means that all messages are accepted in the same order as sent, with no modifications, omissions, insertions or duplications. Our protocol is resilient to processor crashes (in which the entire memory of the processor is erased), and to duplication and, reordering of messages on the link. The protocol is practical, with applications in both the data link layer and the data transport layer of the ISO model.

Our approach is probabilistic. Namely, for the worst case behavior of the underlying unreliable channel, our protocol guarantees reliable communication with very high probability. The probabilistic approach is justified in light of the impossibility result recently shown [LMF88] for protocols resilient to processor crashes.

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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1989/CS/CS0563), 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 1989
To the main CS technical reports page

Computer science department, Technion
admin