CS seminar

You are here

Self Stabilization and Mutual Exclusion

In 1974 Dijkstra introduced the notion of self-stabilizing algorithms, and presented three such algorithms for the problem of mutual exclusion on a ring of processors. The third algorithm is the most interesting of these three, but is rather non intuitive. In 1986 Dijkstra presented a proof of its correctness, but the question of determining its worst case complexity -- that is, providing an upper bound on the number of moves of this algorithm until it stabilizes -- remained open. We solved this
question, and proved an upper bound of $O(n^2)$ ($n$ being the size of the ring) for this algorithm's complexity. This complexity applies to a centralized as well as to a distributed scheduler.

Mordechai Shalom, holds a B.A. degree in Architecture from ITU, Technical University of Istanbul, from which he graduated at 1981. He completed his studies towards M.Sc. degree at 1986 in the Faculty of Computer Science, Technion, from which he received his Ph.D. degree at 2006. He currently serves as Lecturer in the Tel Hai Academic College and as Adjunct Lecturer at the Technion. His research
interests are Optimization Problems in Optical Networks, Distributed Algorithms Approximation Algorithms for Graph Theoretic problems.