2021-09-17T13:29:49Zhttps://tsukuba.repo.nii.ac.jp/oaioai:tsukuba.repo.nii.ac.jp:000198762021-03-01T17:27:05ZA new parameter for a broadcast algorithm with locally bounded Byzantine faults繁野, 麻衣子Ichimura, AkiraShigeno, Maiko© 2010 Elsevier B.V.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.Elsevier B.V.2010-06engjournal articlehttp://hdl.handle.net/2241/105843https://tsukuba.repo.nii.ac.jp/records/1987610.1016/j.ipl.2010.04.0030020-0190AA00674407Information processing letters11012-13514517https://tsukuba.repo.nii.ac.jp/record/19876/files/IPL_110-12.pdfapplication/pdf113.7 kB2013-12-24