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 @math fraction of all messages while incurring a moderate blowup of @math 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.
Pelc @cite_5 shows that if the number of Byzantine-corrupted links is bounded by @math , reliable communication is achievable only over graphs whose connectivity is more than @math . The same work also considers the case where each link is faulty with some probability. In a more recent work, Feinerman, Haeupler and Korman @cite_36 also address complete synchronous networks, and study the specific problems of broadcast and majority consensus under random errors.
@cite_36 @cite_5
2071898078 2950535145
We construct and analyze a fast broadcasting algorithm working in the presence of Byzantine component faults. Such faults are particularly difficult to deal with, as faulty components may behave arbitrarily (even maliciously) as transmitters, by either blocking, rerouting, or altering transmitted messages in a way most detrimental to the broadcasting process. We assume that links and nodes of a communication network are subject to Byzantine failures, and that faults are distributed randomly and independently, with link failure probability p and node failure probability q, these parameters being constant and satisfying the inequality (1 - p)2(1 - q) > 1 2. A broadcasting algorithm, working in an n-node network, is called almost safe if the probability of its correctness is at least 1 - 1 n, for sufficiently large n. Thus the robustness of the algorithm grows with the size of the network. Our main result is the design and analysis of an almost safe broadcasting algorithm working in time O(log2 n) and using O(n log n) messages in n-node networks. Under a stronger assumption on failure probability parameters, namely (1 - p)2(1 - q)2 > 1 2, our algorithm can be modified to work in time O(log2 n log log n), also using O(n log n) messages. The novelty of our algorithm is that it can cope with the most difficult type of faults, potentially affecting all components of the network (both its links and nodes), and that it is simultaneously robust and efficient. Consider a network of n processes each of which has a d-dimensional vector of reals as its input. Each process can communicate directly with all the processes in the system; thus the communication network is a complete graph. All the communication channels are reliable and FIFO (first-in-first-out). The problem of Byzantine vector consensus (BVC) requires agreement on a d-dimensional vector that is in the convex hull of the d-dimensional input vectors at the non-faulty processes. We obtain the following results for Byzantine vector consensus in complete graphs while tolerating up to f Byzantine failures: * We prove that in a synchronous system, n >= max(3f+1, (d+1)f+1) is necessary and sufficient for achieving Byzantine vector consensus. * In an asynchronous system, it is known that exact consensus is impossible in presence of faulty processes. For an asynchronous system, we prove that n >= (d+2)f+1 is necessary and sufficient to achieve approximate Byzantine vector consensus. Our sufficiency proofs are constructive. We show sufficiency by providing explicit algorithms that solve exact BVC in synchronous systems, and approximate BVC in asynchronous systems. We also obtain tight bounds on the number of processes for achieving BVC using algorithms that are restricted to a simpler communication pattern.