Information-Spreading

The Gossiping Problem The Gossiping Problem is a classic problem in distributed systems and graph theory. N people each know a unique secret, and they share information through phone calls. On each call, both parties share all secrets they know. The goal: find the minimum number of calls needed for everyone to know all secrets. The Scenario N people, N secrets: Person i knows secret Si initially When persons i and j call each other, they share ALL secrets they know Goal: Everyone knows all N secrets Question: What’s the minimum number of calls? The Mathematical Result For n ≥ 4 people: ...