Soit l'algorithme du plus fort (bully algorithme) de Garcia-Molina:
Le site initiateur P_{i_0} diffuse le message El\left(c_{i_0},i_0\right) à tous les processus. Puis il attend.
A la réception d'un El\left(c_k,k\right) un processus P_i répond
De | Message | A | Pourquoi |
---|---|---|---|
P1 | El(5,1) | P2 | Init |
P1 | El(5,1) | P3 | Init |
P2 | El(7,2) | P1 | El de P1 |
P2 | El(7,2) | P3 | El de P1 |
P3 | El(9,3) | P1 | El de P1 |
P3 | El(9,3) | P2 | El de P1 |
P1 | Ack(1) | P2 | El de P2 |
P1 | Ack(1) | P3 | El de P3 |
P2 | Ack(2) | P3 | El de P3 |
P3 | El(9,3) | P1 | El de P2 |
P3 | El(9,3) | P2 | El de P2 |
P1 | Ack(1) | P3 | El de P3 |
P2 | Ack(2) | P3 | El de P3 |
On a des élections en cascade et à répétition parce que les sites reposent la question aux sites qui ont déjà répondu Ack
. Qui plus est, il n'y a pas de mécanisme pour déclencher Proclamation : faut dire que le site qui reçoit Ack
de tous les autres sites soit proclame “c'est moi le plus fort!”, soit dit à l'initiateur de le faire.
Pire des cas : le site le plus faible initie. Voyons pourquoi :
Ack
.Ack
,Ack
(dont le sien).k
initie : \displaystyle 1 + (k-1) + (k-2) + ... + 1 = 1+ \sum_{i=1}^{k-1} i = \frac{\left(k-1\right)k}{2}+1Pour réduire le nombre de messages:
Ack()
car il ne peut pas être le futur gagnant – combien ça réduit?