<aside>
🌐
Outdated page — the Temporal Graph Wiki has moved. Read this page on temporalgraph.wiki.
</aside>
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.