29

I was wondering if someone could explain in layman's terms what partial ordering of events are in a distributed system? Also, what is total ordering?

I would really appreciate this. I've looked all over the web and all I can find are mathematical equations defining partial and total ordering, but not in the context of a distributed system.

Thanks very much

2
  • What about a distributed system would make these terms significantly different from their mathematical definitions? Is there anything that does so?
    – Anon.
    Jan 6, 2011 at 22:46
  • Hi there. I don't really understand the mathematical equations that relate to partial and total ordering. I was just wondering if there were some definitions out there that people knew of. Thanks Jan 6, 2011 at 22:49

1 Answer 1

54

Total ordering is an ordering that defines the exact order of every element in the series.

Partial ordering of elements in a series is an ordering that doesn't specify the exact order of every item, but only defines the order between certain key items that depend on each other.

The meaning of these words is exactly the same in the context of distributed computing. The only significance of distributed computing to these terms is the fact that partial ordering of events is much commoner than total ordering. In a local, single-threaded application, the order in which events happen is totally ordered, implicitly, since the CPU can only do one thing at a time. In a distributed system, you generally only coordinate a partial ordering of those events that have a dependency on one another, and let other events happen in whatever order they happen.

Example, taken from the comments: If you have three events {A, B, C}, then they are totally ordered if they always have to happen in the order A > B > C. However, if A must happen before C, but you don't care when B happens, then they are partially ordered. In this case we would say that the sequences A > B > C, A > C > B, and B > A > C all satisfy the partial ordering

4
  • Aw man, that's fantastic! that clears things up for me. Thanks so much for that. So If I had 2 events, A and B. I could say that A and B are partially ordered if there is no "happened before" relationship between A and B or B and A? I could say that A and B are totally ordered if A 'happened before' B 'happened before' A in a SINGLE process? You're a legend! thanks ;) Jan 6, 2011 at 22:56
  • 3
    @Joeblack, not quite. If you have three events A, B, C, then they are totally ordered if they always have to happen in the order A > B > C. However, if A must happen before C, but you don't care when B happens, then they are partially ordered. In this case we would say that the sequences A > B > C, A > C > B, and B > A > C all satisfy the partial ordering. Jan 6, 2011 at 23:07
  • This answer is awesome and crystal clear specially the example part niceeee
    – solti
    Sep 15, 2013 at 18:46
  • If i understand correctly then following assumptions are true. In case of total order between entities only one ordered list of entities is possible but in case partial ordering more than one ordered lists are possible. Jun 17, 2015 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.