Synchronous t-resilient consensus in arbitrary graphs

作     者：Castaneda, Armando Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Roy, Matthieu Travers, Corentin 

作者机构：Univ Nacl Autonoma Mexico Inst Matemat Mexico City Mexico CNRS IRIF Paris France Univ Paris Cite Paris France CNRS LISN Paris France Univ Paris Saclay Paris France CNRS LAAS Toulouse France Univ Aix Marseille LIS Marseille France 

出 版 物：《INFORMATION AND COMPUTATION》 (信息与计算)

年 卷 期：2023年第292卷第1期

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ANR [DUCAT 20-CE48-0006] UNAM-PAPIIT [IA102417, IN108720, IN108723, IN109917, IN106520] Fondation des Sciences Mathematiques de Paris Austrian Science Fund (FWF) INRIA Project GANG netIDEE SCIENCE project [P33775-N] 

主　　题：Crash failures Consensus Combinatorial topology Distributed graph algorithms 

摘      要：We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius(G, t), that extends the standard graph theoretical notion of radius, for considering all the ways in which t nodes may crash, and we present an algorithm that solves consensus in radius(G, t) rounds. Then we derive a lower bound showing that, among oblivious algorithms, our algorithm is optimal for a large family of graphs including all vertex-transitive graphs.(c) 2023 Elsevier Inc. All rights reserved.