HW3SolutionsCS425FA15 ECE 428|all you need

HW3 Solutions: CS425 FA15 1. (Solution and Grading by: Alex Zahdeh) Assume the processes are pi with 1≤i≤5. Consider the scenario when, at each round i where 1≤i≤5, pi crashes after sending its value array to only pi+1 . In that case, after five rounds, p6 ’s set will be {1,2,3,4,5,6,7,8,9,10} whereas every other living node’s set will be {2,3,4,5,6,7,8,9,10}. This is because p1 ’s value is not forwarded due to the successive five failures. So p6 will decide on 1, whereas all other processes will decide on 2 (remember that the “min” taken in the final step of the algorithm is min by id, not min by value proposed). Therefore consensus is not achieved. 2. (Solution and Grading by: Guangxiang Du) a. It is safe, because 2/3rds is larger than 50%, 2 groups of 2/3rds would intersect. Therefore, there could be at most one leader and one decided value. b. Eventual liveness is satisfied. c. The new version slower than majority version because it takes longer to receive more votes (⅔ 50%) . 3. (Solution and Grading by: Qi Wang) a. They are serially equivalent. All conflicting pairs follow order T1­T2. b. They are not serially equi