How to interpret the execution of distributed computation from time-space diagram?

Question

I'm following a course on Distributed Systems

http://www.ict.kth.se/courses/ID2203/index.html

and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram of an execution with the symbolic definition of the execution as a sequence of configurations and events.

In the model, an execution is defined as a sequence of configurations interleaved with events. As in:

<C,E,C,E,C,E...>

Where the C's are configurations (states of the nodes, including their buffers) and the E's are events, which in this model, are either Computation or Delivery events.

A computation event, comp(i), takes place at a single node, indexed by i, and modifies the buffers of node_i and the internal state of node_i and nothing else. A delivery event, del(i,j,m), removes message m from the output buffer of node_i and adds it to the input buffer of node_j.

A time space diagram of a particular execution is given in Slide 11 in this particular lecture: http://www.ict.kth.se/courses/ID2203/material/Lecture_2._Unit_3._Computation_theorem_and_causality.pdf

The arcs on a single timeline are comp(i) events at a particular node. The arcs between timelines are del(i,j,m) events between nodes i and j.

I'd like to interpret this diagram into a sequence of comp and del events, but it seems ambiguous. Specifically, a delivery is initiated from node 1 to node 2 -- del(1,2,m) -- and during the delivery a computation event at node 3 -- comp(3) -- takes place and completes before the delivery event completes.

Since the events in an execution are, by definition, totally ordered, I'm not sure if the comp(3) should precede the del(1,2,m) or vice versa.

Answer 1

Yes, it is ambiguous, and it is ok. A single space-time diagram can be linearized (collapsed into a compatible sequence of configurations and events) in many ways, potentially an exponential number of ways. E.g. imagine that you have 1000 nodes, and each of them performs a local operation. Obviously there's 1000! different ways to linearize this, because there are no inherent causality constraints in this situation.

It is not true that events in an execution are totally ordered. They are only partially ordered, using the partial order given by causality constraints (most of which are "a message is sent BEFORE it is received"). There are many total orders compatible with this partial order.