\input zb-basic
\input zb-ioport
\iteman{io-port 06013746}
\itemau{Ichimura, Akira; Shigeno, Maiko}
\itemti{A new parameter for a broadcast algorithm with locally bounded Byzantine faults.}
\itemso{Inf. Process. Lett. 110, No. 12-13, 514-517 (2010).}
\itemab
Summary: This paper deals with broadcasting in a network with $t$-locally bounded Byzantine faults. One of the simplest broadcasting algorithms under Byzantine failures is referred to as a certified propagation algorithm (CPA), which is the only algorithm we know that does not use any global knowledge of the network topology. Hence, it is worth focusing on a graph-theoretic parameter such that CPA will work correctly. Using the theory of maximum adjacency (MA) ordering, a new graph-theoretic parameter for CPA is proposed. Within a factor of two, this parameter approximates the largest $t$ such that CPA works for $t$-locally bounded Byzantine faults.
\itemrv{~}
\itemcc{}
\itemut{graph algorithm; fault tolerance; broadcasting; Byzantine faults; MA ordering}
\itemli{doi:10.1016/j.ipl.2010.04.003}
\end