2026-08-02T22:12:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11799 2024-03-06T10:48:48Z ddc:004 open_access

Interactive Coding Resilient to an Unknown Number of Erasures Gelles, Ran Iyer, Siddharth Interactive coding erasure channels distributed computation with noise unbounded noise We consider distributed computations between two parties carried out over a noisy channel that may erase messages. Following a noise model proposed by Dani et al. (2018), the noise level observed by the parties during the computation in our setting is arbitrary and a priori unknown to the parties. We develop interactive coding schemes that adapt to the actual level of noise and correctly execute any two-party computation. Namely, in case the channel erases T transmissions, the coding scheme will take N+2T transmissions using an alphabet of size 4 (alternatively, using 2N+4T transmissions over a binary channel) to correctly simulate any binary protocol that takes N transmissions assuming a noiseless channel. We can further reduce the communication to N+T by relaxing the communication model and allowing parties to remain silent rather than forcing them to communicate in every round of the coding scheme. Our coding schemes are efficient, deterministic, have linear overhead both in their communication and round complexity, and succeed (with probability 1) regardless of the number of erasures T. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Gelles and Siddharth Iyer 2020 Is Part Of LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2019.13 urn:nbn:de:0030-drops-117999 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.13 eng https://creativecommons.org/licenses/by/3.0/legalcode