We investigate the problem of broadcasting in a complete synchronous network with dynamic edge faults. The faults may be loss of messages only (omissions) or of arbitrary type (Byzantine fualts). In both cases, broadcasting can be done in at most 5 rounds, i.e. in constant time, as long as the maximal number \phi of fautls per round allows broadcasting at all. We present algorithms which are optimal for different variants of the problem.

Broadcasting in Complete Networks with Dynamic Edge Faults

Liptak, Zsuzsanna;
2000-01-01

Abstract

We investigate the problem of broadcasting in a complete synchronous network with dynamic edge faults. The faults may be loss of messages only (omissions) or of arbitrary type (Byzantine fualts). In both cases, broadcasting can be done in at most 5 rounds, i.e. in constant time, as long as the maximal number \phi of fautls per round allows broadcasting at all. We present algorithms which are optimal for different variants of the problem.
2000
9782912590114
broadcasting, Byzantine faults, synchronous distributed systems, complete graph, dynamic edge failure, fault tolerance
File in questo prodotto:
File Dimensione Formato  
opodis00.pdf

solo utenti autorizzati

Tipologia: Versione dell'editore
Licenza: Copyright dell'editore
Dimensione 569.27 kB
Formato Adobe PDF
569.27 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/391098
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact