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

Synchronous t-resilient consensus in arbitrary graphs

Armando Castañeda
  • Function : Author
  • PersonId : 1309183
Ami Paz
  • Function : Author
  • PersonId : 1309185
Sergio Rajsbaum
  • Function : Author
  • PersonId : 973547
Corentin Travers
  • Function : Author
  • PersonId : 1309186

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⟩
37 View
15 Download

Altmetric

Share

Gmail Facebook X LinkedIn More