Yesterday I had the pleasure of serving as a co-examiner in Jochen Seidel's PhD defence at ETH Zurich.
Jochen's thesis (supervised by +roger wattenhofer
) studies a question related to the foundations of distributed computing that many people have been ignoring so far: what can be computed in anonymous networks
(i.e., networks without unique node identifiers) with the help of randomness
At first, this may seem like a somewhat strange setting: if we have a source of randomness, the nodes can generate random identifiers that are unique w.h.p., and then we are back to usual non-anonymous networks.
The key insight is that this does not hold if we want Las Vegas
algorithms. A randomised distributed algorithm in anonymous networks cannot verify that, e.g., random identifiers are indeed globally unique. Before Jochen's work, we did not really understand what can be computed with randomised Las Vegas algorithms in anonymous networks.
To me the main result is the following characterisation: in anonymous networks, randomised Las Vegas algorithms are precisely as powerful as deterministic algorithms that have access to a distance-2 colouring
. Las Vegas algorithms can find a distance-2 colouring; conversely, with a distance-2 colouring we can derandomise any Las Vegas algorithm. This is a surprising, deep, and highly nontrivial result that will hopefully soon find its way to e.g. textbooks and lecture courses related to the theory of distributed algorithms.
Congratulations to Dr. Seidel! #distributedcomputing #phdthesis