Title: Making Asynchronous Distributed Computations Robust to Noise,
Abstract: We consider the problem of making distributed computations robust to noise,
in particular to worst-case (adversarial) corruptions of messages. We give a
general distributed interactive coding scheme which simulates any asynchronous
distributed protocol while tolerating an optimal corruption of a $\Theta(1/n)$
fraction of all messages while incurring a moderate blowup of $O(n\log^2 n)$ in
the communication complexity.
Our result is the first fully distributed interactive coding scheme in which
the topology of the communication network is not known in advance. Prior work
required either a coordinating node to be connected to all other nodes in the
network or assumed a synchronous network in which all nodes already know the
complete topology of the network.