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

被引：18

作者：

Ichimura, Akira ^{[1
]}

Shigeno, Maiko ^{[1
]}

机构：

[1] Univ Tsukuba, Grad Sch Syst & Informat Engn, Tsukuba, Ibaraki 3058573, Japan

来源：

INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 12-13期

关键词：

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

D O I：

10.1016/j.ipl.2010.04.003

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：514 / 517

页数：4