The congested clique model is a message-passing model of distributed computing where the underlying communication network is the complete graph K_n. Therefore, in this network of diameter 1, the issue of locality is taken out of the picture. The focus is set on congestion, which is, together with locality, the main issue in distributed computing. The point is the following: if the communication network is a complete graph K_n and the cost of local computation is ignored, then the only obstacle to perform any task is due to congestion alone.

In this talk we will discuss the graph reconstruction problem. In this problem, a graph G is given as input to the nodes of the complete communication network K_n (i.e., each node receives its local neighborhood in G). Note that the input graph G is a subgraph of K_n with V(G) = V(K_n) = {1,…,n}. The challenge is to devise an algorithm after which every node ends up knowing the whole graph G. In this talk we will present tight results (in terms of bandwidth and number of rounds) for well-known classes of graphs.

About Ivan Rapaport

Ivan Rapaport is a Full Professor of the Department of Mathematical Engineering of the University of Chile. He obtained a PhD in Computer Science at the École Nórmale Supérior de Lyon in 1999. He has worked in many different issues related to networks: from cellular automata to genetic networks. His main interest, now, lies in distributed computing. In particular, in the problem of checking whether a given network has particular structural properties (such as being planar, k-colorable, etc).

Este evento se impartirá en inglés