Source author record

Florian Huc

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing math.CO Networking and Internet Architecture Computational Complexity Cryptography and Security

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

On Dynamic Distributed Computing

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}-ε$ of the nodes, for some fixed constant $ε> 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.

preprint2011arXiv

Distributed Planarization and Local Routing Strategies in Sensor Networks

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 node's identifier sent by the algorithm is $6n$ , while the computational complexity is $O(nΔ)$ , with $Δ$ 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$ node's 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.

preprint2011arXiv

Scalable and Secure Aggregation in Distributed Networks

We consider the problem of computing an aggregation function in a \emph{secure} and \emph{scalable} way. Whereas previous distributed solutions with similar security guarantees have a communication cost of $O(n^3)$ , we present a distributed protocol that requires only a communication complexity of $O(n\log^3 n)$ , which we prove is near-optimal. Our protocol ensures perfect security against a computationally-bounded adversary, tolerates $(1/2-ε)n$ malicious nodes for any constant $1/2 > ε> 0$ (not depending on $n$ ), and outputs the exact value of the aggregated function with high probability.

preprint2010arXiv

Subgraphs of weakly quasi-random oriented 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 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 that $H$ is an oriented four-cycle we prove: in every $H$ -free oriented graph $D$ , there is a pair $A,B\ssq 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.

preprint2010arXiv

WDM and Directed Star Arboricity

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 arcs of $D$ such that at each vertex $v$ , and for each colour $α$ , $in(v,α)+out(v,α)\leq n$ with $in(v,α)$ the number of arcs coloured $α$ entering $v$ and $out(v,α)$ the number of labels $l$ such that there is at least one arc of label $l$ leaving $v$ and coloured with $α$ . The problem is to find the minimum number of colours $λ_n(D)$ such that the $m$ -labelled digraph $D$ has an $n$ -fibre colouring. In the particular case when $D$ is $1$ -labelled, $λ_1(D)$ is called the directed star arboricity of $D$ , and is denoted by $dst(D)$ . We first show that $dst(D)\leq 2Δ^-(D)+1$ , and conjecture that if $Δ^-(D)\geq 2$ , then $dst(D)\leq 2Δ^-(D)$ . We also prove that for a subcubic digraph $D$ , then $dst(D)\leq 3$ , and that if $Δ^+(D), Δ^-(D)\leq 2$ , then $dst(D)\leq 4$ . Finally, we study $λ_n(m,k)=\max\{λ_n(D) \tq D \mbox{is $m$-labelled} \et Δ^-(D)\leq k\}$. We show that if $m\geq n$ , then $\ds \left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil\leq λ_n(m,k) \leq\left\lceil\frac{m}{n}\left\lceil \frac{k}{n}\right\rceil + \frac{k}{n} \right\rceil + C \frac{m^2\log k}{n}$ for some constant $C$ . We conjecture that the lower bound should be the right value of $λ_n(m,k)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.