Algorithme distribué d'orientation de graphes dans un environnement asynchrone et avec pannes

International audienceNous nous intéressons dans ce papier à l'orientation de graphe de manière distribuée. Plus précisément, nous cherchons à calculer une orientation minimum, c'est-à-dire à minimiser le degré sortant maximum d'un nœud du graphe. Ce problème d'orientation est notamment une modélisation naturelle pour des problèmes d'allocation de ressources. Nous présentons l'algorithme AvrDegAsync qui fonctionne dans un environnement distribué où les communications sont asynchrones et où les nœuds peuvent être en panne. Notre algorithme garantit une 2(2 + ε)-approximation de l'orientation optimale en utilisant un nombre logarithmique de diffusion. De plus, il ne nécessite pas de connaissance sur le graphe comme le nombre de nœuds ou encore sa densité