TY - GEN
T1 - Information Dissemination via Broadcasts in the Presence of Adversarial Noise
AU - Efremenko, Klim
AU - Kol, Gillat
AU - Paramonov, Dmitry
AU - Raz, Ran
AU - Saxena, Raghuvansh R.
N1 - Publisher Copyright:
© Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, and Raghuvansh R. Saxena.
PY - 2024/7
Y1 - 2024/7
N2 - 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.
AB - 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.
KW - Error Correcting Codes
KW - Interactive Coding
KW - Radio Networks
UR - http://www.scopus.com/inward/record.url?scp=85199327525&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85199327525&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2024.19
DO - 10.4230/LIPIcs.CCC.2024.19
M3 - Conference contribution
AN - SCOPUS:85199327525
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 39th Computational Complexity Conference, CCC 2024
A2 - Santhanam, Rahul
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 39th Computational Complexity Conference, CCC 2024
Y2 - 22 July 2024 through 25 July 2024
ER -