Title :
Network synchronization with polylogarithmic overhead
Author :
Awerbuch, Baruch ; Peleg, David
Author_Institution :
Dept. of Math., MIT, Cambridge, MA, USA
Abstract :
The synchronizer is a simulation methodology for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. Previously known synchronizers require each processor in the network to participate in each pulse of the synchronization process. The resulting communication overhead depends linearly on the number n of network nodes. A synchronizer with overhead only polylogarithmically dependent on n is introduced. This synchronizer can also be realized with polylog(n) space. The polylog-overhead synchronizer is based on involving only the relevant portions of the network in the synchronization process
Keywords :
data structures; protocols; switching theory; synchronisation; virtual machines; asynchronous network; communication overhead; data structures; polylogarithmic overhead; protocols; simulation methodology; synchronous network; ARPANET; Algorithm design and analysis; Career development; Clocks; Contracts; Mathematics; Protocols; Pulse generation; Pulse measurements; Synchronization;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89572
