A new parameter for a broadcast algorithm with locally bounded Byzantine faults

作者：Ichimura Akira; Shigeno Maiko^*

来源：Information Processing Letters, 2010, 110(12-13): 514-517.

DOI：10.1016/j.ipl.2010.04.003

• Graph algorithm
• Fault tolerance
• Broadcasting
• Byzantine faults
• MA ordering

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.

• 出版日期2010-6-15