Self-stabilizing Synchronization Algorithms on Oriented Chains
Document Type
Conference Proceeding
Publication Date
8-30-2008
Publication Title
4th International Conference on Intelligent Computer Communication and Processing
Volume
2008
First page number:
303
Last page number:
306
Abstract
We present a space and (asymptotically) time optimal, uniform, self-stabilizing scheme for a given synchronization problem on asynchronous oriented chains (Algorithm SSDS), that works under an unfair distributed daemon. We use this scheme to solve local mutual exclusion and distributed sorting (where each process holds a single value and the values to be sorted are distinct). Algorithm SSDS can be used to obtain optimal space solutions for other problems such as broadcasting, leader election, mutual exclusion.
Language
english
Repository Citation
Bein, D.,
Datta, A. K.,
Larmore, L. L.
(2008).
Self-stabilizing Synchronization Algorithms on Oriented Chains.
4th International Conference on Intelligent Computer Communication and Processing, 2008
303-306.
http://dx.doi.org/10.1109/ICCP.2008.4648392