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.
Synchronizers for unreliable settings have been studied by @cite_31 , which address a dynamic setting, and by Harrington and Somani @cite_35 , which assume faulty nodes.
@cite_35 @cite_31
2123211389 1970745521
Synchronizing distributed networks allows nodes to share resources efficiently, run synchronous programs and vote on redundant results in fault tolerant systems. Due to the low connectivity of hypercube networks, neither the fault tolerant hardware synchronization schemes, phased locked loops nor multistage synchronizers can be used without adding additional links. We describe a new hardware method developed to synchronize hypercube networks. Our analysis shows that the method can sustain one fault if the connectivity of the hypercube, n, is at least three, and it can tolerate up to m spl ges 2 Byzantine faults as long as the connectivity of the hypercube, n, is greater than max 2m+1,3m-2). This scheme has been implemented in an ASIC design for a hypercube of dimension five. It will be used in the Proteus parallel computer system to synchronize the circuit switching communication network. > We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect is that clock synchronization is an on-going task, thus the assumption that some of the processors never fail is too optimistic. To cope with this reality, we suggest self-stabilizing protocols that stabilize in any (long enough) period in which less than a third of the processors are faulty. Another aspect is that the clock value of each processor is bounded. A single transient fault may cause the clock to reach the upper bound. Therefore, we suggest a bounded clock that wraps around when appropriate.We present two randomized self-stabilizing protocols for synchronizing bounded clocks in the presence of Byzantine processor failures. The first protocol assumes that processors have a common pulse, while the second protocol does not. A new type of distributed counter based on the Chinese remainder theorem is used as part of the first protocol.