Abstract
Circulant graphs are regular graphs based on Cayley graphs defined on the Abelian group \(\mathbb{Z}_{n}\). They are popular network topologies that arise in distributed computing.
Using number theoretical tools, we first prove two main results for random directed k-regular circulant graphs with n vertices, when n is sufficiently large and k is fixed. First, for any fixed ε>0, n=p prime and L≥p 1/k(logp)1+1/k+ε, walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm that for almost all undirected 2r-regular circulant graphs finds a vertex bisector and an edge bisector, both of size less than n 1−1/r+o(1). We then prove that the latter result also holds for all (rather than for almost all) 2r-regular circulant graphs with n=p, prime, vertices, while, in general, it does not hold for composite n.
Using the bisection results, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. We introduce generic distributed algorithms to solve the gossip problem in any circulant graphs. We illustrate the efficiency of these algorithms by giving nearly matching upper bounds of the number of rounds required by these algorithms in the vertex-disjoint and the edge-disjoint paths communication models in particular circulant graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ádám, A.: Research problem 2–10. J. Comb. Theory 3, 393 (1967)
Alon, N., Avin, C., Kouck, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Comb. Probab. Comput. 20, 481–502 (2011)
Amir, G., Gurel-Gurevich, O.: The diameter of a random Cayley graph of \(\mathbb{Z}_{q}\). In: Groups Complex. Crypto, vol. 2, pp. 59–65 (2010)
Annexstein, F., Baumslag, M.: On the diameter and bisector size of Cayley graphs. Math. Syst. Theory 26, 271–291 (1993)
Attiya, H., van Leeuwen, J., Santoro, N., Zaks, S.: Efficient elections in chordal ring networks. Algorithmica 4, 437–446 (1989)
Barrière, L., Fàbrega, J.: Edge-bisection of chordal rings. In: Proc. 25th MFCS. LNCS, pp. 162–171. Springer, Berlin (2004)
Barrière, L., Cohen, J., Mitjana, M.: Gossiping in chordal rings under the line model. Theor. Comput. Sci. 264, 53–64 (2001)
Bermond, J.-C., Comellas, F., Hsu, D.F.: Distributed loop computer networks: a survey. J. Parallel Distrib. Comput. 24, 2–10 (1995)
Blackburn, S.R.: Node bisectors of Cayley graphs. Math. Syst. Theory 29, 589–598 (1996)
Cai, J.-Y., Havas, G., Mans, B., Nerurkar, A., Seifert, J.-P., Shparlinski, I.: On routing in circulant graphs. In: Proc. 5th COCOON. LNCS, pp. 370–378. Springer, Berlin (1999)
Elspas, B., Turner, J.: Graphs with circulant adjacency matrices. J. Comb. Theory 9, 229–240 (1970)
Hamidoune, Y.O., Serra, O.: On small cuts separating an Abelian Cayley graph into two equal parts. Math. Syst. Theory 29, 407–409 (1996)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Clarendon, New York (1979)
Hromkovič, J., Klasing, R., Stöhr, E.A., Wagener, H.: Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs. Inf. Comput. 123, 17–28 (1995)
Hromkovič, J., Klasing, R., Stöhr, E.A.: Dissemination of information in generalized communication modes. Comput. Artif. Intell. 15, 295–318 (1996)
Hromkovič, J., Klasing, R., Unger, W., Wagener, H.: Optimal algorithms for broadcast and gossip in the edge-disjoint path modes. Inf. Comput. 133, 1–33 (1997)
Iwaniec, H., Kowalski, E.: Analytic Number Theory. Am. Math. Soc., Providence (2004)
Klasing, R.: The relationship between the gossip complexity in the vertex-disjoint paths mode and the vertex bisection width. Discrete Appl. Math. 83, 229–246 (1998)
Laczkovich, M.: Discrepancy estimates for sets with small boundary. Studia Sci. Math. Hung. 30, 105–109 (1995)
Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo (1992)
Lovász, L.: Random Walks on Graphs: a Survey. Combinatorics, Paul Erdös Is Eighty, pp. 1–46. Bolyai Soc., Hungary (1993)
Mans, B.: Optimal distributed algorithms in unlabeled tori and chordal rings. J. Parallel Distrib. Comput. 46, 80–90 (1997)
Mans, B., Shparlinski, I.E.: Bisecting and gossiping in circulant graphs. In: Proc. 6th LATIN. LNCS, pp. 589–598. Springer, Berlin (2004)
Mans, B., Shparlinski, I.E.: Random walks and bisections in random circulant graphs. In: Proc. 10th LATIN. LNCS, pp. 542–555. Springer, Berlin (2012)
Mans, B., Pappalardi, F., Shparlinski, I.: On the spectral Ádám property for circulant graphs. Discrete Math. 254, 309–329 (2002)
Marklof, J., Strombergsson, A.: Diameters of random circulant graphs. Combinatorica. Available from: http://arxiv.org/abs/1103.3152 (2011, to appear)
Muzychuk, M.: On Ádám’s conjecture for circulant graphs. Discrete Math. 167/168, 497–510 (1997). Erratum: Discrete Math. 176, 285–298 (1997)
Narayanan, L., Opatrny, J., Sotteau, D.: All-to-all optical routing in optimal chordal rings of degree 4. Algorithmica 29, 396–409 (2001)
Niederreiter, H., Wills, J.M.: Diskrepanz und Distanz von Massen bezuglich konvexer und Jordanscher Mengen. Math. Z. 144, 125–134 (1975)
Opatrny, J.: Uniform multi-hop all-to-all optical routings in rings. Theor. Comput. Sci. 297(1–3), 385–397 (2003)
Acknowledgements
The authors are very grateful to the referees for constructive and thorough comments.
The research of B.M. by Australian Research Council Grant DP110104560, and that of I.E.S. by Australian Research Council Grants DP130100237 and Macquarie University Grant MQRDG1465020.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mans, B., Shparlinski, I. Random Walks, Bisections and Gossiping in Circulant Graphs. Algorithmica 70, 301–325 (2014). https://doi.org/10.1007/s00453-013-9810-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-013-9810-3