Transformations of self-stabilizing algorithms

Issue title: Self-Stabilizing Systems, Part 1

Article type: Research Article

Authors: Ioannidou, Kleoni

Affiliations: Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, ON, Canada M5S 3G4 E-mail: [email protected]

Abstract: In this paper, we are interested in transformations of self-stabilizing algorithms from one model to another that preserve stabilization. We propose an easy technique for proving correctness of a natural class of transformations of self-stabilizing algorithms from any model to any other. We present a new transformation of self-stabilizing algorithms from a message passing model to a shared memory model with a finite number of registers of bounded size and processors of bounded memory and prove it correct using our technique. This transformation is not wait-free, but we prove that no such transformation can be wait-free. For our transformation, we use a new self-stabilizing token-passing algorithm for the shared memory model. This algorithm stabilizes in O(nlog 2n) rounds, which improves existing algorithms.

Journal: Journal of High Speed Networks, vol. 14, no. 1, pp. 85-105, 2005