Outline Theoretical Foundations continued Vector clocks review Casual ordering of messages 01 14 19 COP5611 1 Announcements This is no TA for this class I will do the grading and everything else by myself Homework 1 is due this Thursday Feb 6 2003 Turn your homework in hardcopy For the last problem attach a hardcopy of your program Lab 1 will be assigned today You can work as a team with most two members on each team 01 14 19 COP5611 2 Lamport s Logical Clocks review Implementation rules IR1 Clock Ci is incremented between any two successive events in process Pi Ci Ci d d 0 IR2 If event a is the sending of message m by process Pi then message m is assigned a timestamp tm Ci a On receiving the same message m by process Pj Cj is set to Cj max Cj tm d 01 14 19 COP5611 3 An Example 01 14 19 COP5611 4 Total Ordering Using Lamport s Clocks If a is any event at process Pi and b is any event at process Pj then a b if and only if either Ci a C j b or Ci a C j b and Pi Pj Where is any arbitrary relation that totally orders the processes to break ties 01 14 19 COP5611 5 A Limitation of Lamport s Clocks review 01 14 19 COP5611 6 Vector Clocks Implementation rules IR1 Clock Ci is incremented between any two successive events in process Pi Ci i Ci i d d 0 IR2 If event a is the sending of message m by process Pi then message m is assigned a timestamp tm Ci a On receiving the same message m by process Pj Cj is set to Cj k max Cj k tm k 01 14 19 COP5611 7 Vector Clocks cont 01 14 19 COP5611 8 Vector Clocks cont 01 14 19 COP5611 9 Vector Clocks cont Assertion At any instant i j Ci i C j i Events a and b are casually related if t a tb or tb ta Otherwise these events are concurrent In a system of vector clocks a a b iff t t 01 14 19 COP5611 b 10 Causal Ordering of Messages The causal ordering of messages tries to maintain the same causal relationship that holds among message send events with the corresponding message receive events In other words if Send M1 Send M2 then Receive M1 Receive M2 This is different from causal ordering of events 01 14 19 COP5611 11 Causal Ordering of Messages cont 01 14 19 COP5611 12 Causal Ordering of Messages cont The basic idea It is very simple Deliver a message only when no causality constraints are violated Otherwise the message is not delivered immediately but is buffered until all the preceding messages are delivered 01 14 19 COP5611 13 Birman Schiper Stephenson Protocol 01 14 19 COP5611 14 Schiper Eggli Sando Protocol 01 14 19 COP5611 15 Schiper Eggli Sando Protocol cont 01 14 19 COP5611 16 Schiper Eggli Sando Protocol cont 01 14 19 COP5611 17 Regarding Lab 1 For this project you can work as a team with at most two members per team Each team only needs to turn in one report However all the members are required to understand all the parts as you may be tested on the midterm or the final exam Three processes Bank Account Server Bank Office Clients Bank Office Mutual Exclusion Processes 01 14 19 COP5611 18
View Full Document
Unlocking...