Seminar on March 13, 2015



Distributed Leader Election


Mordechai Shalom,

(Tel Hai College & Boğaziçi University



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(n2) (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.


The talk is self-contained and does not assume a priori knowledge of Distributed Systems.


Short Bio: 

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. Since then, he has been serving as Senior Lecturer in the Tel Hai Academic College and as Adjunct Lecturer at the Technion. He is currently in Sabbatical leave with the Department of Industrial Engineering, Bogazici University. His research interests are Approximation Algorithms, Online Algorithms, Graph Algorithms and Distributed Algorithms.


All interested are cordially invited.  


DATE: March 13, 2015 

TIME:  Friday, 15:00-16:00