Skip to main content
SpringerLink
Log in
Book cover

Future of Information and Communication Conference

FICC 2019: Advances in Information and Communication pp 154–163Cite as

Existence of an Optimal Perpetual Gossiping Scheme for Arbitrary Networks

  • Conference paper
  • First Online:

  • 1297 Accesses

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 69))

Abstract

Gossiping is a problem in which a peer-to-peer network must disperse the information held by each machine to all other machines in the minimum number of communication steps. In perpetual gossiping, new information may be introduced to any machine at any time, and the objective is to find a perpetual communication scheme which guarantees that new information will be completely dispersed in optimal time. The basic gossiping problem has a well-known solution, but the perpetual gossiping extension has defied a general solution. Additionally, prior to this paper, it has not been shown that there is even a means to arrive at an optimal solution on a case-by-case basis. Attempts at optimization have thus far taken place in a series of progressive refinements, broadening the scope of network topologies for which optimal or near-optimal solutions are known. This paper proceeds from the opposite direction, by demonstrating an algorithm which is guaranteed to find an optimal perpetual gossiping scheme for an arbitrary graph. The network model is then generalized so as to apply to a broader class of communication schemes.

This is a preview of subscription content, log in via an institution.

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Learn about institutional subscriptions

References

  1. Baker, B., Shostak, R.: Gossips and telephones. Discret. Math. 2(3), 191–193 (1972). https://doi.org/10.1016/0012-365X(72)90001-5

    Article  MathSciNet  MATH  Google Scholar 

  2. Bumby, R.T.: A problem with telephones. SIAM J. Algebraic Discret. Methods 2(1), 13–18 (1981)

    Article  MathSciNet  Google Scholar 

  3. Chang, G.J., Tsay, Y.J.: The partial gossiping problem. Discret. Math. 148(1), 9–14 (1996). https://doi.org/10.1016/0012-365X(94)00257-J

    Article  MathSciNet  MATH  Google Scholar 

  4. van Ditmarsch, H., van Eijck, J., Pardo, P., Ramezanian, R., Schwarzentruber, F.: Epistemic protocols for dynamic gossip. J. Appl. Logic 20, 1–31 (2017). https://doi.org/10.1016/j.jal.2016.12.001

    Article  MathSciNet  MATH  Google Scholar 

  5. Fertin, G.: A study of minimum gossip graphs. Discret. Math. 215(1–3), 33–57 (2000)

    Article  MathSciNet  Google Scholar 

  6. Fertin, G., Labahn, R., et al.: Compounding of gossip graphs. Networks 36(2), 126–137 (2000)

    Article  MathSciNet  Google Scholar 

  7. Hajnal, A., Milner, E.C., Szemerédi, E.: A cure for the telephone disease. Canad. Math. Bull 15(3), 447–450 (1972)

    Article  MathSciNet  Google Scholar 

  8. Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks 18(4), 319–349 (1988)

    Article  MathSciNet  Google Scholar 

  9. Khuller, S., Kim, Y.A., Wan, Y.C.J.: On generalized gossiping and broadcasting. J. Algorithms 59(2), 81–106 (2006). https://doi.org/10.1016/j.jalgor.2005.01.002

    Article  MathSciNet  MATH  Google Scholar 

  10. Knoedel, W.: New gossips and telephones. Discret. Math. 13(1), 95 (1975). https://doi.org/10.1016/0012-365X(75)90090-4

    Article  MathSciNet  MATH  Google Scholar 

  11. Krumme, D.W.: Reordered gossip schemes. Discret. Math. 156(1), 113–140 (1996). https://doi.org/10.1016/0012-365X(94)00302-Y

    Article  MathSciNet  MATH  Google Scholar 

  12. Labahn, R., Hedetniemi, S.T., Laskar, R.: Periodic gossiping on trees. Discret. Appl. Math. 53(1), 235–245 (1994). https://doi.org/10.1016/0166-218X(94)90187-2

    Article  MathSciNet  MATH  Google Scholar 

  13. Liestman, A.L., Richards, D.: Perpetual gossiping. Parallel Process. Lett. 3(04), 347–355 (1993)

    Article  MathSciNet  Google Scholar 

  14. Scott, A.D.: Better bounds for perpetual gossiping. Discret. Appl. Math. 75(2), 189–197 (1997)

    Article  MathSciNet  Google Scholar 

  15. Tijdeman, R.: On a telephone problem. Nieuw Archief voor Wiskunde 3(19), 188–192 (1971)

    MathSciNet  MATH  Google Scholar 

  16. Tsay, Y.J., Chang, G.J.: The exact gossiping problem. Discret. Math. 163(1), 165–172 (1997). https://doi.org/10.1016/S0012-365X(96)00317-2

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. George Mason University, Fairfax, VA, 22030, USA

    Ivan Avramovic & Dana S. Richards

Authors
  1. Ivan Avramovic
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dana S. Richards
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ivan Avramovic .

Editor information

Editors and Affiliations

  1. Faculty of Science and Engineering, Saga University, Saga, Japan

    Kohei Arai

  2. The Science and Information (SAI) Organization, Bradford, UK

    Rahul Bhatia

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Avramovic, I., Richards, D.S. (2020). Existence of an Optimal Perpetual Gossiping Scheme for Arbitrary Networks. In: Arai, K., Bhatia, R. (eds) Advances in Information and Communication. FICC 2019. Lecture Notes in Networks and Systems, vol 69. Springer, Cham. https://doi.org/10.1007/978-3-030-12388-8_11

Download citation

Publish with us

Policies and ethics

Search

Navigation