2.8 KiB
Notes et recherches sur le projet
Arithétique et ordres modulo
s ⊕ n = (s+n) % 2^(16) s ⊕ n = (s + n) and 65535
s ≼ s ′ lorsque ((s ′ − s) mod 2 16 ) < 32768 s ≼ s ′ lorsque ((s ′ − s) and 32768) = 0
Le sujet l'exprime de façon mathématique certes, mais c'est facile, si j'essaie de faire une aussi belle histoire que M. Chroboczek : imaginez que Paul et Gudule, qui sont dans une relation compliquée, se poursuivent en vociférant et en tournant autour d'un arbre. Est-ce que Paul est devant Gudule, ou Gudule devant Paul ? Imaginez en plus que la circonférence de l'arbre est 65536 millimètres (c'est un gros banian). Si Paul doit parcourir moins de millimètres pour attraper Gudule que l'inverse, alors on dit qu'il est derrière Gudule. Imaginez maintenant qu'il y a une graduation en millimètres autour du tronc du banian. Paul est à la graduation 10000, Gudule 20000. Ils courent dans le sens des graduations croissantes (dans quelques millisecondes, Paul sera à la graduation 10001 mm). Paul doit parcourir (20000 - 10000) mod 65536 = 10000 mm pour attraper Gudule, et Gudule,(10000-20000 ) mod 65536 = 55536 mm pour attraper Paul. 10000 < 55536. Donc Paul ≼ Gudule.
Alors voilà, toi et moi on veut connaître le statut Facebook de notre ami Paul. On se rencontre dans la rue (un jour, on aura le droit de nous rencontrer dans la rue), et tu me dis que la dernière fois que t'as regardé, il était « en couple », moi, je dis que la dernière fois, il était « c'est compliqué ». Qui de nous a l'information la plus récente ?
Comme Paul change son statut très souvent, il le publie avec un numéro de séquence. Il publie :
- en couple
- c'est compliqué
- célibataire
- en couple
- célibataire
- c'est compliqué
Moi, j'ai l'information « 2. c'est compliqué ». Toi, tu me dis non, « 4. en couple ». Je compare les deux numéros de séquence, je vois que 2 < 4, donc tu as l'information la plus récente, et je mets à jour ma donnée qui vaut maintenant « 4. en couple ». (Attention, on utilise ici l'ordre cyclique modulo 2^16, pas l'ordre usuel sur les entiers.)
Si par contre j'avais l'information « 6. c'est compliqué » et tu m'avais dit « 4. en couple », je me serais dit que c'est moi qui ai l'information la plus récente, et j'aurais ignoré l'information que tu me donnes.
Tu remarqueras qu'il y a trois morceaux d'information qui apparaissent :
(i) Paul est l'id de la personne qui publie la donnée ; (ii) Le numéro de séquence (2, 4, 6 etc.) (iii) La donnée elle-même (« en couple », etc.)
Maintenant, si tout le monde fait ça, et si Paul ne change pas son statut tout le temps, un jour on se sera mis d'accord : on aura tous la même information. L'algorithme aura convergé.
jch.irif.fr port UDP 1212