Computación distribuida: el modelo Congested Clique

The congested clique model is a message-passing model of distributed computation where the underlying communication network is the complete graph of n nodes. We consider the situation where the joint input to the nodes is an n-node labeled graph G. The reconstruction problem is defined as follows:  if the input graph G does not belong to a particular graph class, then every node must reject; otherwise, every node must "reconstruct G" (i.e., must end up knowing all the edges of G). In this talk we are going to discuss some relations between particular graph classes and the corresponding complexity measures of the distributed algorithms for solving the reconstrucion problem (these complexity measures are in fact time and bandwidth).