Anonymous Distributed Computing
Computability, Randomization and Checkability
1st Edition
Published on 23. December 2015
Book
Paperback/Softback
XII, 136 pages
978-3-86628-557-6 (ISBN)
Description
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.
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.