Research indexJournal article
Synchronization Algorithms on Oriented Chains
Bein, Datta, Larmore
SHILAP Revista de lepidopterología1 Jan 2008Open access
NobleIDark:/48914/w1/20260524/3A9FFA05DOI10.5281/zenodo.12719812
Journal articleOpen access
Synchronization Algorithms on Oriented Chains
Bein, Datta, Larmore · SHILAP Revista de lepidopterología · 2008
NobleIDark:/48914/w1/20260524/3A9FFA05DOI10.5281/zenodo.12719812
Abstract
We present a space- and time-optimal self-stabilizing algorithm, SSDS, for a given synchronization problem on asynchronous oriented chains. SSDS is uniform and works under the unfair distributed daemon. From SSDS we derive solutions for the local mutual exclusion and distributed sorting. Algorithm SSDS can also be used to obtain optimal space solutions for other problems such as broadcasting, leader election, and mutual exclusion.