Mohsen Ghaffari the Winner of the 2017 Principles of Distributed Computing Doctoral Dissertation Award!

The winner of the 2017 Principles of Distributed Computing Doctoral
Dissertation Award is Dr. Moshen Ghaffari, for his dissertation Improved
Distributed Algorithms for Fundamental Graph Problems, written under the
supervision of Prof. Nancy Lynch at the Massachusetts Institute of
Technology.

Ghaffari’s thesis represents an extraordinary study of network algorithms
which is, at the same time, both deep and extensive. Many of the results
included in this thesis (5, to be precise) have already been awarded “Best
Student Paper” award or “Best Paper” award (and sometimes both) in top-notch
conferences. The number of publications produced by Ghaffari while working
on his thesis is also staggering (over 35 papers!): the thesis covers only a
small part of his work. Most important, Ghaffari made a very significant
contribution to the Theory of Network Algorithms, particularly to randomized
network algorithms.

Specifically, the thesis contains three parts. In the first part, a new
randomized algorithm for the Maximal Independent Set (MIS) problem is
developed. The algorithm is simple and local in a strong sense: the
termination time of a node depends only the coin-tosses within distance 2.
This algorithm improves on all previous results and thus leads to improved
time complexity in the many applications that use MIS as a building block.
In the second part, Ghaffari presents results concerning vertex- and
edge-connectivity in graphs, with applications to different problems such as
Connected Dominated Set and Minimum Spanning Tree computation. And in the
last part of the thesis, following classical packet routing results,
scheduling multiple network tasks concurrently is considered. It is shown
that in fact, there may be an unavoidable logarithmic gap between the case
of packet routing and general tasks, but on the positive side, we never need
to pay more than a single logarithmic factor (beyond the
“congestion+dilation” lower bound) to schedule multiple tasks.


The award. The award is sponsored jointly by the ACM Symposium on Principles
of Distributed Computing (PODC) and the EATCS Symposium on Distributed
Computing (DISC). This award is presented annually, with the presentation
taking place alternately at PODC and DISC. The 2017 award will be presented
at PODC 2017, to be held in Washington DC, USA.
The 2016 Principles of Distributed Computing Doctoral Dissertation Award
Committee:
• Cyril Gavoille (LaBRI, U. Bordeaux)
• Boaz Patt-Shamir (Chair, Tel Aviv U.)
• Michel Raynal (IRISA, U. Rennes 1)
• Gadi Taubenfeld (IDC)