| TR#: | CS0650 |
| Class: | CS |
| Title: | EARLY TERMINATIPN IN UNRELIABLE COMMUNICATION NETWORKS |
| Authors: | Amir Herzberg |
| CS0650.pdf | |
| Abstract: | We propose a simple refinement of time complexity, which evaluates the time required for 'typical' executions as well as for 'worst case' executions. This refined measure is particularly useful for analyzing fault-tolerant protocols, which use bounds for the transmission delay. The refined time complexity is a function of both the actual delay over 'most' links, (, and the bound on the delay, B. Usually ( «B. Protocols whose time complexity depends on B as little as possible are called early terminating. We present an early terminating protocol for performing queries in unreliable networks. This protocol may be used to locate the processor containing a given user, in order to communicate with this user. The protocol is resilient both to constantly changing topology and to arbitrary, possibly malicious, processor faults. Previous early terminating solutions assumed that the topology changes eventually stabilize, and also did not allow processor faults. |
| Copyright | The 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/1990/CS/CS0650), 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