On the communication surplus incurred by faulty processors

Dariusz R. Kowalski, Michał Strojnowski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


We study the impact of faulty processors on the communication cost of distributed algorithms in a message-passing model. The system is synchronous but prone to various kinds of processor failures: crashes, message omissions, (authenticated) Byzantine faults. One of the basic communication tasks, called fault-tolerant gossip, or gossip for short, is to exchange the initial values among all non-faulty processors. In this paper we address the question if there is a gossip algorithm which is both fault-tolerant, fast and communication-efficient? We answer this question in affirmative in the model allowing only crash failures, and in some sense negatively when the other kinds of failures may occur. More precisely, in an execution by n processors when f of them are faulty, each non-faulty processor contributes a constant to the message complexity, each crashed processor contributes ⊖(f ε) (ε > 0 could be an arbitrarily small constant independent from n, f but dependent on the algorithm), each omission (or authenticated Byzantine) processor contributes ⊖(t), and each-even potential-Byzantine failure results in additional ⊖(n) messages sent.

Original languageEnglish (US)
Title of host publicationDistributed Computing - 21st International Symposium, DISC 2007, Proceedings
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540751410
StatePublished - 2007
Externally publishedYes
Event21st International Symposium on Distributed Computing, DISC 2007 - Lemesos, Cyprus
Duration: Sep 24 2007Sep 26 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4731 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Symposium on Distributed Computing, DISC 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the communication surplus incurred by faulty processors'. Together they form a unique fingerprint.

Cite this