Totally Ordered Multicast (also referred to as Atomic Broadcast) ensures that messages are delivered to all processes in the same order. It is a stricter form of ordering compared to FIFO (First In, First Out), which only guarantees that messages from the same sender are delivered in the order sent. Totally Ordered Multicast is critical in distributed systems, particularly in achieving consistency across replicated state machines.

Lamport clocks, named after Leslie Lamport, provide a mechanism for capturing causality among events in a distributed system without relying on synchronized physical clocks. Each process in a distributed system maintains a counter, which is incremented each time an event occurs (a message is sent or received). When a process sends a message, it includes its current counter value with the message. Receiving processes can then use this value to order messages causally.

How Lamport Clocks Work

Each process $P_i$ maintains a local logical clock $C_i$, which is a counter. The rules for Lamport clocks are:

1. Initialization: Every clock $C_i = 0$ at start.
2. Sending a Message: $C_i = C_i + 1$ before sending a message. Attach the timestamp $C_i$ to the message.
3. Receiving a Message: Upon receiving a message with timestamp $t$, set $C_i = \max(C_i, t) + 1$.

Implementing Totally Ordered Multicast with Lamport Clocks

In a distributed system using Lamport clocks, each process maintains a priority queue where incoming messages are stored until they can be delivered. Here’s how this is managed:

1. A process increments its Lamport clock and sends a message with this timestamp.
2. Upon receiving a message, the process places it in the priority queue.
3. Messages are delivered (taken from the queue and processed) in order of their timestamps.

The priorities ensure that causality is respected — a message that causally precedes another will have a lower timestamp and will thus be processed first.

Handling Non-FIFO Channels

The challenge comes when the underlying network does not guarantee FIFO delivery of messages — a later message might overtake an earlier message. Without FIFO, the system must handle out-of-order messages. The priority queue plays a crucial role here:

• Even if messages are received out of order, they won't be processed until all earlier messages (as determined by Lamport timestamps) are received and processed.

Example Scenario

Consider three processes (A, B, C), where:

• A sends messages M1 and then M2 to B and C.
• B sends message M3 to C after receiving M1 but before receiving M2 (due to network delay).

Here’s how message delivery would be handled:

• Each message (M1, M2, M3) is timestamped using the sender’s Lamport clock.
• If M3 arrives before M2 at C, it does not matter as M3’s timestamp will make it clear it was sent after M1 and before M2 was received by B.
• C will use its priority queue to sort M1, M2, and M3 correctly regardless of the order they were received.

Summary Table

Conclusion

Totally Ordered Multicast with Lamport Clocks offers a robust method for ensuring that all messages across distributed processes are delivered in a consistent and causal order, even under conditions of network delays and non-FIFO message delivery. This method is fundamental in systems requiring strong consistency guarantees, such as distributed databases and consensus protocols.