Abstract
We consider broadcasting on asynchronous anonymous totally unoriented n × m torus, where N=n·m is the number of nodes. We present a broadcasting algorithm with message complexity 1.43 N+O(n+m) and prove the lower bound in the form 1.14 N – O(1). This is an improvement over the previous \(2N+O(\sqrt{N})\) upper bound and \(1.04 N -- O(\sqrt{N})\) lower bound achieved by Diks, Kranakis and Pelc [DKP96]. Unlike the algorithm from [DKP96], our algorithm works also on non-square tori, does not require the knowledge of sizes n and m and uses only messages of size O(1) bits. This is the first known broadcasting algorithm on unoriented tori that does not use all edges.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Diks, K., Kranakis, E., Pelc, A.: Broadcasting in Unlabeled Tori. Départment d’Informatique, Université du Québec á Hull, Technical Report RR 96/12-5 (1996)
Dobrev, S., Ružička, P.: Linear Broadcasting and N log log N Election in Unoriented Hypercubes. In: Proc. of the 4th International Colloquium on Structural Information and Communication Complexity (SIROCC 1997), pp. 55–73. Carleton Press, Ascona (1997)
Dobrev, S., Ružička, P., Tel, G.: Time and Bit Optimal Broadcasting on Anonymous Unoriented Hypercubes. In: Proc. of the 5th International Colloquium on Structural Information and Communication Complexity (SIROCCO 1998), Carleton Press, Amalfi (1998)
Diks, K., Dobrev, S., Kranakis, E., Pelc, A., Ružička, P.: Broadcasting in Unlabeled Hypercubes with Linear Number of Messages. To appear in Information Processing Letters (1998)
Flocchini, P., Mans, B., Santoro, N.: Sense of Direction: Formal Definitions and Properties. In: Proc. of the 1st International Colloquium on Structural Information and Communication Complexity (SIROCCO 1994), pp. 9–34. Carleton Press, Siena (1995)
Flocchini, P., Mans, B., Santoro, N.: On the Impact of Sense of Direction on Communication Complexity. Information Processing Letters 63(1), 23–31 (1997)
Mans, B.: Broadcast, Traversal and Election in Unlabelled Hypercube. In: Proc. of the 3rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 1996), pp. 333–334. Carleton Press, Siena (1996)
Mans, B.: Optimal Distributed Algorithms in Unlabeled Tori and Chor-dal Rings. In: Proc. of the 3rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 1996), pp. 17–31. Carleton Press, Siena (1996)
Peleg, D.: Personal communication at the Sienna Research School 1997 on Compact Routing and Sense of Direction, Siena, Italy (June 1997)
Peterson, G.L.: Efficient algorithms for elections in meshes and complete networks. Technical Report TR140, Dept. of Computer Science, Univ. of Rochester, Rochester, NY 14627 (1985)
Tel, G.: Network Orientation. International Journal of Foundations of Computer Science 5, 23–57 (1994)
Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge (1994)
Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Ružička, P. (1998). Broadcasting on Anonymous Unoriented Tori. In: Hromkovič, J., Sýkora, O. (eds) Graph-Theoretic Concepts in Computer Science. WG 1998. Lecture Notes in Computer Science, vol 1517. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10692760_5
Download citation
DOI: https://doi.org/10.1007/10692760_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65195-6
Online ISBN: 978-3-540-49494-2
eBook Packages: Springer Book Archive