1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97)
A High Performance Dynamic Token-Based Distributed Synchronization Algorithm
Taipei, Taiwan
December 18-December 20
ISBN: 0-8186-8259-0
In this paper we propose a new dynamic token-based distributed synchronization algorithm that utilizes a new technique called optimistic broadcasting (optcasting) to improve efficiency. Briefly, an optcast message is a reliable unicast one that can also be heard by nodes other than its designated destination. Our algorithm manages pending token requesters by a distributed queue, and optcasts a direction towards the current queue end to help new requesters finding the queue end more quickly. Simulated experimental results indicate that our optcast algorithm outperforms the already fast Chang-Singhal-Liu (CSL) algorithm by up to 36%, especially for large systems of many processor nodes and under high synchronization loads. In addition, optcasting is highly robust and resistant to message loss, retaining at least 63% coverage even when the message loss rate approaches 100%.
Index Terms:
distributed synchronization, optimistic broadcasting, token passing, path compression, mutual exclusion.
Citation:
Alexander I-Chi Lai, Chin-Laung Lei, "A High Performance Dynamic Token-Based Distributed Synchronization Algorithm," ispan, pp.150, 1997 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '97), 1997
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||