World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Tolerating Random Byzantine Failures in an Unbounded Network

    In a context where networks grow larger and larger, their nodes become more likely to fail. Indeed, they may be subject to crashes, attacks, memory corruptions… To encompass all possible types of failure, we consider the most general model of failure: the Byzantine model, where any failing node may exhibit arbitrary (and potentially malicious) behavior.

    We consider an asynchronous grid-shaped network where each node has a probability λ to be Byzantine. Our metric is the communication probability, that is, the probability that any two nodes communicate reliably. A number of Byzantine-resilient broadcast protocols exist, but they all share the same weakness: when the size of the grid increases, the communication probability approaches zero.

    In this paper, we present the first protocol that overcomes this difficulty, and ensures a communication probability of 14λ on a grid that may be as large as we want (for a sufficiently small λ, typically λ<105). The originality of the approach lies in the fractal definition of the protocol, which, we believe, could be used to solve several similar problems related to scalability. We also extend this scheme to a 3-dimensional grid and obtain a 12λ communication probability for λ<103.

    Communicated by D. Peleg