### Topology Recognition and Leader Election in Colored Networks

**2016-01-28**

1601.07790 | cs.DC

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,\dots, d-1$. Colored networks are generalizations both of labeled networks
and anonymous networks.
In colored networks, topology recognition and leader election are not always
feasible. Hence we study two more general problems. The aim of the problem TOP
(resp. LE), for a colored network and for input $I$ given to its nodes, is to
solve topology recognition (resp. leader election) in this network, if this is
possible under input $I$, and to have all nodes answer "unsolvable" otherwise.
We show that nodes of a network can solve problems TOP and LE, if they are
given, as input $I$, an upper bound $k$ on the number of nodes of a given
color, called the size of this color. On the other hand we show that, if the
nodes are given an input that does not bound the size of any color, then the
answer to TOP and LE must be "unsolvable", even for the class of rings.
Under the assumption that nodes are given an upper bound $k$ on the size of a
given color, we study the time of solving problems TOP and LE in the $LOCAL$.
We give an algorithm to solve each of these problems in arbitrary $n$-node
networks of diameter $D$ in time $O(kD+D\log(n/D))$. We also show that this
time is optimal, by exhibiting classes of networks in which every algorithm
solving problems TOP or LE must use time $\Omega(kD+D\log(n/D))$.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-09-07**

1809.02482 | cs.LG

Network embedding algorithms are able to learn latent feature representations
of nodes, transforming… show more

**2019-01-09**

1901.02729 | cs.CR

Nodes in route-restricted overlays have an immutable set of neighbors,
explicitly specified by their… show more

**2018-09-10**

1809.03141 | cs.CC

The diffusion of information has been widely modeled as stochastic diffusion
processes on networks. … show more

**2018-11-28**

1811.11331 | cs.NI

We consider ad-hoc networks consisting of $n$ wireless nodes that are located
on the plane. Any two … show more

**2018-12-30**

1812.11535 | cs.SI

Network immunization is an extensively recognized issue in several domains
like virtual network secu… show more

**2019-04-11**

1904.05627 | cs.DC

Many graph problems are locally checkable: a solution is globally feasible if
it looks valid in all … show more

**2018-11-05**

1811.01643 | cs.DC

A graph is weakly $2$-colored if the nodes are labeled with colors black and
white such that each bl… show more

**2013-07-05**

1307.1690 | cs.DS

People today typically use multiple online social networks (Facebook,
Twitter, Google+, LinkedIn, et… show more

**2019-04-25**

1904.11533 | cs.NI

The increasing reliance upon cloud services entails more flexible networks
that are realized by virt… show more

**2018-05-18**

1805.07294 | cs.DC

In this paper, we study distributed graph algorithms in networks in which the
nodes have a limited c… show more

**2016-05-06**

1605.01903 | cs.DC

Leader election is, together with consensus, one of the most central problems
in distributed computi… show more

**2017-09-10**

1709.03034 | cs.DM

We propose and analyze a graph model to study the connectivity of
interdependent networks. Two inter… show more

**2019-01-02**

1901.00342 | cs.DC

In this paper, we look at the problem of randomized leader election in
synchronous distributed netwo… show more

**2018-10-07**

1810.03120 | cs.DC

Two anonymous mobile agents navigate synchronously in an anonymous graph and
have to meet at a node,… show more

**2018-02-19**

1802.06742 | cs.DC

Given two colorings of a graph, we consider the following problem: can we
recolor the graph from one… show more

**2014-06-07**

1406.1923 | cs.DC

In this paper, we address the problem of broadcasting in a wireless network
under a novel communicat… show more