edited by Roger Wattenhofer
Anonymous Distributed Computing:
Computability, Randomization and Checkability
1st edition / 1. Aufl. 2015. XII, 136 pages/Seiten, € 64,00.
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
Hartung-Gorre Verlag / D-78465 Konstanz / Germany