What happens when two different nodes have the same Lamport clock ID

Question

With Lamport clocks, each node keeps its own counter. Before sending a message, a node increments its counter by one: LC(A)=LC(A)+1, and sends {1,msg} to B. Upon receiving a message, B updates its counter using the following formula: LC(B)=max(LC(B),LC(msg))+1=max(0,1)+1=2.

This works as expected when A and B take turns: A sends a message to B and B reacts by sending a message to A (or another node entirely).

However, this is not always the case. For example, in a typical TCP connection:

• A sends a message to B ("SYN")

• B replies to A ("SYN/ACK")

• A replies to B ("ACK") and then sends an actual request, such as an HTTP GET.

What happens (assuming both A and B start with their logical clocks set to zero):

• A increments its counter: LC(A)=1

• A sends {1,SYN} to B

• B updates its counter: LC(B)=max(0,1)+1=2

• B increments its counter: LC(B)=2+1=3

• B sends {3,SYN/ACK} to A

• A updates its counter: LC(A)=max(1,3)+1=4

• A increments its counter: LC(A)=4+1=5

• A sends {5,ACK} to B

• B updates its counter: LC(B)=max(3,5)+1=6

• At this point, A has to send another message (e.g. "GET /"). It increments its counter: LC(A)=5+1=6 and sends {6, GET /} to B.

As a result, both nodes have the same logical clock ID: LC(A)=LC(B)=6.

Is this a valid result? What happens next?

I have read that

Though there can be a case where both nodes have the same clock id for the key and if so we will have to rely on some external mechanism to resolve the conflict.

Source

But I'm not clear on the details. What kind of external mechanism could be adopted, if it is even needed?

Answer 1

tl;dr As Lamport writes at the top of page 561 of Time, Clocks, and the Ordering of Events in a Distributed System:

To break ties, we use any arbitrary total ordering $\prec$ of the processes.

To elaborate, ties are indeed possible and already anticipated by Lamport in the paper that introduced the concept. A somewhat minimal example would be one of two concurrent processes that each send a message to the other.

In the later literature, "process IDs" are often recommended to break those ties. Plain UNIX PIDs wouldn't necessarily work because those aren't necessarily unique across machines. Instead, one could combine a machine ID followed by a process ID.