Vector Time Stamp mechanism for synchronization is used for capturing casuality of events. Justify

This question appears in Mumbai University > Parallel And Distributed System subject

Marks: 5 M

Year: May 14

1 Answer
  • Lamport timestamps does not say anything about the relationship between events by comparing their time values. It also does not capture causalities.
  • The receipt of an article always casually precedes the posting of a reaction. If casual relationships are to be maintained within a group of processes then the receipt of the reaction to an article should always follow the receipt of that article.
  • If two articles or reactions are independent then their order of delivery should not matter.
  • Causality can be captured using vector timestamps. A vetor timestamp VT(a) for event a will have the property such that if VT(a) < VT(b) for event b then event a is known to causally precede event b.
  • Vector timestamps are constructed by letting each process Pi maintain a vector Vi with the following properties: Vi [ i ] is the number of events that have occurred at Pi If Vi[ j ] = k then Pi knows k events have occurred at Pj
  • The first property is maintained by incrementing Vi[ i ] at the occurrence of each new event that happens at process Pi.
  • The second property is maintained by piggy-backing vectors along with sent messages.
  • A receiver is informed about the number of events that occurred at Pi and also how many events at other processes have taken place before Pi sent message m.
  • When Pj receives m, it adjusts its own vector by setting each entry Vj[k] to max{Vj[k],vt[k]}.
  • The vector now reflects the number of messages that Pj must receive.
Please log in to add an answer.