The role of randomness in the broadcast congested clique model

We study the role of randomness in the broadcast congested clique model. This is a message-passing model of distributed computation where the nodes of a network know their local neighborhoods and they broadcast, in synchronous rounds, messages that are visible to every other node. This works aims to separate three different settings: deterministic protocols, randomized protocols with private coins, and randomized protocols with public coins. We obtain the following results: • If more than one round is allowed, public randomness is as powerful as private randomness. • One-round public-coin algorithms can be exponentially more powerful than deterministic algorithms running in several rounds. • One-round public-coin algorithms can be exponentially more powerful than one-round private-coin algorithms. • One-round private-coin algorithms can be exponentially more powerful than one-round deterministic algorithms.