An Optimal Synchronizer for the Hypercube

The synchronizer is a simulation methodology introduced by Awerbuch [J. Assoc. Comput. Math., 32 (1985), pp. 804–823] for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. In this paper a novel technique for constructing network synchronizers is presented. This technique is developed from some basic relationships between synchronizers and the structure of a t-spanning subgraph over the network. As a special result, a synchronizer for the hypercube with optimal time and communication complexities is obtained.