| Presentation | 1994/10/21 Broadcasting in Hypercubes with Randamly Distributed Byzantine Faults Feng Bao, Yoshihide Igarashi, Keiko Katano, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper 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-cube (n- dimesional hypercube) in time 2n where for communication by each node,only one of its links is used in each time unit.The scheme BC1-n-cube can tolerate [(n-1), 2] Byzantine node/link faults in the worst case.If there are exactly fByzantine faulty nodes randomly distributed in the n-cube,BC1-n-cube succeeds in broudcasting with probability higher than 1-(64nf/2^n)^[n/2]>.In other words,if 1/64nk of all the nodes fail (in Byzantine manner) randomly in the n-cube,then the scheme succeeds with probability higher than 1-k^-[n/2]>.We also consider the case where all the nodes are fault-free but links may fail randomly in the n-cube. Scheme BC1-n-cube succeeds in broadcasting with probability higher 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 onlylinks may fail,we give another broadcasting scheme BC2-n-cube,which runs in time 2n^2.Scheme BC2-n-cube can tolerate a constant proportional Byzantine link faults that are randomly distributed in the n-cube.It succeeds with probability higher than 1-n・k^-[n/2]> if at most 1/48k of all the links in the n-cube fail (in Byzantine manner) randomly. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | hypercubes / broadcasting / fault-tolerance / random faults |
| Paper # | COMP94-48 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1994/10/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Broadcasting in Hypercubes with Randamly Distributed Byzantine Faults |
| Sub Title (in English) | |
| Keyword(1) | hypercubes |
| Keyword(2) | broadcasting |
| Keyword(3) | fault-tolerance |
| Keyword(4) | random faults |
| 1st Author's Name | Feng Bao |
| 1st Author's Affiliation | Department of Computer Science,Faculty of Engineering,Gunma University() |
| 2nd Author's Name | Yoshihide Igarashi |
| 2nd Author's Affiliation | Department of Computer Science,Faculty of Engineering,Gunma University |
| 3rd Author's Name | Keiko Katano |
| 3rd Author's Affiliation | Department of Computer Science,Faculty of Engineering,Gunma University |
| Date | 1994/10/21 |
| Paper # | COMP94-48 |
| Volume (vol) | vol.94 |
| Number (no) | 304 |
| Page | pp.pp.- |
| #Pages | 9 |
| Date of Issue | |