Minimum-Cost First-Push-Then-Pull Gossip Algorithm

Abstract

In this paper, we study the communication overhead of gossip-based information dissemination algorithms. Among basic variants of gossip algorithm Push is most efficient in the early rounds while, in contrast, Pull becomes more efficient in the later rounds. Therefore, a cost-efficient gossip algorithm needs to combine the advantages of push and pull algorithms. One possible approach is to begin with push algorithm and then at some point switch to pull algorithm. We analyze the effect of transition round from Push to Pull on the communication cost of gossip algorithm. We use simple deterministic difference equations to approximately model the message propagation throughout the network for both Push and Pull algorithms and derive closed form solution for Pull model.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2012
Accession Number
AD1108603

Entities

People

  • Ali Saidi
  • Mojdeh Mohtashemi

Organizations

  • MITRE Corporation

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Ad Hoc Networks
  • Algorithms
  • Applied Mathematics
  • Computer Science
  • Computers
  • Cooperation
  • Damage Detection
  • Difference Equations
  • Differential Equations
  • Diffusion
  • Equations
  • Mathematical Models
  • Mesh Networks
  • Mobile Ad Hoc Networks
  • Mobile Phones
  • Mobility
  • Models
  • Networks
  • Probability
  • Simulations

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Operations Research
  • Systems Analysis and Design