On Byzantine broadcast in loosely connected networks

DOI10.1007/978-3-642-33651-5_18MaRDI QIDQ4909416zbMATH OpenOpenAlexFDO

Authors Alexandre Maurer, Sébastien Tixeuil

Publication date 13 March 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

broadcastByzantine failuresdistributed computingfault toleranceloosely connected networksprotocolrandom failures

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Abstract: We consider the problem of reliably broadcasting information in a multihop asynchronous network that is subject to Byzantine failures. Most existing approaches give conditions for perfect reliable broadcast (all correct nodes deliver the authentic message and nothing else), but they require a highly connected network. An approach giving only probabilistic guarantees (correct nodes deliver the authentic message with high probability) was recently proposed for loosely connected networks, such as grids and tori. Yet, the proposed solution requires a specific initialization (that includes global knowledge) of each node, which may be difficult or impossible to guarantee in self-organizing networks - for instance, a wireless sensor network, especially if they are prone to Byzantine failures. In this paper, we propose a new protocol offering guarantees for loosely connected networks that does not require such global knowledge dependent initialization. In more details, we give a methodology to determine whether a set of nodes will always deliver the authentic message, in any execution. Then, we give conditions for perfect reliable broadcast in a torus network. Finally, we provide experimental evaluation for our solution, and determine the number of randomly distributed Byzantine failures than can be tolerated, for a given correct broadcast probability.

Recommendations

• On reliable broadcast in a radio network
• Reliable Broadcast Tolerating Byzantine Faults in a Message-Bounded Radio Network
• Tolerating Random Byzantine Failures in an Unbounded Network
• FAST BROADCASTING WITH BYZANTINE FAULTS
• Broadcast in radio networks tolerating Byzantine adversarial behavior

Cited in

(9)

• Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions
• Reliable Broadcast Tolerating Byzantine Faults in a Message-Bounded Radio Network
• Discovering Network Topology in the Presence of Byzantine Faults
• Tolerating Random Byzantine Failures in an Unbounded Network
• Reliable broadcast in unknown fixed-identity networks
• scientific article; zbMATH DE number 7650856 (Why is no real title available?)
• Reliable broadcast in dynamic networks with locally bounded Byzantine failures
• Distributed CONGEST Algorithms against Mobile Adversaries
• Byzantine-Tolerant Reliable Broadcast in the Presence of Silent Churn

This page was built for publication: On Byzantine broadcast in loosely connected networks

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