ML p(r)ior | Topology Recognition and Leader Election in Colored Networks

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))\$.

Highlights - Most important sentences from the article

Related Articles

2018-09-07
1809.02482 | cs.LG

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

Highlights - Most important sentences from the article

2019-01-09
1901.02729 | cs.CR

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

Highlights - Most important sentences from the article

2018-09-10
1809.03141 | cs.CC

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-12-30
1812.11535 | cs.SI

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2013-07-05
1307.1690 | cs.DS

Highlights - Most important sentences from the article

2019-04-25
1904.11533 | cs.NI

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2016-05-06
1605.01903 | cs.DC

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2014-06-07
1406.1923 | cs.DC