publication . Article . Preprint . 2016

Topology recognition and leader election in colored networks

Dereniowski, Dariusz; Pelc, Andrzej;
Open Access
  • Published: 28 Jan 2016 Journal: Theoretical Computer Science, volume 621, pages 92-102 (issn: 0304-3975, Copyright policy)
  • Publisher: Elsevier BV
Abstract
Topology recognition and leader election are fundamental tasks in distributed computing in networks. The first of them requires each node to find a labeled isomorphic copy of the network, while the result of the second one consists in a single node adopting the label 1 (leader), with all other nodes adopting the label 0 and learning a path to the leader. We consider both these problems in networks whose nodes are equipped with not necessarily distinct labels called colors, and ports at each node of degree d are arbitrarily numbered 0 , 1 , ? , d - 1 . Colored networks are generalizations both of labeled networks, in which nodes have distinct labels, and of anony...
Subjects
free text keywords: Theoretical Computer Science, General Computer Science, Upper and lower bounds, Generalization, Computation, Topology, Isomorphism, Combinatorics, Leader election, Colored, Mathematics, Discrete mathematics, Computer Science - Distributed, Parallel, and Cluster Computing
Funded by
NSERC
Project
  • Funder: Natural Sciences and Engineering Research Council of Canada (NSERC)
43 references, page 1 of 3

[1] D. Angluin, Local and Global Properties in Networks of Processors, Proc. 12th Annual ACM Symposium on Theory of Computing (STOC 1980), 82-93.

[2] H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, R. Reischuk, Renaming in an Asynchronous Environment, Journal of the ACM 37 (1990), 524-548.

[3] H. Attiya, M. Snir, M. Warmuth, Computing on an Anonymous Ring, Journal of the ACM 35 (1988), 845- 875. [OpenAIRE]

[4] H. Attiya, M. Snir, Better Computing on the Anonymous Ring, Journal of Algorithms 12 (1991), 204-238. [OpenAIRE]

[6] B. Awerbuch, O. Goldreich, D. Peleg, R. Vainish, A Trade-O between Information and Communication in Broadcast Protocols, J. ACM 37 (1990), 238-256.

[7] P. Boldi, S. Shammah, S. Vigna, B. Codenotti, P. Gemmell, J. Simon, Symmetry Breaking in Anonymous Networks: Characterizations, Proc. 4th Israel Symposium on Theory of Computing and Systems (ISTCS 1996), 16-26.

[8] P. Boldi, S. Vigna, Computing Anonymously with Arbitrary Knowledge, Proc. 18th ACM Symp. on Principles of Distributed Computing (PODC 1999), 181-188. [OpenAIRE]

[9] J.E. Burns, A Formal Model for Message Passing Systems, Tech. Report TR-91, Computer Science Department, Indiana University, Bloomington, September 1980.

[10] J. Chalopin, Local Computations on Closed Unlabelled Edges: The Election Problem and the Naming Problem, Proc. 31st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2005), 82-91. [OpenAIRE]

[11] J. Chalopin, S. Das, A. Kosowski, Constructing a Map of an Anonymous Graph: Applications of Universal Sequences, Proc. 14th International Conference on Principles of Distributed Systems (OPODIS 2010), 119- 134. [OpenAIRE]

[12] J. Chalopin, A.W. Mazurkiewicz, Y. Me´tivier, Labelled (Hyper)Graphs, Negotiations and the Naming Problem, Proc. 4th International Conference on Graph Transformations (ICGT 2008), 54-68. [OpenAIRE]

[13] J. Chalopin, Y. Me´tivier, Election and Local Computations on Edges, Proc. Foundations of Software Science and Computation Structures (FoSSaCS 2004), 90-104. [OpenAIRE]

[14] D. Dereniowski, A. Kosowski, D. Pajak, Distinguishing Views in Symmetric Networks: A Tight Lower Bound, Theoretical Computer Science 582 (2015) 27-34.

[15] D. Dereniowski, A. Pelc, Drawing Maps with Advice, Journal of Parallel and Distributed Computing 72 (2012), 132-143.

[16] D. Dereniowski, A. Pelc, Leader Election for Anonymous Asynchronous Agents in Arbitrary Networks, Distributed Computing 27 (2014), 21-38.

43 references, page 1 of 3
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue