Seminar on May 8, 2015



Distributed Minimum Spanning Tree


Mordechai Shalom,

(Tel Hai College & Boğaziçi University



In a distributed network, many tasks become easier if a spanning tree of the network is provided. In networks such as ad-hoc networks in which the topology changes dynamically, the spanning tree has to be found dynamically by the processors of the networks.

We consider the asynchronous message passing model in which processors can communicate only by sending and receiving messages, and there is no upper bound on the reception time of a message. However, we assume that the network is reliable, i.e. every message sent will actually be received. We also assume that the messages sent on the same link arrive in FIFO order.

We present the well-known algorithm by Gallager, Humblet and Spira that finds a Minimum Spanning Tree with efficient message complexity.


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:  May 8, 2015 

TIME:  Friday, 15:00-16:00