Fault-tolerant Gossip Graphs Based on Wheel Graphs
Keywords:
Gossip, Information dissemination, Fault-tolerant gossipingAbstract
The gossip problem (telephone problem) is an information dissemination problem where each of n nodes of a communication network has a unique piece of information that must be transmitted to all the other nodes using two-way communications (telephone calls) between the pairs of nodes. Upon a call between the given two nodes, they exchange the whole information known to them at that moment. In this paper, we investigate the k-fault-tolerant gossip problem, which is a generalization of the gossip problem, where at most k arbitrary faults of calls are allowed. The problem is to find the minimal number of calls ¿(n; k) needed to guarantee the spread of whole information. We constructed a k-fault-tolerant gossip scheme (sequences of calls) to find the upper bounds of ¿(n; k), which improves the previously known results for some particular small values of n and k.
References
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 Discrete Methods, vol. 2, pp. 13-18, 1981.
A. Hajnal, E.C. Milner and E. Szemeredi, “A cure for the telephone disease", Canadian Mathematical Bulletin., vol. 15, pp. 447-450, 1972.
T. Tijdeman, “On a telephone problem", Nieuw Archief voor Wiskunde vol. 3, pp. 188-192, 1971.
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 Discrete Methods, vol. 3, pp. 418-419, 1982.
G. Fertin and A. Respaud," A survey on Knödel 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. Knodel, “New gossips and telephones", Discrete Mathematics, vol. 13, pp. 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 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 Discrete Methods, vol. 8, pp. 439-445, 1987.
T. Hasunama and H. Nagamochi, “Improved bounds for minimum fault-tolerant gossip graphs", Lecture Notes in Computer Science, vol. 6986, pp. 203-214, 2011.
S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, “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:
A. Seress, “Quick Gossiping without duplicate transmissions", Graphs and Combinatorics, vol. 2, pp. 363-381, 1986.
P. Fraigniaud, A. L. Liestman and D. Soiteau, “Open problems", Parallel Processing Letters, vol. 3, no. 4, pp. 507-524, 1993.
A. Pelc, “Fault-tolerant broadcasting and gossiping in communication networks", Networks, vol. 28, pp. 143-156, 1996.
K. Menger, “Zur allgemeinen Kurventheorie", Fund. Math. vol. 10, pp. 96-115, 1927.
D. B. West, A class of solutions to the gossip problem" ; part II, Disc. Math., vol. 40, no. 1, pp. 87-113, 1982
D. B. West, A class of solutions to the gossip problem" ; part III, Discrete Mathematics, vol. 40, no. 2-3, pp. 285-310, 1982.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
