#algorithmes #fr #distributedalgorithms #sorbonne

Critères d'evaluation

La complexité en nombre d'operations est peu significative.

Si la complexité en nombre total de messages échangés est pris, donc on a un critère biaisé si les tailles de messages sont très differentes.

Complexité en temps

En l'absence d'horloge globale 2b4-temporal-models, on utilise une notion idéalisée du temps:

• les temps d'execution d'un pas de calcul est nul
• le temps de transmission d'un message nécessite une unité de temps

Alors la complexité en temps = longue de la plus longue chaîne de messages.