Adibi, Aria (2021) Broadcasting in Hyper-cylinder graphs. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
1MBAdibi_MCompSc_F2021.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
Broadcasting in computer networking means the dissemination of information, which is known initially only at some nodes, to all network members. The goal is to inform every node in the minimal time possible. There are few models for broadcasting; the simplest and the historical model is called the Classical model. In the Classical model, dissemination happens in synchronous rounds, wherein a node may only inform one of its neighbors. The broadcast question is: What is the minimum number of rounds needed for broadcasting, and what broadcast scheme achieves it?
For general graphs, these questions are NP-hard, and it is known to be at least 3 - ε inapproximable for any real ε > 0. Even for some very restricted classes of graphs, the questions remain as an NP-hard problem. Little is known about broadcasting in restricted graphs, and only a few classes have a polynomial solution.
Parallel and distributed computing is one of the important domains which relies on efficient broadcasting. Hypercube and torus are the most used network topology in this domain. The widespread use is not only due to their simplicity but also is for their efficiency and high robustness (e.g., fault tolerance) while having an acceptable number of links. In this thesis, it is observed that the Cartesian product of a number of path and cycle graphs produces a valuable set of topologies, we called hyper-cylinders, which contain hypercube and Torus as well. Any hyper-cylinder shares many of the beneficial features of hypercube and torus and might be a suitable substitution in some cases. Some hyper-cylinders are also similar to other practically used topologies such as cube-connected cycles. In this thesis, the effect of the Cartesian product on broadcasting and broadcasting of hyper-cylinders under the Classical and Messy models is studied. This will add a valuable class of graphs to the limited classes of graphs which have a polynomially computable broadcast time. In the end, the relation between worst-case originators and diameters in trees is studied, which may help in the broadcast study of a larger class of graphs where any tree is allowed instead of a path in the Cartesian product.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Adibi, Aria |
| Institution: | Concordia University |
| Degree Name: | M. Comp. Sc. |
| Program: | Computer Science |
| Date: | 25 August 2021 |
| Thesis Supervisor(s): | Harutyunyan, Hovhannes A. |
| Keywords: | Broadcasting, Hyper-cylinder |
| ID Code: | 988972 |
| Deposited By: | Aria Adibi |
| Deposited On: | 29 Nov 2021 16:18 |
| Last Modified: | 29 Nov 2021 16:18 |
References:
[1] Dennis Abts. “The Cray XT4 and Seastar 3-D torus interconnect”. In: (2011).[2] Narasimha R Adiga, Matthias A Blumrich, Dong Chen, Paul Coteus, Alan Gara, Mark E Giampapa, Philip Heidelberger, Sarabjeet Singh, Burkhard D Steinmacher- Burow, Todd Takken, et al. “Blue Gene/L torus interconnection network”. In: IBM Journal of Research and Development 49.2.3 (2005), pp. 265–276.
[3] R Ahlswede, H Haroutunian, and L Khachatrian. Messy broadcasting in networks, Communications and Cryptography, eds. RE Blahut, DJ Costello Jr., U. Mauter, and T. Mittelholzer. 1994.
[4] Stefan Arnborg, Jens Lagergren, and Detlef Seese. “Easy problems for tree-decomposable graphs”. In: Journal of Algorithms 12.2 (1991), pp. 308–340.
[5] Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. “A tradeoff between information and communication in broadcast protocols”. In: Aegean Workshop on Computing. Springer. 1988, pp. 369–379.
[6] Anindo Bagchi and S. Louis Hakimi. “Data transfers in broadcast networks”. In: IEEE Computer Architecture Letters 41.07 (1992), pp. 842–847.
[7] Anindo Bagchi, S. Louis Hakimi, and Edward F. Schmeichel. “Gossiping in a distributed network”. In: IEEE transactions on computers 42.2 (1993), pp. 253–256.
[8] Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. “Multicasting in heterogeneous networks”. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998, pp. 448–453.
[9] Reuven Bar-Yehuda, Amos Israeli, and Alon Itai. “Multiple communication in multihop radio networks”. In: SIAM Journal on Computing 22.4 (1993), pp. 875–887.
[10] René Beier and Jop F. Sibeyn. “A powerful heuristic for telephone gossiping”. In:
SIROCCO 7, Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity, Laquila, Italy, June 20-22, 2000. Ed. by Michele Flammini, Enrico Nardelli, Guido Proietti, and Paul G. Spirakis. Carleton Scientific, 2000, pp. 17–35.
[11] Amir Ben-Dor, Shai Halevi, and Assaf Schuster. On greedy hot-potato routing. Laboratory for Parallel Computing Research, Technion-Israel Institute of . . ., 1993.
[12] Jean-Claude Bermond, Pierre Fraigniaud, and Joseph G Peters. “Antepenultimate broadcasting”. In: Networks 26.3 (1995), pp. 125–137.
[13] Jean-Claude Bermond, Pavol Hell, Arthur L Liestman, and Joseph G Peters. “Broadcasting in bounded degree graphs”. In: SIAM Journal on Discrete Mathematics 5.1 (1992), pp. 10–24.
[14] Jean-Claude Bermond and Claudine Peyrat. “Broascasting in de Bruijn networks”. In: Congressus numerantium 66 (1988), pp. 283–292.
[15] Jean-Claude Bermond and Claudine Peyrat. “De Bruijn and Kautz networks: a competitor for the hypercube?” In: First European Workshop on Hypercube and Distributed Computers. Elsevier. 1989, pp–279.
[16] Dimitri P Bertsekas, C Özveren, George D Stamoulis, Paul Tseng, and John N. Tsit- siklis. “Optimal communication algorithms for hypercubes”. In: Journal of Parallel and Distributed Computing 11.4 (1991), pp. 263–275.
[17] Puspal Bhabak and Hovhannes A. Harutyunyan. “Constant Approximation for Broadcasting in k-cycle Graph”. In: Conference on Algorithms and Discrete Applied Mathematics. Springer. 2015, pp. 21–32.
[18] Laxmi N. Bhuyan and Dharma P. Agrawal. “Generalized hypercube and hyperbus structures for a computer network”. In: IEEE Computer Architecture Letters 33.04 (1984), pp. 323–333.
[19] Luc Bomans and Dirk Roose. “Communication benchmarks on the iPSC/2”. In:
Proceedings of the First European Workshop on Hypercube and Distributed Computers. 1989, pp. 93–103.
[20] Jehoshua Bruck, Robert Cypher, and Ching-Tien Ho. Multiple message broadcasting with generalized Fibonacci trees. IEEE, 1992.
[21] Renato M Capocelli, Luisa Gargano, and Ugo Vaccaro. “Time bounds for broadcasting in bounded degree graphs”. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer. 1989, pp. 19–33.
[22] MajaCˇevnikandJanezŽerovnik “Broadcasting on cactus graphs”.In: Journal of Combinatorial Optimization 33.1 (2017), pp. 292–316.
[23] T Champion and B Tourancheau. “Tnode: user document”. In: Technical Report LIP-IMAG 89-02. Ecole Normale Supérieure de Lyon France, 1989.
[24] Siu-Cheung Chau and Arthur L Liestman. “Constructing minimal broadcast networks”. In: J. Combin. Inform. Syst. Sci 10 (1985), pp. 110–122.
[25] X Chen. “An upper bound for the broadcast function B (n), Chinese J”. In: Computers 13 (1990), pp. 605–611.
[26] Edward Chow, Herbert Madan, John Peterson, Dirk Grunwald, and Daniel Reed. “Hyperswitch network for the hypercube computer”. In: ACM SIGARCH Computer Architecture News 16.2 (1988), pp. 90–99.
[27] Israel Cidon and Inder S Gopal. “Paris: An approach to integrated high-speed private networks”. In: International Journal of Digital & Analog Cabled Systems 1.2 (1988), pp. 77–85.
[28] D Clark, B Davie, D Farber, I Gopal, and B Kadaba. “D, Sincoskie, J. Smith, and D. Tennenhouse, The AURORA gigabit testbed”. In: Computer Networks and ISDN (1991).
[29] EJ Cockayne and ST Hedetniemi. A conjecture concerning broadcasting in m- dimensional grid graphs. Tech. rep. Technical Report CS-TR-78-14, University of Oregon, 1978.
[30] Francesc Comellas, Hovhannes A. Harutyunyan, and Arthur L Liestman. “Messy broadcasting in multidimensional directed tori”. In: Journal of Interconnection Networks 4.01 (2003), pp. 37–51.
[31] Kris Coolsaet, H De Meyer, and Veerle Fack. “Optimal algorithms for total ex- change without buffering on the hypercube”. In: BIT Numerical Mathematics 32.4 (1992), pp. 559–569.
[32] David Culler, Richard Karp, David Patterson, Abhijit Sahay, Klaus Erik Schauser, Eunice Santos, Ramesh Subramonian, and Thorsten Von Eicken. “LogP: Towards a realistic model of parallel computation”. In: Proceedings of the fourth ACM SIG- PLAN symposium on Principles and practice of parallel programming. 1993, pp. 1– 12.
[33] William J Dally. “Performance analysis of k-ary n-cube interconnection networks”. In: IEEE transactions on Computers 39.06 (1990), pp. 775–785.
[34] William J Dally, Andrew Chien, Stuart Fiske, Waldemar Horwat, and John Keen. The J-machine: A fine grain concurrent computer. Tech. rep. Massachusetts inst of tech Cambridge microsystems research enter, 1989.
[35] Michael J Dinneen, Michael R Fellows, and Vance Faber. “Algebraic constructions of efficient broadcast networks”. In: International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes. Springer. 1991, pp. 152–158.
[36] Michael J Dinneen, Jose A Ventura, Mark C Wilson, and Golbon Zakeri. “Compound constructions of broadcast networks”. In: Discrete applied mathematics 93.2- 3 (1999), pp. 205–232.
[37] S. Djelloul. “Etudes de certains rCseaux d’interconnexion: structures et communi- cations”. PhD thesis. Paris-Sud, Orsay, 1992.
[38] Michael Elkin and Guy Kortsarz. “Sublogarithmic approximation for telephone multicast: path out of jungle.” In: SODA. Vol. 3. 2003, pp. 76–85.
[39] Michael Elkin and Guy Kortsarz. “A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem”. In: SIAM journal on Computing 35.3 (2005), pp. 672–689.
[40] AM Farley and ST Hedetniemi. “Broadcasting in grid graphs”. In: Proc. 9th SE Conf. Combinatorics, Graph Theory, and Computing, Utilitas Mathematica. 1978, pp. 275–288.
[41] Arthur Farley, Stephen Hedetniemi, Sandra Mitchell, and Andrzej Proskurowski. “Minimum broadcast graphs”. In: Discrete Mathematics 25.2 (1979), pp. 189–193.
[42] Arthur M Farley and Andrzej Proskurowski. Broadcasting: Between whispering and shouting. University of Oregon. Department of Computer and Information Science, 1989.
[43] Uriel Feige, David Peleg, Prabhakar Raghavan, and Eli Upfal. “Randomized broadcast in networks”. In: Random Structures & Algorithms 1.4 (1990), pp. 447–460.
[44] Pierre Fraigniaud. “Complexity analysis of broadcasting in hypercubes with restricted communication capabilities”. In: Journal of Parallel and Distributed Computing 16.1 (1992), pp. 15–26.
[45] Pierre Fraigniaud and Emmanuel Lazard. “Methods and problems of communication in usual networks”. In: Discrete Applied Mathematics 53.1-3 (1994), pp. 79– 133.
[46] Pierre Fraigniaud and Emmanuel Lazard. “Methods and problems of communication in usual networks”. In: Discrete Applied Mathematics 53.1-3 (1994), pp. 79– 133.
[47] Pierre Fraigniaud and Sandrine Vial. “Approximation algorithms for broadcasting and gossiping”. In: Journal of Parallel and Distributed Computing 43.1 (1997), pp. 47–55.
[48] Pierre Fraigniaud and Sandrine Vial. “Comparison of heuristics for one-to-all and all-to-all communications in partial meshes”. In: Parallel Processing Letters 9.01 (1999), pp. 9–20.
[49] Matthias Függer, Thomas Nowak, and Kyrill Winkler. “On the radius of nonsplit graphs and information dissemination in dynamic networks”. In: Discrete Applied Mathematics 282 (2020), pp. 257–264.
[50] Luisa Gargano and Ugo Vaccaro. “On the construction of minimal broadcast networks”. In: Networks 19.6 (1989), pp. 673–689.
[51] Jonathan L Gross, Jay Yellen, and Ping Zhang. Handbook of graph theory. CRC press, 2013.
[52] András Hajnal, Eric C Milner, and Endre Szemerédi. “A cure for the telephone disease”. In: Canadian Mathematical Bulletin 15.3 (1972), pp. 447–450.
[53] Hovhannes A. Harutyunyan, George Laza, and Edward Maraachlian. “Broadcasting in necklace graphs”. In: Proceedings of the 2nd Canadian Conference on Computer Science and Software Engineering. 2009, pp. 253–256.
[54] Hovhannes A. Harutyunyan and Arthur L Liestman. “Messy broadcasting”. In: Parallel Processing Letters 8.02 (1998), pp. 149–159.
[55] Hovhannes A. Harutyunyan and Arthur L Liestman. “More broadcast graphs”. In: Discrete Applied Mathematics 98.1-2 (1999), pp. 81–102.
[56] Hovhannes A. Harutyunyan and Edward Maraachlian. “Linear algorithm for broadcasting in unicyclic graphs”. In: International Computing and Combinatorics Conference. Springer. 2007, pp. 372–382.
[57] Hovhannes A. Harutyunyan and Edward Maraachlian. “On broadcasting in uni- cyclic graphs”. In: Journal of combinatorial optimization 16.3 (2008), pp. 307– 322.
[58] Hovhannes A. Harutyunyan and Edward Maraachlian. “Broadcasting in fully connected trees”. In: 2009 15th International Conference on Parallel and Distributed Systems. IEEE. 2009, pp. 740–745.
[59] Hovhannes A. Harutyunyan and Edward Maraachlian. “Linear Algorithm for Broadcasting in Networks With No Intersecting Cycles.” In: PDPTA. 2009, pp. 296–301.
[60] Hovhannes A. Harutyunyan and Edward Maraachlian. “Broadcasting in hierarchical tree cluster network”. In: PDPTA 2010: proceedings of the 2010 international conference on parallel and distributed processing techniques and applications (Las Vegas NV, July 12-15, 2010). 2010, pp. 479–484.
[61] Hovhannes A. Harutyunyan and Bin Shao. “An efficient heuristic for broadcasting in networks”. In: Journal of Parallel and Distributed Computing 66.1 (2006), pp. 68–76.
[62] Sandra M Hedetniemi, Stephen T Hedetniemi, and Arthur L Liestman. “A survey of gossiping and broadcasting in communication networks”. In: Networks 18.4 (1988), pp. 319–349.
[63] Marie-Claude Heydemann, Jaroslav Opatrny, and Dominique Sotteau. “Broadcasting and spanning trees in de Bruijn and Kautz networks”. In: Discrete applied mathematics 37 (1992), pp. 297–317.
[64] JurajHromkovicˇ,Claus-DieterJeschke,andBurkhardMonien.“Optimalalgo- rithms for dissemination of information in some interconnection networks”. In: International Symposium on Mathematical Foundations of Computer Science. Springer. 1990, pp. 337–346.
[65] Juraj Hromkovicˇ, Ralf Klasing, Burkhard Monien, and Regine Peine. “Dissemination of information in interconnection networks (broadcasting & gossiping)”. In: Combinatorial network theory. Springer, 1996, pp. 125–212.
[66] Cray Inc. The Gemini Network. URL: https : / / wiki . alcf . anl . gov / parts/images/2/2c/Gemini-whitepaper.pdf.
[67] Andreas Jakoby, Rüdiger Reischuk, and Christian Schindelhauer. “The complexity of broadcasting in planar and decomposable graphs”. In: Discrete Applied Mathe- matics 83.1-3 (1998), pp. 179–206.
[68] Klaus Jansen and Haiko Müller. “The minimum broadcast time problem for several processor networks”. In: Theoretical Computer Science 147.1-2 (1995), pp. 69–85.
[69] LH Khachatrian and OS Harutounian. “Construction of new classes of minimal broadcast networks”. In: Conference on Coding Theory, Armenia. 1990, pp. 69–77.
[70] Ralf Klasing, Burkhard Monien, Regine Peine, and Elena A Stöhr. “Broadcasting in butterfly and DeBruijn networks”. In: Discrete Applied Mathematics 53.1-3 (1994), pp. 183–197.
[71] C Ko. “Broadcasting, Graph homomorphisms and chord intersections.” In: (1980).
[72] Chen-Shung Ko. “On a conjecture concerning broadcasting in grid graphs”. In: AMS Notices (1979), A196–A197.
[73] Guy Kortsarz and David Peleg. “Approximation algorithms for minimum time broadcast”. In: Israel Symposium on Theory of Computing and Systems. Springer. 1992, pp. 67–78.
[74] S Kuppuswami and B Tourancheau. “Evaluating the performances of transputer based hypercube vector computer”. In: La lettre du Transputer 4 (1990).
[75] Roger Labahn. “Information flows on hypergraphs”. In: Discrete mathematics 113.1- 3 (1993), pp. 71–97.
[76] Roger Labahn. “A minimum broadcast graph on 63 vertices”. In: Discrete Applied Mathematics 53.1-3 (1994), pp. 247–250.
[77] Tomas Lang and Harold S Stone. “A shuffle-exchange network with simplified control”. In: IEEE Transactions on computers 100.1 (1976), pp. 55–65.
[78] Frank Thomson Leighton. Layouts for the Shuffle-Exchange Graph and Lower Bound Techniques for VLSI. Tech. rep. Massachusetts inst of tech Cambridge lab for computer science, 1982.
[79] Arthur L Liestman and Joseph G Peters. “Broadcast networks of bounded degree”. In: SIAM journal on Discrete Mathematics 1.4 (1988), pp. 531–540.
[80] Arthur L Liestman and Joseph G Peters. “Minimum broadcast digraphs”. In: Discrete Applied Mathematics 37 (1992), pp. 401–419.
[81] Arthur L. Liestman and Dana Richards. “Network communication in edge-colored graphs: gossiping”. In: IEEE Transactions on Parallel and Distributed Systems 4.4 (1993), pp. 438–445.
[82] Philip D MacKenzie. “A lower bound for order-preserving broadcast in the postal model”. In: Parallel Processing Letters 3.04 (1993), pp. 313–320.
[83] David May. “The next generation transputers and beyond”. In: European Conference on Distributed Memory Computing. Springer. 1991, pp. 7–22.
[84] DS Meliksetian and CYR Chen. Optimal routing algorithm and other communication issues of the cube-connected cycles. Tech. rep. Tech. Rep. TR90-4, Dept. Elec. & Comp. Eng., Syracuse University, 1990.
[85] Martin Middendorf. “Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2”. In: Information Processing Letters 46.6 (1993), pp. 281– 287.
[86] Sandra Mitchell and Stephen Hedetniemi. “A census of minimum broadcast graphs”. In: J. Combin. Inform. System Sci 5 (1980), pp. 141–151.
[87] Mohamed Ould-Khaoua. “On the optimal network for multicomputer: Torus or hypercube?” In: European Conference on Parallel Processing. Springer. 1998, pp. 989– 992.
[88] Brigitte Plateau and Denis Trystam. “Optimal total exchange for a 3-D torus of processors”. In: Information Processing Letters 42.2 (1992), pp. 95–102.
[89] Franco P Preparata and Jean Vuillemin. “The cube-connected cycles: a versatile network for parallel computation”. In: Communications of the ACM 24.5 (1981), pp. 300–309.
[90] Prabhakar Raghavan and Eli Upfal. “Efficient routing in all-optical networks”. In: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing. 1994, pp. 134–143.
[91] Justin Rattner. “The new age of supercomputing”. In: European Conference on Distributed Memory Computing. Springer. 1991, pp. 1–6.
[92] R Ravi. “Rapid rumor ramification: Approximating the minimum broadcast time”. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE. 1994, pp. 202–213.
[93] R Reischuk. “An Algebraic Divide and Conquer Approach to Design Highly Parallel Solution Strategies for Optimization Problems on Graphs”. In: Technical Report. TH Darmstadt, 1991.
[94] Youcef Saad and Martin H Schultz. “Topological properties of hypercubes”. In: IEEE Transactions on computers 37.7 (1988), pp. 867–872.
[95] Peter Scheuermann and Geoffrey Wu. “Heuristic algorithms for broadcasting in point-to-point computer networks”. In: IEEE Computer Architecture Letters 33.09 (1984), pp. 804–811.
[96] Christian Schindelhauer. “On the inapproximability of broadcasting time”. In: International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer. 2000, pp. 226–237.
[97] Steve R Seidel. “Circuit-switched vs. store-and-forward solutions to symmetric communication problems”. In: Proceedings of the 4th Conference on Hypercube Computers and Concurrent Applications. 1989, pp. 253–255.
[98] Steven R Seidel, Ming-Homg Lee, and Shivi Fotedar. “Concurrent bidirectional communication on the Intel iPSC/860 and iPSC/2”. In: The Sixth Distributed Memory Computing Conference, 1991. Proceedings. IEEE Computer Society. 1991, pp. 283–284.
[99] Charles L Seitz. “The cosmic cube”. In: Communications of the ACM 28.1 (1985), pp. 22–33.
[100] Peter J. Slater, Ernest J. Cockayne, and Stephen T. Hedetniemi. “Information dis- semination in trees”. In: SIAM Journal on Computing 10.4 (1981), pp. 692–701.
[101] Elena Stöhr. “Broadcasting in the butterfly network”. In: Information Processing Letters 39.1 (1991), pp. 41–43.
[102] Elena Stöhr. “On the broadcast time of the butterfly network”. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer. 1991, pp. 226– 229.
[103] Abderezak Touzene and Brigitte Plateau. “Optimal multinode broadcast on a mesh connected graph with reduced bufferization”. In: European Conference on Distributed Memory Computing. Springer. 1991, pp. 143–152.
[104] Jonathan S Turner and Leonard F Wyatt. “A packet network architecture for integrated services”. In: Proceedings of GLOBECOM. Vol. 83. 1983, pp. 11–83.
[105] Frances Van Scoy. “Broadcasting a small number of messages in a square grid graph”. In: Proc. Seventeenth Allerton Conf. on Communication, Control and Computing. 1979.
[106] Emmanouel A Varvarigos and Dimitri P Bertsekas. “Communication algorithms for isotropic tasks in hypercubes and wraparound meshes”. In: Parallel Computing 18.11 (1992), pp. 1233–1257.
[107] Wikipedia. Cartesian product of graphs. URL: https : / / en . wikipedia . org/wiki/Cartesian_product_of_graphs.
[108] Wikipedia. Torus interconnect. URL: https://en.wikipedia.org/wiki/ Torus_interconnect#cite_note-1.
[109] Ouri Wolfson and Adrian Segall. “The communication complexity of atomic commitment and of gossiping”. In: SIAM Journal on Computing 20.3 (1991), pp. 423– 450.
[110] Jian-guo Zhou and Ke-min Zhang. “A minimum broadcast graph on 26 vertices”. In: Applied mathematics letters 14.8 (2001), pp. 1023–1026.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics