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

作     者：Ichimura, Akira Shigeno, Maiko 

作者机构：Univ Tsukuba Grad Sch Syst & Informat Engn Tsukuba Ibaraki 3058573 Japan 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2010年第110卷第12-13期

页      面：514-517页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：MEXT Kayamori Foundation of Informational Science Advancement Grants-in-Aid for Scientific Research Funding Source: KAKEN 

主　　题：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. (C) 2010 Elsevier B.V. All rights reserved.