Gossips and telegraphs |
| |
Authors: | Roger C Entringer Peter J Slater |
| |
Institution: | Department of Mathematics, University of New Mexico, Albuquerque, NM 87131, USA;Applied Mathematics-5121, Sandia Laboratories, Albuquerque, NM 87115, USA |
| |
Abstract: | 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) = ?logk+1n?.We define g(n, k) analogously except that no person may both send and receive information during a unit time period. We show ?logk+1n?≤g(n, k)≤2?logk+1n? 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|