scientific article; zbMATH DE number 15364
[For the entire collection see Zbl 0698.00017.] In the gossip problem there are \(n\) persons, each knowing a piece of information ( gossip) unknown to others. At each discrete unit of time information is exchanged between pairs of persons when all the information known to one is passed on to the other. If information exchange takes place in both ways (modelled by an undirected graph) we have the telephone problem. If exchange can take place only in one way in unit time (modelled by a directed graph) we have a telegraph problem. If, in unit time, a person can communicate with \(k\) others we have a \(k\)- conference calls problem or a \(k\)-telegraph problem, respectively. One of the objectives is to find the minimum number \(T_ k(n)\) of rounds (time) necessary for a complete exchange of information. The authors settle a conjecture of Entringer and Slater for the \(k\)-telegraph problem: \[ T_ k(n)=\alpha_ k\log_{k+1}(n)+O(1)\text{ with } \alpha_ k\to 1\text{ as } k\to\infty. \] They actually prove that, for \(k\geq 2\), \(T_ k(n)\in\{\lceil\log_{\tau_ k}n\rceil,\lceil\log_{\tau_ k}n\rceil+1\}\) where \(\tau_ k={1\over 2}[k+(k^ 2+4)^{1/2}]\) is the positive root of \(x^ 2-kx-1=0\). The proof technique involves the generation of a message sequence involving the recurrent sequence \(\{F_ k(t)\}\) defined by \(F_ k(0)=0\), \(F_ k(1)=1\) and \(F_ k(t+1)=kF_ k(t)+F_ k(t+1)\) for \(t\geq 1\). This is an obvious generalization of the Fibonacci sequence. At least two sets of people seem to be working on these problems in non- communicating compartments. For example the list of references in the paper under review and the one by \textit{Akos Seress} [Combinatorial mathematics, Proc. 3rd Int. Conf., New York/NY (USA) 1985, Ann. N.Y. Acad. Sci. 555, 375-382 (1989; Zbl 0722.05059)] have empty intersection.
- Quick gossiping by telegraphs
- Methods and problems of communication in usual networks
- Note on optimal gossiping in some weak-connected graphs
- Gossiping and broadcasting versus computing functions in networks.
- Lower bounds on systolic gossip
- Gossiping with multiple sends and receives
- Lossy gossip and composition of metrics
- Information flows on hypergraphs
- On Gossiping with Faulty Telephone Lines
- Quick Gossiping by Conference Calls
- scientific article; zbMATH DE number 3849231 (Why is no real title available?)
- scientific article; zbMATH DE number 3979080 (Why is no real title available?)
- scientific article; zbMATH DE number 4059434 (Why is no real title available?)
- Gossiping in Minimal Time
- scientific article; zbMATH DE number 166936 (Why is no real title available?)
- Fast Gossiping by Short Messages
- scientific article; zbMATH DE number 1756018 (Why is no real title available?)
- Gossiping and broadcasting versus computing functions in networks
- scientific article; zbMATH DE number 4189783 (Why is no real title available?)
- Gossiping in vertex-disjoint paths mode in interconnection networks
- A class of solutions to the gossip problem. III
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972008)
