Fast gossiping with short unreliable messages

Bogdan S. Chlebus, Krzysztof Diks, Andrzej Pelc

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Each of n nodes of a communication network has a piece of information (gossip) which should be made known to all other nodes. Gossiping is done by sending letters. In a unit of time each node can either send one letter to a neighbor or receive one such letter, containing one gossip currently known to the sender. Letters reach their destinations with constant probability 0<q<1, independently of one another. For a large class of networks, including rings, grids, hypercubes and complete graphs, we construct gossip schemes working in linear time and successfully performing gossiping with probability converging to 1, as the number of nodes grows.

Original languageEnglish (US)
Pages (from-to)15-24
Number of pages10
JournalDiscrete Applied Mathematics
Volume53
Issue number1-3
DOIs
StatePublished - Sep 14 1994
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Fast gossiping with short unreliable messages'. Together they form a unique fingerprint.

Cite this