Networks Cannot Compute Their Diameter in Sublinear Time

Silvio Frischknecht, Stephan Holzer and Roger Wattenhofer

Abstract:
We study the problem of computing the diameter of a network in a distributed way. The model of distributed computation we consider is: in each synchronous round, each node can transmit a different (but) short message to each of its neighbors. We provide an lower bound for the number of communication rounds needed, where n denotes the number of nodes in the network. This lower bound is valid even if the diameter of the network is a small constant. We also show that a -approximation of the diameter requires rounds. Furthermore we use our new technique to prove an lower bound on approximating the girth of a graph by a factor
.

Guest: Stephan Holzer
Host: Chen Avin

Rumor Spreading and Vertex Expansion

George Giakkoupis and Thomas Sauerwald

Abstract:
We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion , we show that this protocol spreads a rumor from a single node to all other nodes in rounds with high probability. Further, we construct graphs for which rounds are needed. Our results complement a long series of works that relate rumor spreading to edge-based notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion.

Guest: George Giakkoupis
Host: Chen Avin

Black Hole Search with Finite Automata Scattered in a Synchronous Torus

Jeremie Chalopin, Shantanu Das, Arnaud Labourel and Euripides Markou

Abstract:
We consider the problem of locating a black hole in synchronous anonymous networks using finite-state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. Previous studies for black hole search used more powerful models where the agents had non-constant memory, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to oriented torus networks and first show that no team of finite-state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on thenumber of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens, thus providing matching upper bounds for the problem.

Guest: Jeremie Chalopin
Host: Zvi Lotker

The Round Complexity of Distributed Sorting

Boaz Patt-Shamir and Marat Teplitsky

Abstract:
We consider the model of fully connected networks, where
in each round each node can send an O(log n)-bit message
to each other node (this is the congest model with diame-
ter 1). It is known that in this model, min-weight spanning
trees can be found in O(log log n) rounds. In this paper we
show that distributed sorting, where each node has at most
n items, can be done in time O(log log n) as well. It is also
shown that selection can be done in O(1) time. (Using a con-
current result by Lenzen and Wattenhofer, the complexity of
sorting is further reduced to constant.) Our algorithms are
randomized, and the stated complexity bounds hold with
high probability.

Guest: Boaz Patt-Shamir
Host: Chen Avin