Technical Report CS0706

Authors: L. Shabtay and A. Segall
PDF - RevisedCS0706.revised.pdf
Abstract: Correctness of synchronizers is examined: a synchronizer is said to be correct, if each execution of a protocol created by combining it with a synchronous protocol, is equivalent to some execution of the original (synchronous) protocol. Two families of synchronizers are introduced, {\em passive} synchronizers and {\em active} synchronizers. Passive synchronizers do not change the original synchronous protocol and only add a synchronization protocol for synchronizing it, while active synchronizers may change the original protocol code, messages, etc. The {\em timely} property, which is sufficient and necessary for correctness of passive synchronizers, and the {\em matching} property, which is sufficient and necessary for correctness of active synchronizers, are introduced. Lower bounds are set for communication and time complexity of correct passive synchronizers, thus showing that active synchronizers are necessary for low complexities, while retaining the correctness of the synchronizers. Two types of active synchronizers are introduced: {\em message-monitoring} synchronizers, in which synchronizer code is performed as a result of original-protocol message reception and transmission, and {\em variable-duplicating} synchronizers, which duplicate all original-protocol variables at each node. A message-monitoring correct synchronizer with low communication and time complexities is presented. A method is introduced for creating variable-duplicating correct synchronizers from passive incorrect synchronizers, with identical communication and time complexities. One more family of active synchronizers is examined: {\em message-delaying} synchronizers. In message-delaying synchronizers, early messages are saved and treated later. We show that implementation of such synchronizers, using certain passive synchronizers, is not straightforward, since in these cases, nodes may not always know which messages are early and which are timely. Solutions for this problem are suggested.
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 1991
To the main CS technical reports page

Computer science department, Technion