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

Marks: 5 M

Year: May 14

• 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.