This paper shows for the first time that distributed computing can be both reliable and efficient in an environment that is both highly dynamic and hostile. More specifically, we show how to maintain clusters of size $O(log N)$, each containing more
than two thirds of honest nodes with high probability, within a system whose size can vary textit{polynomially} with respect to its initial size. Furthermore, the communication cost induced by each node arrival or departure is polylogarithmic with respect to $N$, the maximal size of the system. Our clustering can be achieved despite the presence of a Byzantine adversary controlling a fraction $bad leq {1}{3}-epsilon$ of the nodes, for some fixed constant $epsilon > 0$, independent of $N$. So far, such a clustering could only be performed for systems who size can vary constantly and it was not clear whether that was at all possible for polynomial variances.
We present an algorithm which computes a planar 2-spanner from an Unit Disk Graph when the node density is sufficient. The communication complexity in terms of number of nodes identifier sent by the algorithm is $6n$, while the computational complexi
ty is $O(nDelta)$, with $Delta$ the maximum degree of the communication graph. Furthermore, we present a simple and efficient routing algorithm dedicated to the computed graph. Last but not least, using traditional Euclidean coordinates, our algorithm needs the broadcast of as few as $3n$ nodes identifiers. Under the hypothesis of sufficient node density, no broadcast at all is needed, reducing the previous best known complexity of an algorithm to compute a planar spanner of an Unit Disk Graph which was of $5n$ broadcasts.
A digraph is $m$-labelled if every arc is labelled by an integer in ${1, dots,m}$. Motivated by wavelength assignment for multicasts in optical networks, we introduce and study $n$-fibre colourings of labelled digraphs. These are colourings of the ar
cs of $D$ such that at each vertex $v$, and for each colour $alpha$, $in(v,alpha)+out(v,alpha)leq n$ with $in(v,alpha)$ the number of arcs coloured $alpha$ entering $v$ and $out(v,alpha)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $alpha$. The problem is to find the minimum number of colours $lambda_n(D)$ such that the $m$-labelled digraph $D$ has an $n$-fibre colouring. In the particular case when $D$ is $1$-labelled, $lambda_1(D)$ is called the directed star arboricity of $D$, and is denoted by $dst(D)$. We first show that $dst(D)leq 2Delta^-(D)+1$, and conjecture that if $Delta^-(D)geq 2$, then $dst(D)leq 2Delta^-(D)$. We also prove that for a subcubic digraph $D$, then $dst(D)leq 3$, and that if $Delta^+(D), Delta^-(D)leq 2$, then $dst(D)leq 4$. Finally, we study $lambda_n(m,k)=max{lambda_n(D) tq D mbox{is $m$-labelled} et Delta^-(D)leq k}$. We show that if $mgeq n$, then $ds leftlceilfrac{m}{n}leftlceil frac{k}{n}rightrceil + frac{k}{n} rightrceilleq lambda_n(m,k) leqleftlceilfrac{m}{n}leftlceil frac{k}{n}rightrceil + frac{k}{n} rightrceil + C frac{m^2log k}{n}$ for some constant $C$. We conjecture that the lower bound should be the right value of $lambda_n(m,k)$.
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(ell,k)$-routing problem, each node can send at most $el
l$ packets and receive at most $k$ packets. Permutation routing is the particular case $ell=k=1$. In the $r$-central routing problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$. In this article we study the permutation routing, the $r$-central routing and the general $(ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the emph{store-and-forward} $Delta$-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on $(ell,k)$-routing on plane grids. Our main contributions are the following: 1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. 2. Tight $r$-central routing algorithms on triangular and hexagonal grids. 3. Tight $(k,k)$-routing algorithms on square, triangular and hexagonal grids. 4. Good approximation algorithms (in terms of running time) for $(ell,k)$-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the $(ell,k)$-routing problem as a textsc{Weighted Edge Coloring} problem on bipartite graphs.
It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active are
a of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,Bssq V(D)$ such that $e(A,B)ge e(D)^{2}/32|D|^{2}$ and $e(B,A)le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.
In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks are dependent either on expensive and sometimes unava
ilable hardware (e.g. GPS) or on sophisticated localization calculus (e.g. triangulation) which are both error-prone and with a costly overhead. Instead of localizing nodes in a traditional 2-dimensional space, we use directly the raw distance to a set of anchors to route messages in a multi-dimensional space. This should enable us to use any geographic routing protocol in a robust and efficient manner in a very large range of scenarios. We test this technique for two different geographic routing algorithms, namely GRIC and ROAM. The simulation results show that using the raw coordinates does not decrease their efficiency.
In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks are dependent either on expensive and sometimes unava
ilable hardware (e.g. GPS) or on sophisticated localization calculus (e.g. triangulation) which are both error-prone and with a costly overhead. Instead of localizing nodes in a traditional 2-dimensional space, we intend to use directly the raw distance to a set of anchors to route messages in the multi-dimensional space. This should enable us to use any geographic routing protocol in a robust and efficient manner in a very large range of scenarios.
