Series in
Distributed Computing
edited by Roger Wattenhofer
Vol. 22
Jochen Seidel
Anonymous Distributed Computing:
Computability, Randomization and Checkability
1st edition / 1. Aufl. 2015. XII, 136 pages/Seiten, € 64,00.
ISBN
978-3-86628-557-6
This dissertation studies various aspects
of computing in anonymous networks, where nodes are not equipped with unique
identifiers. Nodes in the network exchange messages and each node computes some
local output; the global output of the network is the combination of all local outputs. We
focus mainly on randomized algorithms, beginning with the question “What can be
computed in an anonymous network?”.
Two classes of problems solvable in
anonymous networks are defined, depending on whether nodes are allowed to
revoke their outputs or not. We introduce and study the concept of a
distributed oracle, which in yields a hierarchy of hard and complete problems
for the classes. Several classic and/or characteristic problems in distributed
computing are classified in terms of computability and hardness.
Access to random bits arguably has a huge
impact on the computability in anonymous networks. In an effort to exactly
characterize this impact, we prove that every problem that can be solved (and
verified) by a randomized anonymous algorithm can also be solved by a
deterministic anonymous algorithm provided that the latter is equipped with a
2-hop coloring of the input graph.
It is natural to ask how many random bits
are required to solve any such problem. We find that the answer depends on the
desired runtime of the algorithm. More precisely, we devise a randomized 2-hop
coloring scheme that allows to trade an increase in runtime for a decrease in
the random bit complexity. A lower bound we show yields that the trade-off
achieved by our scheme is asymptotically optimal for any reasonable runtime,
i.e., reducing the runtime must lead to an increase in the random bit
complexity.
Lastly, we study local checkability
of network properties like s-t reachability, or whether the network is acyclic
or contains a cycle. A prover assigns a label to each node so that a verifier
can check in constant time whether the property holds or not. We obtain
asymptotically tight bounds for the label size of the latter two problems. For
s-t reachability, we obtain a new asymptotically tight label size lower bound
in one of our models, and devise an emulation technique that allows us to
transfer a previously known upper bound without asymptotic loss in the bit
complexity in another model.
About
the Author
Jochen Seidel received his Dipl.-Inform. degree in 2011 from the Departement
of Computer Science at the Karlsruhe Institute of Technology, Germany. He then
joined the Distributed Computing group of Prof. Roger Wattenhofer
at ETH Zurich to pursue his doctoral studies. In 2015 he was awarded the Ph.D.
degree for his work on distributed anonymous computing.
Keywords: Distributed Computing, Anonymous Networks, Computability, Randomization,
Non-Determinism.
Direkt bestellen
bei / to order directly from: Hartung.Gorre@t-online.de
Series in Distributed Computing in
http://www.hartung-gorre.de
Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de
Hartung-Gorre Verlag / D-78465
Konstanz / Germany
Telefon: +49
(0) 7533 97227 Telefax: +49 (0) 7533
97228
http://www.hartung-gorre.de eMail: verlag@hartung-gorre.de