3.2.7 Complexité de l'algorithme en nombre de
messages
On peut distinguer deux situations selon la nature du
site demandeur, si le site demandeur est une racine et il détient un
jeton libre, il passe directement à la SC, le nombre de message
nécessaire dans ce cas est 0, si non, il va demander
à ses voisins un jeton, le nombre de message nécessaire dans ce
cas est K messages au maximum. Pour un site dans un arbre, l'entrée en
SC nécessite au minimum deux messages : un message de demande est un
autre message de réponse si la racine détient un jeton libre, si
non, le site racine doit demander un jeton supplémentaire où on a
besoin de K messages au pire des cas, donc au maximum K+2
messages seront échangés pour répondre à la
demande d'un site.
En conclusion, notre algorithme nécessite entre
0 et K+2 messages par entrée en SC, ce
qui représente une grande amélioration par rapport aux
algorithmes proposés dans ce cadre, la complexité est
donnée en fonction de K. La figure 3.3
résume la complexité de notre algorithme :
Figure 3.3 - La
complexité de notre algorithme.
Dans notre algorithme, on peut assurer la K-exclusion
mutuelle sans aucun échange de messages dans le meilleur cas, la K-EM
est assurée en échangeant K+2 messages seulement
dans le cas défavorable. On remarque que la valeur de N est absente dans
la complexité de notre algorithme.
| 
