Article

Broadcasting vs. mixing and information dissemination on Cayley graphs

Authors:

Robert Elsässer,

Thomas SauerwaldAuthors Info & Claims

STACS'07: Proceedings of the 24th annual conference on Theoretical aspects of computer science

Pages 163 - 174

Published: 22 February 2007 Publication History

Abstract

One frequently studied problem in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following randomized broadcasting protocol: At some time t an information r is placed at one of the nodes of a graph G. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of r to it.

First, we consider the relationship between randomized broadcasting and random walks on graphs. In particular, we prove that the runtime of the algorithm described above is upper bounded by the corresponding mixing time, up to a logarithmic factor. One key ingredient of our proofs is the analysis of a continuous-type version of the afore mentioned algorithm, which might be of independent interest. Then, we introduce a general class of Cayley graphs, including (among others) Star graphs, Transposition graphs, and Pancake graphs. We show that randomized broadcasting has optimal runtime on all graphs belonging to this class. Finally, we develop a new proof technique by combining martingale tail estimates with combinatorial methods. Using this approach, we show the optimality of our algorithm on another Cayley graph and obtain new knowledge about the runtime distribution on several Cayley graphs.

References

[1]

. Akers, D. Harel, and B. Krishnamurthy. The star graph: An attractive alternative to the n-cube. In Proc. of ICPP'87, pages 393-400, 1987.

[2]

S. Akers and B. Krishnamurthy. A group-theoretic model for symmetric innterconnection networks. In Proc. of ICPP'86, pages 555-565, 1986.

[3]

N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization, 2000.

[4]

I. Benjamini, N. Berger, C. Hoffmann, and E. Mossel. Mixing times of the biased card shuffling and the asymmetric exclusion process. Transactions of the American Mathematical Society, 357:3013-3029, 2005.

[5]

N. Biggs. Algebraic Graph Theory. Cambridge University Press, 1993.

[6]

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

[7]

F. Chung. Spectral Graph Theory, volume 92 of CBMS Regional conference series in mathematics. American Mathematical Society, 1997.

[8]

F. Chung and L. Lu. Concentration inequalities and martingale inequalities -- a survey. Internet Mathematics (to appear).

[9]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proc. of PODC'87, pages 1-12, 1987.

Digital Library

[10]

P. Diaconis. Group Representations in Probability and Statistics, volume 11. Lecture notes-Monograph Series, 1988.

[11]

R. Diekmann, A. Frommer, and B. Monien. Efficient schemes for nearest neighbor load balancing. Parallel Computing, 25(7):789-812, 1999.

Digital Library

[12]

R. Elsässer and T. Sauerwald. On randomized broadcasting in star graphs. In Proc. of WG'05, pages 307-318, 2005.

Digital Library

[13]

R. Elsässer and T. Sauerwald. On the runtime and robustness of randomized broadcasting. In Proc. of ISAAC'06, pages 349-358, 2006.

Digital Library

[14]

U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random Structures and Algorithm, I(4):447-460, 1990.

Digital Library

[15]

L. Gasieniec and A. Pelc. Adaptive broadcasting with faulty nodes. Parallel Computing, 22:903-912, 1996.

Digital Library

[16]

M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed. Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms and Combinatorics, 1991.

[17]

T. Hagerup and C. Rüb. A guided tour of chernoff bounds. Information Processing Letters, 36(6):305-308, 1990.

Digital Library

[18]

J. Hromkovi?c, R. Klasing, A. Pelc, P. Ruzicka, and W. Unger. Dissemination of Information in Communication Networks. Springer, 2005.

Digital Library

[19]

F. Leighton, B. Maggs, and R. Sitamaran. On the fault tolerance of some popular bounded-degree networks. In Proc. of FOCS'92, pages 542-552, 1992.

Digital Library

[20]

A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.

[21]

B. Pittel. On spreading rumor. SIAM Journal on Applied Mathematics, 47(1):213- 223, 1987.

Digital Library

[22]

A. Sinclair and M. Jerrum. Approximate counting, uniform generation, and rapidly mixing markov chains. Inform. and Comput., 82:93-113, 1989.

Digital Library

[23]

D. Wilson. Mixing times of lozenge tiling and card shuffling markov chains. Annals of Applied Probability, 14:274-325, 2004.

Cited By

Giakkoupis GNazari YWoelfel PGiakkoupis G(2016)How Asynchrony Affects Rumor Spreading TimeProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933117(185-194)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933117
Berenbrink PElsässer RFriedetzky T(2016)Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systemsDistributed Computing10.1007/s00446-016-0264-029:5(317-339)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00446-016-0264-0
Guo ZSun HIndyk P(2015)Gossip vs. Markov chains, and randomness-efficient rumor spreadingProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722158(411-430)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722158
Show More Cited By

Index Terms

Broadcasting vs. mixing and information dissemination on Cayley graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Meyniel Extremal Families of Abelian Cayley Graphs
Abstract
We study the game of Cops and Robbers, where cops try to capture a robber on the vertices of a graph. Meyniel’s conjecture states that for every connected graph G on n vertices, the cop number of G is upper bounded by $O (\sqrt{n})$ . That is, for every ... $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ $_{}$ $_{}$ $^{}$
Broadcasting in Harary-Like Graphs
CSE '14: Proceedings of the 2014 IEEE 17th International Conference on Computational Science and Engineering

Broadcasting is an information dissemination problem in a connected graph in which one vertex, called the originator, must distribute a message to all other vertices by placing a series of calls along the edges of the graph. Every time the informed ...
Broadcasting on cactus graphs

Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between neighboring vertices, where one call requires one unit of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

STACS'07: Proceedings of the 24th annual conference on Theoretical aspects of computer science

February 2007

707 pages

ISBN:9783540709176

Editors:
Wolfgang Thomas
RWTH Aachen, Aachen, Germany
,
Pascal Weil
Laboratoire Bordelais de Recherche en Informatique, Université de Bordeaux, Talence Cedex, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 22 February 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Giakkoupis GNazari YWoelfel PGiakkoupis G(2016)How Asynchrony Affects Rumor Spreading TimeProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933117(185-194)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2933057.2933117
Berenbrink PElsässer RFriedetzky T(2016)Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systemsDistributed Computing10.1007/s00446-016-0264-029:5(317-339)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00446-016-0264-0
Guo ZSun HIndyk P(2015)Gossip vs. Markov chains, and randomness-efficient rumor spreadingProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722158(411-430)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722158
(2014)The worst case behavior of randomized gossip protocolsTheoretical Computer Science10.5555/2945717.2945734560:P2(108-120)Online publication date: 4-Dec-2014
https://dl.acm.org/doi/10.5555/2945717.2945734
Giakkoupis GChekuri C(2014)Tight bounds for rumor spreading with vertex expansionProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634133(801-815)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634133
Doerr BHuber ALevavi A(2013)Strong robustness of randomized rumor spreading protocolsDiscrete Applied Mathematics10.1016/j.dam.2012.10.014161:6(778-793)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.dam.2012.10.014
Giakkoupis GSauerwald T(2012)Rumor spreading and vertex expansionProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095245(1623-1641)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095245
Sauerwald TStauffer ARandall D(2011)Rumor spreading and vertex expansion on regular graphsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133073(462-475)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133073
Giakkoupis GWoelfel PRandall D(2011)On the randomness requirements of rumor spreadingProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133072(449-461)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133072
Doerr BFouz M(2011)Asymptotically optimal randomized rumor spreadingProceedings of the 38th international conference on Automata, languages and programming - Volume Part II10.5555/2027223.2027274(502-513)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027223.2027274
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents