CSE 124 Lecture Notes - Lecture 15: Bulletin Board System, Vector Clock, Master Sergeant
8 May 2018
School
Department
Course
Professor
Finishing Clocks
Vector Clock (VC) - a vector of Lamport clocks!
- label each event e w/ a vector V(e) = [c1,...,cn]
- ci is a “count” of events in process i
that causally precede e
- initially, ALL vectors are [0,...,0]
Two update rules:
1. For EACH local event on process i
, increment local entry ci
2. If process j
receives msg w/ vector [d1,...,dn]:
- Set EACH local entry ck = max{ck,dk}
- Increment local entry cj
Vector Clocks can Establish Causality
Rule for comparing vector clocks:
- V(a) = V(b) when ak = bk for ALL k
- V(a) < V(b) when ak <= bk for ALL k AND V(a) != V(b)
Concurrency: a || b if ai < bi AND aj > bj, for some i,j
V(a) < V(z) when there is a chain of events linked by → between a and z
VC Application: Causally-ordered Bulletin Board System
EACH post → multicast of the post to ALL other users
- Want: NO user to “see” a reply before the corresponding original message post
- Deliver message only after ALL messages that causally precede it have been delivered
- Otherwise, user sees a reply to a message they could NOT find
For example:
- User 0 posts
- User 1 replies to 0’s post
- User 2 observes: knows that 2 events happened: 1 from User 0, 1 from User 1
- It must not have gotten a message yet because User 0 and User 1 already
updated!
Limited “Fault Tolerance” In Totally-Ordered Multicast
- stateful server replication for fault tolerance
- but NO story for server replacement upon a server failure! → NO replication
Primary-Backup: Goals
Mechanism: Replicate and separate servers
Note on wording: multiple “servers” work together to produce a service!
Goal #1: Provide a highly reliable service
State Machine Replication
ANY server is essentially a “state machine”
Document Summary
Vector clock (vc) - a vector of lamport clocks! Label each event e w/ a vector v( e ) = [c 1 ,,c n ] C i is a count of events in process i that causally precede e. Two update rules: for each local event on process i , increment local entry c i, if process j receives msg w/ vector [d 1 ,,d n ]: Set each local entry c k = max{c k ,d k } V( a ) = v( b ) when a k = b k for all k. Concurrency : a || b if a i < b i and a j > b j , for some i,j. V(a) < v(z) when there is a chain of events linked by between a and z. Each post multicast of the post to all other users. Want : no user to see a reply before the corresponding original message post.
