Technical Report LPCR9301

TR#:LPCR9301
Class:LPCR
Title: A VERSION OF THE \gamma SYNCHRONIZER with LOW MEMORY OVERHEAD.
Authors: L. Shabtay and A. Segall
PDFLPCR9301.pdf
Abstract:

A new message-delaying version of synchronizer \gamma, named, \zeta, is presented. Synchronizer \zeta ensures that original-protocol messages received by a node from nodes in the same cluster are never early, and thus, no buffers for their temporary storage are necessary. Only original-protocol messages on edges leading to nodes of other clusters (external edges) may be early. The n-partition algorithm is introduced to reduce the number of external edges connected to each node, thus reducing the memory overhead of \zeta. For an arbitrary n, this algorithm ensures that the external degree of each node is no more than \Lfloor \Frac{|V|}{N}\Rfloor - 1. The n-partition algorithm increases the time complexity of \zeta to O(N+\Log_K |V|) per pulse. We prove that the tradeoff between memory overhead and time complexity achieved by the n-partition algorithm is optimal.

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/1993/LPCR/LPCR9301), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the LPCR technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin