Abstract

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 ran-domness. One-round public-coin algorithms can be exponentially more powerful than determin-istic 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. (C) 2020 Elsevier Inc. All rights reserved.