Search

International audience; Dans cet article nous étudions l'élection de leader distribuée dans des réseaux anonymes. Dans ce modèle l'ensemble des noeuds produisent en sortie un chemin simple vers l'un d'entre eux, ce dernier sera alors qualifié de leader. Nous étudions en particulier le cas de l'élection dans des arbres anonymes lorsque le temps alloué est inférieur au diamètre de l'arbre considéré. Si aucune information supplémentaire n'est accessible, les noeuds ne pouvant pas avoir une vision complète du réseau, l'élection est impossible et ce quel que soit l'algorithme utilisé. Nous étudions donc le compromis entre la quantité d'information initialement requise par les noeuds et le temps τ leur étant alloué pour réaliser l'élection. Nous utilisons le modèle des algorithmes avec conseil dans lequel un oracle ayant une connaissance complète du réseau, fournit un conseil unique sous forme d'une chaîne binaire, à l'ensemble des noeuds avant que ceux-ci n'initient leurs calculs. Pour la majorité des valeurs de τ nos bornes inférieures et supérieures sont proches à un facteur multiplicatif près, ou diffèrent seulement d'un facteur logarithmique. Pour un arbre T de diamètre diam ≤ D et un temps τ = diam − 1 la borne sur la quantité d'information requise (en nombre de bits) est Θ(log D). En réduisant le temps d'une unité, i.e., pour τ = diam − 2 la quantité d'information requise pour élire dépend de la parité du diamètre, elle est de Θ(log D) lorsque diam est pair et de Θ(log n) sinon. Pour tout temps τ ∈ [β · diam, diam − 3] avec β > 1/2, notre borne supérieure est O(n log n D) et notre borne inférieure de Ω(n D) à l'exception du cas où diam est pair et τ est exactement diam − 3, cas pour lequel le problème reste ouvert. Enfin, pour des temps α · diam avec α < 1/2, nous montrons que l'information requise a une taille de Θ(n).Cet article est une version courte de l'article Time vs. Information Tradeoffs for Leader Election in Anonymous Trees paru à SODA'16.

National audience; Nous étudions la quantité de connaissance nécessaire sur le réseau pour résoudre efficacement une tâche sur celui-ci. L'impact de l'information disponible sur l'efficacité de la résolution des problèmes, comme la communication ou l'exploration, a déjà été étudié auparavant mais les hypothèses concernaient la disponibilité d'informations {\em particulières} sur le réseau, comme sa taille, son diamètre ou une carte de celui-ci. Au contraire, notre approche est {\em quantitative} : nous étudions le nombre minimum de bits d'information (taille d'oracle minimum) qui doivent être fournis à l'algorithme pour effectuer une tâche avec une certaine efficacité. Nous illustrons cette approche quantitative de l'information disponible par le problème de l'exploration d'arbres. Une entité mobile (robot) doit traverser toutes les arêtes d'un arbre inconnu, en utilisant aussi peu de traversées d'arêtes que possible. La qualité d'un algorithme d'exploration $\cA$ est mesuré par son {\em rapport compétitif}, i.e., par comparaison de son coût (nombre de traversées d'arêtes) à la longueur du plus court chemin contenant toutes les arêtes de l'arbre. Le parcours en profondeur d'abord a un rapport compétitif de 2 et en l'absence d'information sur l'arbre aucun algorithme ne peut faire mieux. Nous déterminons le nombre minimal de bits d'information qui doit être donné à un algorithme d'exploration afin d'obtenir un rapport compétitif strictement plus petit que 2. Notre résultat principal établit un seuil exact sur la taille de l'oracle, qui est approximativement $\log \log D$ bits, où $D$ est le diamètre de l'arbre. Plus précisément, pour toute constante $c$, nous construisons un algorithme d'exploration de rapport compétitif plus petit que 2, utilisant un oracle de taille au plus $\log \log D -c$, et nous montrons que tout algorithme utilisant un oracle de taille $\log \log D -g(D)$, pour toute fonction $g$ non bornée supérieurement, a un rapport compétitif au moins égal à 2.

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le réseau est anonyme, au sens que les nœuds ne disposent pas nécessairement d'un étiquetage global. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à traverser chacun des liens du réseau. Nous montrons que, pour tout robot à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ nœuds que le robot ne réussit pas à explorer. Cette borne $K+1$ améliore toutes les bornes connues jusqu'aujourd'hui. Nous montrons également que, pour explorer tous les graphes de diamètre $D$ et de degré maximum $d$, un robot doit disposer de $\Omega(D\log{d})$ bits de mémoire, et ce même si l'on restreint l'exploration aux réseaux planaires. Enfin, nous montrons que cette borne est asymptotiquement optimale, en décrivant un algorithme qui permet à un robot possédant une mémoire de $O(D\log{d})$ bits d'explorer tous les réseaux de diamètre $D$ et de degré maximum $d$. Ceci nous permet donc de conclure que la complexité mémoire du problème de l'exploration de réseaux est $\Theta(D\log{d})$ bits.