Suppose that we have a network of n processors where each processor knows its own ID and the IDs of its neighbors. Processors communicate in synchronous rounds by writing messages on a whiteboard, which is visible to all of them. The goal is to design a protocol at the end of which every processor knows the topology of the network. It has already been shown that there is a one-round protocol of O(log n) message size for reconstructing networks with bounded degeneracy. The main drawback of that protocol is that the degeneracy k of the network must be known a priori by the processors and that the protocol does not reconstruct the network if its degeneracy is k+1. In this paper we address this issue by introducing a stronger notion of reconstruction: the processors must be able to reconstruct every network, and for networks belonging to some particular class the expected size of the messages written on the whiteboard must be O(log n). We prove the existence of such a protocol for the class of Barabasi-Albert trees. More precisely, we introduce a very simple two-round protocol that reconstructs every network G, and prove that the expected length of the messages written by every processor in this protocol is upper bounded by 31/20 log(n) when G is a Barabasi-Albert tree. Moreover, we show computational evidence suggesting that the same protocol works for arbitrary Barabasi-Albert networks. Our computational experiments suggest that if G is a Barabasi-Albert network generated with parameter m, then for every processor v in G the length of the first message written by v on the whiteboard is log(n) while the expected length of the second message is upper bounded by (m+1)log(n).

About Ivan Rapaport 

Ivan Rapaport is an Associate Professor in the Department of Mathematical Engineering, Universidad de Chile. He received his Ph.D. from the École Normale Supérieure de Lyon, France. His research interests are in the area of Distributed Systems: multiparty computational models, communication complexity, cellular automata, tiling models, biological networks. He has served many times as a committee member in the Latin American computer science conference LATIN. He has participated in several projects funded by France and National Agencies.  These projects have been mainly related to networks (ranging from social networks to biological networks). He has several publications in journals and conference proceedings.

Personal Site

This event will be conducted in English