COMP 409 Lecture Notes - Lecture 10: Consistency Model, Sequential Consistency, Concurrent Computing
22 Mar 2018
School
Department
Course
Professor
Document Summary
T0: reads a variable: t1: maybe reads or writes, then t1 tree also necessary exists between t0"s actions, not univalent! Therefore, both t0 and t1 must both write: could write different variables, t0 and t1 write different variables. Order: x = , y = or y = , x = : they both write to the same variable x. R/w primitives have a consensus number of 1. Recall: r/w resistant, consensus #1, fa, ts, can solve consensus for more than one processor int decide(int v) { x = ts(decider, v); // old value if (x == 1) { return v; Book has a proof that ts, fa cannot solve consensus for 3 processes. Cas: consensus number is infinite int decide(int v) { In general, not functional: output can depend on timing/scheduling. 49 m2(); m2 follows m1 (since it is the way we wrote them) If m1 and m2 take place at a single time instance (atomic commit)
