Definition:

The timestamp for an event is an n-tuple of integers, where n is the number of processes.

Each process assigns a timestamp to each event. The timestamp is composed of that process’s logical time and the last known time of every other process.

Example:

( P1_Last_Known_Time, P2_Logical_Time, P3_Last_Known_Time)

Book Notation:

1. Events: Every time an event is generated, a process increments its clock and assigns a timestamp to the event based on its knowledge of all the clocks in the system.
2. Sending messages: When a message is sent the timestamp of the sending event is given to the message.
3. Receiving messages: When a message is received, the process updates its knowledge of the system clock states by taking the maximum of each component of the message timestamp and its current knowledge of the system clock states. The receiving event gets this new timestamp.

Causally OR Concurrent:

Definition: "event a" causes "event b" if and only if ta < tb

1. they are not equal timestamps ( there exists i, ta[i] != tb[i]) and
2. each ta[i] is less than or equal to tb[i] (for all i, ta[i] <= tb[i])

Examples:

          Column A             Column B
     1)   (0,1,0)     and      (1,0,0)

     2)   (2,3,1)     and      (0,0,2)

     3)   (2,4,1)     and      (0,0,1)

     4)   (2,4,1)     and      (3,4,1)

Test Questions:

1. What are the advantages of vector clocks over Lamports logical clocks?
2. If two events are not causally related then they are concurrent. Explain why this is true.
3. Are the following pairs of timestamps concurrent or causally related?

      (2,3,4) and (1,4,4)
      (1,2,1) and (0,1,1)
      (3,4,1) and (0,0,2)
      

4. Can two timestamps be equal?
   If yes, give a system example.
   If no, give explanation.

References:

Go Back to the Operating Systems page.