Making asynchronous distributed computations robust to noise

DOI10.1007/S00446-018-0343-5zbMATH Open1451.68040arXiv1702.07403OpenAlexW2591825508WikidataQ129189554 ScholiaQ129189554MaRDI QIDQ2010600FDOQ2010600

Bernhard Haeupler, Ran Gelles, Keren Censor-Hillel

Publication date: 27 November 2019

Published in: Distributed Computing (Search for Journal in Brave)

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(nlo{g}^{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.

Full work available at URL: https://arxiv.org/abs/1702.07403

zbMATH Keywords

adversarial noisecomputation with noiseinteractive coding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12) Communication complexity, information complexity (68Q11)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to Distributed Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Complexity of network synchronization
• Graph spanners
• Agreement under faulty interfaces
• Impossibility of distributed consensus with one faulty process
• Coding for interactive communication
• A coding theorem for distributed computation
• Sublinear fully distributed partition with applications
• Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links
• Interactive channel capacity
• Reliable communication in networks with Byzantine link failures
• List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
• Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback
• Optimal Coding for Streaming Authentication and Interactive Communication
• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• Toward Coding for Maximum Errors in Interactive Communication
• Efficient Coding for Interactive Communication
• Interactive Coding for Multiparty Protocols
• Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
• Synchronizing hypercube networks in the presence of faults
• Coding for Interactive Communication Correcting Insertions and Deletions
• The Adversarial Noise Threshold for Distributed Protocols
• Towards Optimal Deterministic Coding for Interactive Communication
• Coding for Interactive Communication: A Survey
• Reliable Communication over Highly Connected Noisy Networks
• Fast Interactive Coding against Adversarial Noise

Cited In (3)

• Noisy beeping networks
• Making Asynchronous Distributed Computations Robust to Channel Noise
• Distributed computations in fully-defective networks

This page was built for publication: Making asynchronous distributed computations robust to noise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010600)