This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity Õ(√n) and time complexity Õ(1).

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 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 τ ≤ 1⁄3-ε of the nodes, for some fixed constant ε > 0, independent of N. So far, such a clustering could only be performed for systems whose size can vary constantly and it was not clear whether that was at all possible for polynomial variances.

In this paper, we present PDP, a distributed polling protocol that enables a set of participants to gather their opinion on a common interest without revealing their point of view. PDP does not rely on any centralized authority or on heavyweight cryptography. PDP is an overlay-based protocol where a subset of participants may use a simple sharing scheme to express their votes. In a system of M participants arranged in groups of size N where at least 2k-1 participants are honest, PDP bounds the probability for a given participant to have its vote recovered with certainty by a coalition of B dishonest participants by π(B/N)(k+1), where π is the proportion of participants splitting their votes, and k a privacy parameter. PDP bounds the impact of dishonest participants on the global outcome by 2(kα + BN), where represents the number of dishonest nodes using the sharing scheme.

In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC).Our first algorithm computes a planar 2-spanner under light constraints on the edge lengths and induces a total exchange of at most 6n node identifiers. Its total complexity is O(nΔ), with Δ the maximum degree of the communication graph. The second algorithm that we present is a simple and efficient algorithm to route messages in this planar graph that requires routing tables with only three entries. We support these theoretical results by simulations showing the robustness of our algorithms when the coordinates are inaccurate.

We consider the problem of securely conducting a poll in synchronous dynamic networks equipped with a Public Key Infrastructure (PKI). Whereas previous distributed solutions had a communication cost of O(n2) in an n nodes system, we present SPP (Secure and Private Polling), the first distributed polling protocol requiring only a communication complexity of O(n log3n), which we prove is near-optimal. Our protocol ensures perfect security against a computationally-bounded adversary, tolerates (1/2 - ϵ)n Byzantine nodes for any constant 1/2 >; ϵ >; 0 (not depending on n), and outputs the exact value of the poll with high probability. SPP is composed of two sub-protocols, which we believe to be interesting on their own: SPP-Overlay maintains a structured overlay when nodes leave or join the network, and SPP-Computation conducts the actual poll. We validate the practicality of our approach through experimental evaluations and describe briefly two possible applications of SPP: (1) an optimal Byzantine Agreement protocol whose communication complexity is Θ(n log n) and (2) a protocol solving an open question of King and Saia in the context of aggregation functions, namely on the feasibility of performing multiparty secure aggregations with a communication complexity of o(n2).

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 area 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 where H is an oriented four-cycle we prove the following: in every H-free oriented graph D, there is a pair $A,B\subseteq V(D)$ such that $e(A,B)\geq e(D)^{2}/32|D|^{2}$ and $e(B,A)\leq 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 where H is an oriented six-cycle and a more precise result in the case where 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 we provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.

This work introduces a new shared segment protection scheme that ensures both node and link protection in an efficient manner in terms of cost and bandwidth, while taking full advantage of the optical hop endpoints of the primary logical hops (induced by the routing) without adding extra ones for protection. As opposed to the link or path protection schemes, the segment protection scheme has been less studied although it offers an interesting compromise between those two protection schemes, attempting to encompass all their advantages. We investigate two different Shared Segment Protection (SSP) schemes: Basic Shared Segment Protection (BSSP) and Shared Segment Protection with segment Overlap (SSPO), and propose design of 100% single segment protections. In SSPO, we study the extra protection capabilities, node failure and dual link failure survivability, offered by the single 100% segment protection. For both BSSP and SSPO schemes, we propose two novel efficient ILP formulations, based on a column generation mathematical modeling. While (SSPO) offers the advantage over (BSSP) to ensure both node and link protection, it is not necessarily much more costly. Indeed, depending on the network topology and the traffic instances, it can be shown that none of the two SSP schemes dominates the other one. Therefore, the SSPO protection scheme should be favored as it offers more protection, i.e., it adds the node protection to the link protection at the expense of a minor additional cost.

We study the problem of routing messages in sensor networks where the energy saving issue is essential. In this paper, we propose ROAM2, an improvement of ROAM (Routing protocol with Obstacle Avoidance Mechanism) proposed in [HJL+09]. This distributed protocol has a light obstacle detection and avoidance component with low message and computation overhead and a routing component which sends messages along short paths, thus saving energy. We improved it so that is has an 100% delivery rate and we prove that ROAM finds with high probability paths whose lengths are comparable to the length of the shortest paths. Furthermore, we prove a general result on the length of any path computed in a greedy way. Whereas ROAM uses one bit of memory in nodes (even if there are several destinations), in [KWZ08], it was shown that no geographic routing algorithm not using any sensor memory can compute a path whose length is guaranteed to be of order less than O(l2), where l is the length of the shortest path. Finally, we compare the energy efficiency of ROAM against GPSR (or GFG) [KK00], the algorithm proposed in [MLNR08] and SLGF [JMLW08], by running simulations which validates our theoretical results

In this article, we study a combinatorial optimization problem arising from on-board networks in satellites. In these kinds of networks, the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four available links. The paths connecting inputs to outputs should be link-disjoint. More formally, we call a (p, λ, k)-network an undirected graph with p + λ inputs, p + k outputs, and internal vertices of degree four. A (p, λ, k)-network is valid if it is tolerant to a restricted number of faults in the network, i.e., if, for any choice of at most λ faulty inputs and k faulty outputs, there exist p edge-disjoint paths from the remaining inputs to the remaining outputs. Our optimization problem consists of determining N(p, λ, k), the minimum number of vertices in a valid (p, λ, k)-network. We present validity certificates and a quasi-partitioning technique from which we derive lower bounds for N(p, λ, k). We also provide constructions, and hence upper bounds, based on expanders. The problem is shown to be sensitive to the order of λ and k. For instance, when λ and k are small compared with p, the question reduces to the avoidance of some forbidden local configurations. For larger values of λ and k, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called α-robustness. We use α-robustness to generalize our constructions for larger values of k and λ. In many cases, we provide asymptotically tight bounds for N(p, λ, k). © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We present a result concerning the relation between the path-width of a plane graph and the path-width of its dual. We prove that for a 3-connected planar graph G, ${\rm pw}(G)\leq3{\rm pw}(G^*)+2$. For 4-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound ${\rm pw}(G^*)\leq2~{\rm pw}(G)+c$. The best previously known bound was obtained by Fomin and Thilikos who proved that ${\rm pw}(G^*)\leq6~{\rm pw}(G)+c$. Our proof is based on a transformation which, given a fixed spanning tree of G, sends any given decomposition of G into one of $G^*$. The ratio of the corresponding parameters is bounded by the maximum degree of the spanning tree.

The notion of Shared Risk Resource Groups (SRRG) has been introduced to capture survivability issues when a set of resources may fail simultaneously. Applied to Wavelength Division Multiplexing Network (WDM), it expresses that some links and nodes may fail simultaneously. The reliability of a connection therefore depends on the number of SRRGs through which it is routed. Consequently, this number has to be minimized. This problem has been proved NP-complete and hard to approximate in general, even when routing a single request. Some heuristics using shortest paths have already been designed, however the cost (the usual routing cost, not in term of SRRG) was not part of the objective. In this paper we study the problem of minimizing a linear combination of the average number of SRRG per paths and the cost of the routing. The main result of our work is a column generation formulation that allows to solve efficiently the problem of maximizing the reliability of a set of connection requests in MPLS/WDM mesh networks with SRRGs while keeping the cost of the routing low.