Multi-Party Error Resilience Beyond 1/n

In the information dissemination problem, n parties each hold a unique piece of information and wish to learn all the information. They communicate over an adversarial broadcast channel, where an adversary may corrupt a fraction of the received transmissions. What is the largest fraction of errors to which an information dissemination protocol can be resilient?

In adversarial multi-party communication models, 1/n is a natural upper bound on error resilience, and prior work has therefore largely avoided these models. The reason is a simple attack: with only a 1/n-fraction of errors, the adversary can corrupt all messages sent by the party that broadcasts least, making information dissemination impossible.

We observe, however, that this attack applies only to non-adaptive protocols, a restricted class of protocols with a fixed speaking order. Can an adaptive protocol tolerate a constant fraction of errors, or does the 1/n barrier persist?

We find that the truth lies in the middle. Our main result shows that the optimal error resilience of general adaptive information dissemination protocols over the broadcast channel is Θ(1/√n). We give a protocol achieving this resilience and a matching impossibility result that holds even against erasure noise. To the best of our knowledge, this is the first impossibility result for multi-party adversarial noise in the adaptive model.