GOSSIPS AND TELEGRAPHS

Suppose we have a group of n people, each possessing an item of information not known to any of the others and that during each unit of time each person can send all of the information he knows to at most other people. Further suppose that each of at most k other people can send all of the information they know to him. Determine the length of time required, f(n, k), so that all n people know all of the information. We show f(n, k) = {top left corner}logk+1n{top right corner}. We define g(n, k) analogously except that no person may both send and receive information during a unit time period. We show {top left corner}logk+1n{top right corner}≤g(n, k)≤2{top left corner}logk+1n{top right corner} in general and further show that the upper bound can be significantly improvea in the cases k = 1 or 2. We conjecture g(n, k) = bk logk+1n+0(1) for a function bk we determine. © 1979.