Introduction

• Brief explanation of gossip theory: origin in communication protocols and distributed computing.
• Core problems: Gossiping (All-to-All) and Broadcasting (One-to-All).
• Relevance: foundational to understanding information dissemination in dynamic systems.

Literature on Gossip Theory

Classical Setting and Historical Origins

• Origin in the 1950s–1970s (though often referred to as “19 hundreds”) in the context of telephone models and early network theory.
• Milestone papers and authors:
  • H. T. Gallager (1962) — early exploration of broadcasting on fixed networks.
  • J. A. Turner (1978) — bounds on broadcast time in complete graphs.
  • M. J. Fischer & A. R. Meyer (1971) — minimal time for gossiping.
  • Mention of the telephone model and its combinatorial abstractions.
• Key constructions:
  • Minimal-time gossip schemes on complete graphs.
  • Use of gossip graphs (e.g., trees, stars, complete graphs).
  • Techniques like scheduling matrices, round-based protocols, etc.

Gossiping and Broadcasting — Overview of Core Problems and Results

• Broadcasting (One-to-All)
  • Objective: Disseminate a message from one source to all others.
  • Results:
    • Time complexity in various models (synchronous/asynchronous).
    • Lower and upper bounds depending on the topology.
• Gossiping (All-to-All)
  • Objective: Every node must learn every other’s message.
  • Minimum time on complete graphs: $2n – 4$ rounds (tight).
  • Known optimal schedules: rotation schemes, Johnson graphs, etc.
• Influence of constraints:
  • Degree bounds.
  • Limited bandwidth / call restrictions.
  • Fault tolerance or message loss.

Connection to Temporal Graphs

• Motivation: Real-world networks are not static.
• Transition to temporal models (links appear over time).
• Definitions:
  • Temporal broadcasting time: time to spread from one source in a temporal graph.
  • Temporal gossiping time: time for all nodes to exchange all messages.