Topology recognition and leader election in colored networks

摘要

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 anonymous networks, in which nodes do not have labels (all nodes have the same color).