Horodatage Lamport avec temps de parcours de message variable

Question

Je pense que je ne comprends pas quelque chose avec Lamport timestamps. Il semble qu'il s'attend à ce que les messages prennent le même temps pour se déplacer entre les points de terminaison distribués.

Disons que ce processus p1 envoie des messages m1 et m2 séquentielle pour traiter p2. Suite à la pseudocode dans la section algorithme de l'article, nous avons:

# we start at 0 
time(p1) = 0 

# we send m1 
time(p1) = time(p1) + 1 = 1 
send(m1, 1) 

# we send m2 
time(p1) = time(p1) + 1 = 2 
send(m2, 2) 

Si m1 atteint p2 avant m2 tout va bien. Mais si m2 vient d'abord, nous obtenons:

# we start at 0 
time(p2) = 0 

# we receive m2 first 
time(p2) = max(2, time(p2)) + 1 = max(2, 0) + 1 = 3 

# we receive m1 second 
time(p2) = max(1, time(p2)) + 1 = max(1, 3) + 1 = 4 

Donc, à l'heure locale de p2 (time(p2)) m2 a le temps de 3 et m1 a le temps de 4. C'est le contraire de l'ordre dans lequel les messages ont été envoyés à l'origine. Ai-je besoin de quelque chose de fondamental ou est-ce que les horodatages Lamport nécessitent des durées de déplacement constantes pour fonctionner?

Answer 1

Le temps d'un message est le temps contenue dans le message, et non le temps du processus de réception du message. Le temporisateur est logiquement partagé entre les deux processus, il doit donc compter les événements (envois) des deux processus, c'est pourquoi le récepteur ajoute un à l'instant où il reçoit un message. L'algorithme tente de synchroniser les timers des deux processus, même si les messages sont perdus ou retardés, ce qui explique pourquoi le récepteur prend le maximum de sa vue sur l'heure et la vue de l'expéditeur sur l'heure trouvée dans le message . Si ce n'est pas la même chose, un message a été perdu ou retardé. Cela aura pour résultat que les deux processus auront des vues différentes de l'heure, mais les horloges seront resynchronisées lorsque le message suivant est envoyé et reçu (dans les deux sens).

Si les deux processus envoient simultanément un message, les deux messages contiendra le même temps, ce qui explique pourquoi il n'est pas un ordre total. Mais les horloges seront toujours resynchronisées.