Synchronous t-resilient consensus in arbitrary graphs

Armando Castañeda (1) , Pierre Fraigniaud (2) , Ami Paz (3) , Sergio Rajsbaum (1) , Matthieu Roy (4) , Corentin Travers (5)

1 UNAM - Instituto de Matematicas
2 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
3 ParSys - Systèmes Parallèles - LISN
4 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique
5 LIS - Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon)

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.

Keywords: Crash failures; Consensus; Combinatorial topology; Distributed graph algorithms

Domains: Computer Science [cs]; Mathematics [math]

Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy, et al.. Synchronous t-resilient consensus in arbitrary graphs. Information and Computation, 2023, 292, pp.105035. ⟨10.1016/j.ic.2023.105035⟩. ⟨hal-04287975⟩