Synchronous t-resilient consensus in arbitrary graphs - Réseaux, Informatique, Systèmes de Confiance
Journal Articles Information and Computation Year : 2023

Synchronous t-resilient consensus in arbitrary graphs

Abstract

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.
Fichier principal
Vignette du fichier
journal.pdf (406.19 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04287975 , version 1 (15-11-2023)

Identifiers

Cite

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⟩
105 View
52 Download

Altmetric

Share

More