Information Dissemination via Broadcasts in the Presence of Adversarial Noise

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where n parties, each holding an input bit, wish to know each other’s input. For this, they communicate in rounds, where, in each round, one designated party sends a bit to all other parties over a channel governed by an adversary that may corrupt a constant fraction of the received communication. We mention that the dissemination problem was studied in the stochastic noise model since the 80’s. While stochastic noise in multi-party channels has received quite a bit of attention, the case of adversarial noise has largely been avoided, as such channels cannot handle more than a n1 -fraction of errors. Indeed, this many errors allow an adversary to completely corrupt the incoming or outgoing communication for one of the parties and fail the protocol. Curiously, we show that by eliminating these “trivial” attacks, one can get a simple protocol resilient to a constant fraction of errors. Thus, a model that rules out such attacks is both necessary and sufficient to get a resilient protocol. The main shortcoming of our dissemination protocol is its length: it requires Θ(n2) communication rounds whereas n rounds suffice in the absence of noise. Our main result is a matching lower bound of Ω(n2) on the length of any dissemination protocol in our model. Our proof first “gets rid” of the channel noise by converting it to a form of “input noise”, showing that a noisy dissemination protocol implies a (noiseless) protocol for a version of the direct sum gap-majority problem. We conclude the proof with a tight lower bound for the latter problem, which may be of independent interest.

Original languageEnglish (US)
Title of host publication39th Computational Complexity Conference, CCC 2024
EditorsRahul Santhanam
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773317
DOIs
StatePublished - Jul 2024
Event39th Computational Complexity Conference, CCC 2024 - Ann Arbor, United States
Duration: Jul 22 2024Jul 25 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume300
ISSN (Print)1868-8969

Conference

Conference39th Computational Complexity Conference, CCC 2024
Country/TerritoryUnited States
CityAnn Arbor
Period7/22/247/25/24

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Error Correcting Codes
  • Interactive Coding
  • Radio Networks

Fingerprint

Dive into the research topics of 'Information Dissemination via Broadcasts in the Presence of Adversarial Noise'. Together they form a unique fingerprint.

Cite this