Development of Self-Stabilizing Distributed Algorithms using Transformation: Case Studies
Hirotsugu Kakugawa, Masaaki Mizuno, Mikhail Nesterenko · McGill-Queen's University Press eBooks · 1997
Many self-stabilizing (SS) algorithms have been developed for the serial model, which has much stronger assumptions on the execution environments than common distributed ( i. e ., message-passing) systems provide. It seems that many of the serial model algorithms were developed for theoretical interest rather than practical application. In contrast, SS distributed model algorithms, which actually run in a real distributed computing environment, are more difficult to develop and verify than those for the serial model. In an earlier paper, we presented a transformation algorithm that transforms SS serial model algorithms to equivalent distributed model algorithms. The transformation enables us to execute many existing SS serial model algorithms in a distributed environment. More importantly, the transformation also helps us develop new and more practical algorithms starting with the serial model. In this way, the task of developing SS distributed model algorithms is significantly simplified. This paper demonstrates, through case studies, the effectiveness of the transformation to develop new SS distributed algorithms. We present SS versions of lock based distributed mutual exclusion (DMX) algorithms and a leader election algorithm for the serial model. For one of the DMX algorithms, we give a correctness proof and compare message complexity of its transformed algorithm to that of an algorithm developed from scratch; both algorithms exhibit the same asymptotic complexity.