ECE 526 Distributed Algorithms
Fall 2015
Homework 2

Due September 23, 2016 by 2:00 p.m.


(1) Prove that there is a unique maximal consistent cut preceding any given cut. 

(2) Consider three processors p0, p1 and p2, where p0 and p1 are connected by communication channels, and p1 and p2 are connected by communication channels. p0 and p2 cannot send messages to each directly (but may potentially forward messages via p1). Assume that the delay on each communication channel is in the range [d-u,d]. Determine (and prove) the tight upper bound on the clock synchronization skew obtainable in this case.