Search code examples
computer-sciencedistributed-computing

Example of logical order and total order in distributed system

Total order:

Lamport timestamps can be used to create a total ordering of events in a distributed system by using some arbitrary mechanism to break ties (e.g. the ID of the process).

Logical order:

When two entities communicate by message passing, then the send event is said to 'happen before' the receive event, and the logical order can be established among the events

enter link description here

Can anyone give me an example where I can see the differences of logical order and total order? What is the difference of both orders?

Solution

  • Since you are looking for an example about differences between Logical order and Total order, here is a little story my old distributed algorithm teacher told us when he wanted to explain that specific topic.

    • Let's say that A owes B some money.
    • A tells B on the phone, that A is going to credit B's account in A's local branch at 6 p.m.
    • So anytime after 6 p.m., B can withdraw money from A's bank.
    • Let's say B is nice and tells A's branch that at 8 p.m. they can debit A's account the money that A owes B.
    • So B's branch is going to basically do a debit call to the central bank server asking for the money that is owed by A to be transferred to B's account and that's what is going to happen.
    • B has been given A enough time to make sure that A have indicated to B bank, that A have enough money, so that A's debit transaction can go through.
    • B would think it should go through, right?
    • But it turns out, that B's branch's local time is far ahead of real time. The branch thought it was 8 p.m., it was not quite 8 p.m., yet.
    • A is keeping his word, exactly at 6 p.m., A's branch happens to be good with the time. (synced with the real time)
    • So at 6 p.m., A has done the credit of the amount that A owes B to A's central bank server.
    • Unfortunately, the central bank server, in real time, got B's message much earlier than the time at which A sent his message.
    • The central bank server isn't looking at any logical time. It is looking at real time when there's a debit transaction coming in. Is there money in the bank for paying those debit transactions?
    • No, there isn't. So B's request is declined. This is the result of the fact that in real world scenarios, logical clocks are not good enough.

    So what caused the problem here? It is the fact that B's branch's notion of real time is completely at odds with real time. The computer at B's local bank might have a clock that is drawing near with the respect to real time.It's either going faster than real time or it is going slower than the real time.

    It so happens that A's, A's branch's time is is perfectly in sync with the real time, but that doesn't help A.

    This example seems a little complex to understand straightaway. This is known as the clock synchronization problem.

    I invite you strongly to read Lamport's paper concerning Time, Clocks, and the Ordering of Events in a Distributed System as he presents a different way to explain the differences.

    You might also find these references quite handy :

    I hope this helps.