Self-stabilizing Algorithms for Sorting and Heapification
Document Type
Conference Proceeding
Publication Date
4-18-2008
Publication Title
IEEE International Symposium on Parallel and Distributed Processing
Volume
2008
Abstract
We present two space and time efficient asynchronous distributed self-stabilizing algorithms. The first sorts an oriented chain network and the second heapifies a rooted tree network. The time complexity of both solutions is linear — in terms of the nodes (for the chain) and height (for the tree). The chain sorting algorithm uses O(m) bits per process where m represents the number of bits required to store any value in the network. The heapify algorithm needs O(m·D) bits per process where D is the degree of the tree.
Language
english
Repository Citation
Bein, D.,
Datta, A. K.,
Larmore, L. L.
(2008).
Self-stabilizing Algorithms for Sorting and Heapification.
IEEE International Symposium on Parallel and Distributed Processing, 2008
http://dx.doi.org/10.1109/IPDPS.2008.4536327