{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:17:03Z","timestamp":1760145423781,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T00:00:00Z","timestamp":1720742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In classical broadcast models, information is disseminated in synchronous rounds under the constant communication time model, wherein a node may only inform one of its neighbors in each time-unit\u2014also known as the processor-bound model. These models assume either a coordinating leader or that each node has a set of coordinated actions optimized for each originator, which may require nodes to have sufficient storage, processing power, and the ability to determine the originator. This assumption is not always ideal, and a broadcast model based on the node\u2019s local knowledge can sometimes be more effective. Messy models address these issues by eliminating the need for a leader, knowledge of the starting time, and the identity of the originator, relying solely on local knowledge available to each node. This paper investigates the messy broadcast time and optimal scheme in a grid graph, a structure widely used in computer networking systems, particularly in parallel computing, due to its robustness, scalability, fault tolerance, and simplicity. The focus is on scenarios where the originator is located at one of the corner vertices, aiming to understand the efficiency and performance of messy models in such grid structures.<\/jats:p>","DOI":"10.3390\/a17070310","type":"journal-article","created":{"date-parts":[[2024,7,12]],"date-time":"2024-07-12T16:23:41Z","timestamp":1720801421000},"page":"310","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Messy Broadcasting in Grid"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-9936-4166","authenticated-orcid":false,"given":"Aria","family":"Adibi","sequence":"first","affiliation":[{"name":"Department of Computer Science, Concordia University, Montr\u00e9al, QC H3G 1M8, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7260-4186","authenticated-orcid":false,"given":"Hovhannes A.","family":"Harutyunyan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Concordia University, Montr\u00e9al, QC H3G 1M8, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2024,7,12]]},"reference":[{"key":"ref_1","unstructured":"Adibi, A. (2021). Broadcasting in Hyper-Cylinder Graphs. [Master\u2019s Thesis, Concordia University]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","article-title":"Methods and problems of communication in usual networks","volume":"53","author":"Fraigniaud","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1002\/net.3230180406","article-title":"A survey of gossiping and broadcasting in communication networks","volume":"18","author":"Hedetniemi","year":"1988","journal-title":"Networks"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J., Klasing, R., Monien, B., and Peine, R. (1996). Dissemination of information in interconnection networks (broadcasting &amp gossiping). Combinatorial Network Theory, Springer.","DOI":"10.1007\/978-1-4757-2491-2_5"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Harutyunyan, H.A., Liestman, A.L., Peters, J.G., and Richards, D. (2013). Broadcasting and gossiping. Handbook of Graph Theory, Chapman and Hall.","DOI":"10.1201\/b16132-87"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Blahut, R.E., Costello, D.J., Mauter, U., and Mittelholzer, T. (1994). Messy Broadcasting in Networks, Communications and Cryptography, Springer.","DOI":"10.1007\/978-1-4615-2694-0"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1142\/S0129626498000171","article-title":"Messy broadcasting","volume":"8","author":"Harutyunyan","year":"1998","journal-title":"Parallel Process. Lett."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/j.dam.2010.12.002","article-title":"Messy broadcasting\u2014Decentralized broadcast schemes with limited knowledge","volume":"159","author":"Harutyunyan","year":"2011","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1142\/S0219265908002400","article-title":"Average-case \u201cmessy\u201d broadcasting","volume":"9","author":"Li","year":"2008","journal-title":"J. Interconnect. Netw."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"114508","DOI":"10.1016\/j.tcs.2024.114508","article-title":"Parameterized complexity of broadcasting in graphs","volume":"997","author":"Fomin","year":"2024","journal-title":"Theor. Comput. Sci."},{"key":"ref_11","unstructured":"Tale, P. (2024). Double Exponential Lower Bound for Telephone Broadcast. arXiv."},{"key":"ref_12","first-page":"804","article-title":"Heuristic algorithms for broadcasting in point-to-point computer networks","volume":"33","author":"Scheuermann","year":"1984","journal-title":"IEEE Comput. Archit. Lett."},{"key":"ref_13","unstructured":"Flammini, M., Nardelli, E., Proietti, G., and Spirakis, P.G. (2000, January 20\u201322). A powerful heuristic for telephone gossiping. Proceedings of the SIROCCO 7, 7th International Colloquium on Structural Information and Communication Complexity, Laquila, Italy."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1006\/jpdc.1997.1318","article-title":"Approximation algorithms for broadcasting and gossiping","volume":"43","author":"Fraigniaud","year":"1997","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1142\/S0129626499000049","article-title":"Comparison of heuristics for one-to-all and all-to-all communications in partial meshes","volume":"9","author":"Fraigniaud","year":"1999","journal-title":"Parallel Process. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.jpdc.2005.06.010","article-title":"An efficient heuristic for broadcasting in networks","volume":"66","author":"Harutyunyan","year":"2006","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1111\/itor.13146","article-title":"A matheuristic approach for the minimum broadcast time problem using a biased random-key genetic algorithm","volume":"31","author":"Lima","year":"2024","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_18","unstructured":"Ben-Dor, A., Halevi, S., and Schuster, A. (1993). On Greedy Hot-Potatoe Routing, Laboratory for Parallel Computing Research, Technion-Israel Institute of Technology."},{"key":"ref_19","first-page":"842","article-title":"Data transfers in broadcast networks","volume":"41","author":"Bagchi","year":"1992","journal-title":"IEEE Comput. Archit. Lett."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1109\/12.204799","article-title":"Gossiping in a distributed network","volume":"42","author":"Bagchi","year":"1993","journal-title":"IEEE Trans. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1137\/0222055","article-title":"Multiple communication in multihop radio networks","volume":"22","author":"Israeli","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0020-0190(98)00055-6","article-title":"Broadcasting in unlabeled hypercubes with a linear number of messages","volume":"66","author":"Diks","year":"1998","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1142\/S0129626498000195","article-title":"Broadcasting in unlabeled tori","volume":"8","author":"Diks","year":"1998","journal-title":"Parallel Process. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0166-218X(98)00047-X","article-title":"Perfect broadcasting in unlabeled networks","volume":"87","author":"Diks","year":"1998","journal-title":"Discret. Appl. Math."},{"key":"ref_25","first-page":"39","article-title":"Efficient communication in unknown networks","volume":"38","author":"Gargano","year":"2001","journal-title":"Netw. Int. J."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1002\/rsa.3240010406","article-title":"Randomized broadcast in networks","volume":"1","author":"Feige","year":"1990","journal-title":"Random Struct. Algorithms"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2650185","article-title":"Quasirandom rumor spreading","volume":"11","author":"Doerr","year":"2014","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.tcs.2014.08.008","article-title":"The worst case behavior of randomized gossip protocols","volume":"560","author":"Baumann","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"88","DOI":"10.23919\/JCN.2022.000051","article-title":"HUB-GA: A heuristic for universal lists broadcasting using genetic algorithm","volume":"25","author":"Gholami","year":"2023","journal-title":"J. Commun. Netw."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2340017","DOI":"10.1142\/S0129626423400170","article-title":"A Note to Non-adaptive Broadcasting","volume":"34","author":"Gholami","year":"2024","journal-title":"Parallel Process. Lett."},{"key":"ref_31","unstructured":"Awerbuch, B., Goldreich, O., Peleg, D., and Vainish, R. (July, January 28). A tradeoff between information and communication in broadcast protocols. Proceedings of the Aegean Workshop on Computing, Corfu, Greece."},{"key":"ref_32","unstructured":"Farley, A.M., and Hedetniemi, S.T. (February, January 30). Broadcasting in grid graphs. Proceedings of the 9th Southeastern Conference Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Boca Raton, FL, USA."},{"key":"ref_33","unstructured":"Cockayne, E., and Hedetniemi, S. (1978). A Conjecture Concerning Broadcasting in m-Dimensional Grid Graphs, University of Oregon. Technical Report, Technical Report CS-TR-78-14."},{"key":"ref_34","unstructured":"Ko, C.S. (1979). On a conjecture concerning broadcasting in grid graphs. AMS Notices, American Mathematical Society."},{"key":"ref_35","unstructured":"Ko, C. (1980). Broadcasting, Graph Homomorphisms and Chord Intersections. [Ph.D. Thesis, Rutgers University]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/7\/310\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:16:09Z","timestamp":1760109369000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/7\/310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,12]]},"references-count":35,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,7]]}},"alternative-id":["a17070310"],"URL":"https:\/\/doi.org\/10.3390\/a17070310","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,7,12]]}}}