A Visualization and Modeling Tool for Fault-Tolerant Gossip Graphs
DOI:
https://doi.org/10.51408/1963-0137Keywords:
Gossip problem, Knödel graphs, Fault-tolerant gossip schemesAbstract
The gossip problem (telephone problem) is an information dissemination problem where each of n nodes of a communication network has a unique message that should be transmitted to all the other nodes using two-way communications (telephone calls) between the pairs of nodes. During a call between the two given nodes, they exchange all the information known to them at that moment.
In this paper, a visualization and modeling tool for constructing and analyzing gossip graphs is presented. The tool features an interactive interface and automated algorithms for generating arbitrary graphs and evaluating their gossiping properties. Among the supported features are k-fault-tolerance analysis, simulation of Messy broadcast models, exploration of the NOHO (No One Hears one’s Own information) schemes, detection of information flow folded paths, and identification of non-optimal communication patterns (i.e., repeated message arrivals).
References
T. Tijdeman, ”On a telephone problem”, Nieuw Archief voor Wiskunde, vol. 3, pp. 188–192, 1971.
B. Baker and R. Shostak, ”Gossips and telephones,” Discrete Mathematics, vol. 2, pp. 191–193, 1972.
R. T. Bumby, ”A problem with telephones,” SIAM Journal on Algebraic and Discrete Methods, vol. 2, pp. 13–18, 1981.
A. Hajnal, E. C. Milner, and E. Szemerdi, ”A cure for the telephone disease,” Canadian Mathematical Bulletin, vol. 15, pp. 447–450, 1972.
A. Seress, ”Quick gossiping by conference calls,” SIAM Journal on Discrete Mathematics, vol. 1, pp. 109–120, 1988.
D. B. West, ”Gossiping without duplicate transmissions,” SIAM Journal on Algebraic and Discrete Methods, vol. 3, pp. 418–419, 1982.
G. Fertin and A. Respaud, ”A survey on Kn¨odel graphs,” Discrete Applied Mathematics, vol. 137, no. 2, pp. 173–195, 2003.
R. Labahn, ”Kernels of minimum size gossip schemes,” Discrete Mathematics, vol. 143, pp. 99–139, 1995.
R. Labahn, ”Some minimum gossip graphs,” Networks, vol. 23, pp. 333–341, 1993.
G. Fertin and R. Labahn, ”Compounding of gossip graphs,” Networks, vol. 36, pp. 126–137, 2000.
A. Bavelas, ”Communication pattern in task-oriented groups,” Journal of the Acoustical Society of America, vol. 22, pp. 725–730, 1950.
W. Knödel, ”New gossips and telephones,” Discrete Mathematics, vol. 13, p. 95, 1975.
Z. Ho and M. Shigeno, ”New bounds on the minimum number of calls in failure-tolerant gossiping,” Networks, vol. 53, pp. 35–38, 2009.
K. A. Berman and M. Hawrylycz, ”Telephone problems with failures,” SIAM Journal on Algebraic and Discrete Methods, vol. 7, pp. 13–17, 1987.
R. W. Haddad, S. Roy, and A. A. Schaffer, ”On gossiping with faulty telephone lines,” SIAM Journal on Algebraic and Discrete Methods, vol. 8, pp. 439–445, 1987.
T. Hasunuma and H. Nagamochi, ”Improved bounds for minimum fault-tolerant gossip graphs,” in Lecture Notes in Computer Science, vol. 6986, pp. 203–214, 2011.
S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Listman, ”A survey of gossiping and broadcasting in communication networks,” Networks, vol. 18, pp. 319–349, 1988.
D. B. West, ”A class of solutions to the gossip problem,” Part I, Discrete Mathematics, vol. 39, no. 3, pp. 307–326, 1982; Part II, Discrete Mathematics, vol. 40, no. 1, pp. 87–113, 1982; Part III, Discrete Mathematics, vol. 40, no. 2–3, pp. 285–310, 1982.
A. Seress, ”Quick gossiping without duplicate transmissions,” Graphs and Combinatorics, vol. 2, pp. 363–381, 1986.
P. Fraigniaud, A. L. Liestman, and D. Soitoteau, ”Open problems,” Parallel Processing Letters, vol. 3, no. 4, pp. 507–524, 1993.
V. Hovnanyan, S. Poghosyan, and V. Poghosyan, ”New methods of construction of fault-tolerant gossip graphs,” in 2013 International Conference on Computer Science and Information Technologies, Revised Selected Papers, IEEE, pp. 1–5, 2013.
V. Hovnanyan, S. Poghosyan, and V. Poghosyan, ”Fault-tolerant gossip graphs based on wheel graphs,” Transactions of IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 42, pp. 43–53, 2014.
V. Hovnanyan, S. Poghosyan, and V. Poghosyan, ”Graph plotter: A software tool for the investigation of fault-tolerant gossip graphs,” in 2013 International Conference on Computer Science and Information Technologies (CSIT), pp. 20–22, 2013.
V. Hovnanyan, S. Poghosyan, and V. Poghosyan, ”Method of local interchange to investigate gossip problems,” Transactions of IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 40, pp. 5–12, 2013.
V. Hovnanyan, S. Poghosyan, and V. Poghosyan, ”Method of local interchange to investigate gossip problems: Part 2,” Transactions of IIAP of NAS RA, Mathematical Problems of Computer Science, vol. 41, pp. 15–22, 2014.
V. Hovnanyan, S. Poghosyan, and V. Poghosyan, ”Gossiping properties of the edgepermuted Knödel graphs,” in 2017 International Conference on Computer Science and Information Technologies (CSIT), IEEE, pp. 1–4, 2017.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Vahagn S. Poghosyan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
