Broadcasting in Hypercubes with Randomly Distributed Byzantine Faults
スポンサーリンク
概要
- 論文の詳細を見る
We study all-to-all broadcasting in hypercubes with randomly distributed Byzantine faults. We construct an efficient broadcasting scheme BC1-n-cube running on the n-dimensional hypercube (n-cube for short) in 2n rounds, where for communication by each node of the n-cube, only one of its links is used in each round. The scheme BC1-n-cube can tolerate &floor; (n-1)/2 &floor; Byzantine faults of nodes and/or links in the worst case. If there are exactly f Byzantine faulty nodes randomly distributed in the n-cube, BC1-n-cube succeeds with a probability higher than 1-(64nf/2^n) ^⌈ n/2⌉ . In other words, if 1/(64nk) of all the nodes (i.e., 2^n/(64nk) nodes) fail in Byzantine manner randomly in the n-cube, then the scheme succeeds with a probability higher than 1-k^-⌈ n/2⌉ . We also consider the case where all nodes are faultless but links may fail randomly in the n-cube. Broadcasting by BC1-n-cube is successful with a probability hig her than 1-k^-⌈ n/2⌉ provided that not more than 1/(64(n + 1)k) of all the links in the n-cube fail in Byzantine manner randomly. For the case where only links may fail, we give another broadcasting scheme BC2-n-cube which runs in 2n^2 rounds. Broadcasting by BC2-n-cube is successful with a high probability if the number of Byzantine faulty links randomly distributed in the n-cube is not more than a constant fraction of the total number of links. That is, it succeeds with a probability higher than 1-n k-⌈ n/2⌉ if 1/(48k) of all the links in the n-cube fail randomly in Byzantine manner.
- 社団法人電子情報通信学会の論文
- 1995-09-25
著者
-
Bao F
National Univ. Sinpapore Singapore
-
Bao Feng
Faculty of Engineering, Gunma University
-
Igarashi Yoshihide
Faculty of Engineering, Gunma University
-
Katano Keiko
Faculty of Engineering, Gunma University
-
Bao Feng
Faculty Of Engineering Gunma University
-
Katano Keiko
Faculty Of Engineering Gunma University
-
Igarashi Y
Gunma Univ. Kiryu‐shi Jpn
-
Igarashi Yoshihide
Faculty Of Engineering Gunma University
関連論文
- A More Efficient Improvement of the Virtual Software Token Protocols (Fundamental Theories for Communications)
- Security Notes on Generalization of Threshold Signature and Authenticated Encryption(Information Security)
- Optimal Time Broadcasting Schemes in Faulty Star Graphs (Special Section on Discrete Mathematics and Its Applications)
- Reliable Broadcasting and Secure Distributing in Channel Networks(Special Section on Discrete Mathematics and Its Applications)
- Independent Spanning Trees of Product Graphs and Their Construction
- Independent Spanning Trees of Product Graphs and Their Construction
- Nonadaptive Fault-Tolerant File Transmission in Rotator Graphs (Special Section on Discrete Mathematics and Its Applications)
- Broadcasting in Hypercubes with Randomly Distributed Byzantine Faults
- Broadcasting in Hypercubes with Randamly Distributed Byzantine Faults
- Reliability of Hypercubes for Broadcasting with Random Faults
- Embeddings of Hyper-Rings in Hypercubes
- Some Results on Decomposability of Weakly Invertible Finite Automata
- A Shortest Path Algorithm for Banded Matrices by a Mesh Connection without Processor Penalty
- Navigating in Unknown Environment with Rectangular Obstacles
- Some Modifications of the Tournament Algorithm for the Mutual Exclusion Problem
- A Robot Navigation Strategy in Unknown Environment and Its Efficiency (Special Section on Discrete Mathematics and Its Applications)