Top

Distributed Computing

Published in:

01-10-2016

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

Authors: Petra Berenbrink, Robert Elsässer, Tom Friedetzky

Published in: Distributed Computing | Issue 5/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS ’00, 2000). In the phone call model, in every time step, each node calls a randomly chosen neighbour to establish a communication channel to this node. The communication channels can then be used bi-directionally to transmit messages. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node required to broadcast a message efficiently decreases exponentially. Formally, we present an algorithm that has time complexity \(O(\log n)\) and uses \(O(n\log \log n)\) transmissions per message. In contrast, we show for the standard model that every distributed algorithm in a restricted address-oblivious model that broadcasts a message in time \(O(\log n)\) requires \(\Omega (n \log n{/} \log d)\) message transmissions. Our algorithm efficiently handles limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.

next article Randomized mutual exclusion on a multiple access channel

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

By w.h.p. or with high probability we mean with a probability of at least \(1-1{/}n^{\Omega (1)}\).

Note that in a sequentialised version of our model, in each step every node v i.u.r. chooses one neighbour from the set of neighbours not chosen by v during the last three time steps [13]. Clearly, four steps of this sequentialised model can be viewed as one step in the model considered in this paper, and thus, our results can easily be extended to the sequentialised version of our model.

A.a.s. means almost always surely, i.e., with probability \(1-\log ^{-\Omega (1)} n\)

To apply this result for simple graphs, the degree should be independent of n. For higher degrees, some more probabilistic analysis is needed which is omitted in the lower bound case.

Bollobás, B.: Random Graphs. Academic Press, Cambridge (1985)MATH

Botros, S.M., Waterhause, S.R.: Search in JXTA and other distributed networks. In: Proceedings of the P2P’01, pp. 30–35 (2001)

Boyd, S.P., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE Trans. Inf. Theory 52(6), 2508–2530 (2006). doi:10.1109/TIT.2006.874516 MathSciNetCrossRefMATH

Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–507 (1952)MathSciNetCrossRefMATH

Cooper, C., Dyer, M., Greenhill, C.: Sampling regular graphs and a peer-to-peer network. In: Proceedings of the SODA ’05, pp. 980–988 (2005)

Cooper, C., Frieze, A.: The cover time of sparse random graphs. Random Struct. Algorithms 30, 1–16 (2007)MathSciNetCrossRefMATH

Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: Proceedings of the PODC ’87, pp. 1–12 (1987)

Doerr, B., Fouz, M., Friedrich, T.: Social networks spread rumors in sublogarithmic time In: Proceedings of the STOC ’11, pp. 21–30 (2011)

Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: Proceedings of the SODA ’08, pp. 773–781 (2008)

10.

Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)CrossRefMATH

11.

Elsässer R.: On the communication complexity of randomized broadcasting in random-like graphs. In: Proceedings of the SPAA ’06, pp. 148–157 (2006)

12.

Elsässer R., Sauerwald T., Broadcasting vs. mixing and information dissemination on Cayley graphs. In: Proceedings of the STACS ’07, pp. 163–174 (2007)

13.

Elsässer R., Sauerwald, T.: The power of memory in randomized broadcasting. In: Proceedings of the SODA ’08, pp. 290–227 (2008)

14.

Erdős, P., Rényi, A.: On random graphs I. Publ. Math. Debr. 6, 290–297 (1959)MATH

15.

Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960)MathSciNetMATH

16.

Feder, T., Guetz, A., Mihail, M., Saberi, A.: A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks. In: Proceedings of the FOCS ’06, pp. 69–76 (2006)

17.

Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. Random Struct. Algorithms 1(4), 447–460 (1990)MathSciNetCrossRefMATH

18.

Friedman, J.: A proof of Alon’s second eigenvalue conjecture. In: Proceedings of the STOC ’03, pp. 720–724 (2003)

19.

Frieze, A.M., Grimmett, G.R.: The shortest-path problem for graphs with random arc-lengths. Discret. Appl. Math. 10, 57–77 (1985)MathSciNetCrossRefMATH

20.

Fountoulakis, N., Panagiotou, K.: Rumor spreading on random regular graphs and expanders. In: Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM ’10), pp. 560–573 (2010)

21.

Gnutella: The Gnutella Protocol Specification v.0.4, Patrick Kirk (2003). http://rfc-gnutella.sourceforge.net/developer/stable/index.html

22.

Hagerup, T., Rüb, C.: A guided tour of Chernoff bounds. Inf. Process. Lett. 36(6), 305–308 (1990)MathSciNetCrossRefMATH

23.

Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. AMS 43(4), 439–561 (2006)MathSciNetCrossRefMATH

24.

Jagannathan, S., Pandurangan, G., Srinivasan, S.: Query protocols for highly resilient peer-to-peer networks. In: Proceedings of the ISCA PDCS ’06, pp. 247–252 (2006)

25.

Karp, R., Schindelhauer, C., Shenker, S., Vöcking B.: Randomized rumor spreading. In Proceedings of the FOCS ’00, pp. 565–574 (2000)

26.

Kempe, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. In: Proceedings of the 33rd Symposium on the Theory of Computing (STOC), pp. 163–172 (2001)

27.

Law, C., Siu, K.-Y.: Distributed construction of random expander networks. In: Proceedings of the 22nd INFOCOM, pp. 2133–2143 (2003)

28.

Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)CrossRefMATH

29.

Mahlmann, P., Schindelhauer, C.: Distributed random digraph transformations for peer-to-peer networks. In: Proceedings of the SPAA ’06, pp. 308–317 (2006)

30.

McKay, B.D., Wormald, N.C.: Asymptotic enumeration by degree sequence of graphs with degrees o(sqrt(n)). Combinatorica 11, 369–382 (1991)MathSciNetCrossRefMATH

31.

Newman, M.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003)MathSciNetCrossRefMATH

32.

Pandurangan, G., Raghavan, P., Upfal, E.: Building low-diameter peer-to-peer networks. In: Proceedings of the FOCS ’01, pp. 492–499 (2001)

33.

Pittel, B.: On spreading a rumor. SIAM J. Appl. Math. 47(1), 213–223 (1987)MathSciNetCrossRefMATH

34.

Sauerwald, T.: On mixing and edge expansion properties in randomized broadcasting. In: Proceedings of the ISAAC’07, pp. 196–207 (2007)

Title: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
Authors: Petra Berenbrink
Robert Elsässer
Tom Friedetzky
Publication date: 01-10-2016
Publisher: Springer Berlin Heidelberg
Published in: Distributed Computing / Issue 5/2016
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-016-0264-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2016

Randomized mutual exclusion on a multiple access channel

Distributed algorithms for barrier coverage using relocatable sensors

Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

The computability of relaxed data structures: queues and stacks as examples

Premium Partner