{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:20:33Z","timestamp":1752229233137},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[1998,6]]},"abstract":"<jats:p> We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled torus: neither nodes nor links have a priori assigned labels but they know the topology and the size of the torus. Nodes can send messages of arbitrary size and we are interested in minimizing the total number of messages. A naive broadcasting algorithm in a n \u00d7 n totally unlabeled torus uses 3n<jats:sup>2<\/jats:sup> + 1 messages, while the obvious lower bound is n<jats:sup>2<\/jats:sup> - 1. The main result of this paper is a broadcasting algorithm using 2n<jats:sup>2<\/jats:sup> + O(n) messages. We also give a lower bound of 1.04n<jats:sup>2<\/jats:sup> - O(n) messages. This is the first result on message complexity of broadcasting in totally unlabeled networks. <\/jats:p>","DOI":"10.1142\/s0129626498000195","type":"journal-article","created":{"date-parts":[[2003,9,8]],"date-time":"2003-09-08T09:56:09Z","timestamp":1063014969000},"page":"177-188","source":"Crossref","is-referenced-by-count":9,"title":["Broadcasting in Unlabeled Tori"],"prefix":"10.1142","volume":"08","author":[{"given":"Krzysztof","family":"Diks","sequence":"first","affiliation":[{"name":"Instytut Informatyki,  Uniwersytet Warszawski, ul. Banacha 2, 02-097  Warszawa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University,  Ottawa, Ontario, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"D\u00e9partement d'Informatique,  Universit\u00e9 du Qu\u00e9bec \u00e0 Hull, Hull,  Qu\u00e9bec J8X 3X7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626498000195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:33:43Z","timestamp":1565184823000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626498000195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[1998,6]]}},"alternative-id":["10.1142\/S0129626498000195"],"URL":"https:\/\/doi.org\/10.1142\/s0129626498000195","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,6]]}}}