Source d'incertitude : localité de la connaissance ; algorithmes de routage

Ces travaux se placent dans le contexte des réseaux et s’intéressent aux propriétés des algorithmes de routage robustes à un ensemble de fautes aléatoires. Plus précisément, nous nous intéressons à des protocoles de routage robustes aux défaillances de l’infrastructure de communication et nous étudions leur capacité à exploiter une infrastructure (topologie) initialement k-connexe. La particularité de notre approche est de développer des algorithmes locaux, où chaque routeur de la topologie doit prendre des décisions de routage (à qui relayer un paquet) qui dépendent uniquement de sa vision locale, c’est-à-dire de l’état de ses ports et du paquet courant. Cette propriété est très intéressante en pratique, puisque l’absence de communication permet des réactions de l’ordre de la milliseconde en comparaison à des approches “globales” aux latences de l'ordre de la seconde. Le gain en performance est particulièrement adapté aux réseaux locaux à trafic dense, comme les datacenters. C’est aussi un défi théorique difficile : l’absence d’information sur l’état global du réseau oblige à concevoir des solutions en envisageant a priori tous les états possibles. Le nombre de ces états possibles explosant de façon combinatoire avec le nombre de fautes, l’exploration exhaustive de ces états est proscrite, laissant place à des approches plus fines reposant sur des abstractions efficaces.

Dans cette perspective nous montrons qu’un tel protocole de routage est nécessairement obligé de faire un compromis entre trois propriétés désirables d’une telle solution de routage, à savoir que celle-ci 1) soit tolérante aux fautes (trafic maintenu malgré f fautes), 2) limite la longueur des détours des paquets concernés, et 3) équilibre naturellement la charge sur les liens survivants[1].

Nous apportons aussi des solutions de routage efficaces[2],[3] sous la forme d’algorithmes exacts ou d’approches heuristiques.

Source d'incertitude : asynchronie ; algorithmes wait-free

La réplication de machines à états est une technique majeure de tolérance aux fautes, déployée en particulier dans les clouds. Elle utilise une forme de consensus pour garantir la cohérence des différentes répliques.

Nous avons développé un mécanisme algorithmique mettant en lumière l'effet de l'incertitude temporelle sur la cohérence d'un système de réplication[4]. Lorsque le système est totalement synchrone – tous les processus s’exécutent à la même vitesse – il est possible d'implémenter cette technique de réplication. Plus le système est asynchrone, plus les performances du système de réplication se dégradent. Ces travaux formalisent ce compromis, et proposent une définition formelle de l'asynchronie dans un système réparti.

Nous avons également étudié l'effet de l'incertitude due à l'asynchronie au travers du problème de coordination asynchrone[5] dans lequel, étant donné un graphe, les participants doivent se coordonner pour renvoyer chacun un sommet de manière à ce qu'aucune paire de processus ne soit reliée par un arc du graphe. Ce problème, à la croisée des deux sous-communautés de la recherche en systèmes répartis “graphes” et “algorithmes tolérants aux fautes”, a un intérêt pratique dans le cadre des grands systèmes répartis de transactions de type cloud. Les dépendances entre transactions, dues aux accès aux mêmes données, peuvent être décrites par un graphe. L'application directe de ces travaux consiste à déterminer un ensemble maximal de transactions indépendantes pouvant être exécutées en parallèle par les serveurs, sans conflit. Le problème associé au graphe dual est relié au gathering, un problème fondamental de robotique collaborative[6].

[1] Foerster K-T., Pignolet Y-M., Schmid S., Tredan G, CASA: Congestion and Stretch Aware Static Fast Rerouting, 38th IEEE Conference on Computer Communications (INFOCOM), Paris, France, 2019

[2] Foerster K-T., Kamisinski A., Pignolet Y-M., Schmid S., Tredan G, Bonsai: Efficient Fast Failover Routing, 49th IEEE/IFIP International Conference on Dependable Systems and Networks (DSN-2019), Portland, OR, USA, Juin 2019

[3] Borokhovich M., Pignolet Y-M., Schmid S., Tredan G., Load-Optimal Local Fast Rerouting for Dense Networks, IEEE/ACM Transactions on Networking (TON), 26, 6, 2018

[4] Fraignaud P., Gafni E., Rajsbaum S., Roy M., Automatically adjusting concurrency to the level of synchrony, International Symposium on Distributed Computing (DISC), Austin, USA, LNCS (8784), pp.1-15, 2014

[5] Castañeda A., Fraigniaud P., Gafni E., Rajsbaum S., Roy M. Asynchronous Coordination with Constraints and Preferences. 23rd Int. Colloquium on Structural Information and Communication Complexity (SIROCCO 2016)

[6] Castañeda A., Rajsbaum S., Roy M., Convergence and covering on graphs for wait-free robots. J. Brazilian Computer Society, 24(1), 2018