We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Broadcasting in Unlabeled Tori.
- Authors
Diks, Krzysztof; Kranakis, Evangelos; Pelc, Andrzej
- Abstract
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 × n totally unlabeled torus uses 3n2 + 1 messages, while the obvious lower bound is n2 - 1. The main result of this paper is a broadcasting algorithm using 2n2 + O(n) messages. We also give a lower bound of 1.04n2 - O(n) messages. This is the first result on message complexity of broadcasting in totally unlabeled networks.
- Publication
Parallel Processing Letters, 1998, Vol 8, Issue 2, p177
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626498000195