30

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

Joeblackdev
  • 7,217
  • 24
  • 69
  • 106
  • What about a distributed system would make these terms significantly different from their mathematical definitions? Is there anything that does so? – Anon. Jan 06 '11 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 – Joeblackdev Jan 06 '11 at 22:49

1 Answers1

56

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

JSBձոգչ
  • 40,684
  • 18
  • 101
  • 169
  • 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 ;) – Joeblackdev Jan 06 '11 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. – JSBձոգչ Jan 06 '11 at 23:07
  • This answer is awesome and crystal clear specially the example part niceeee – solti Sep 15 '13 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. – user2772346 Jun 17 '15 at 12:37