ECE 526 Distributed Algorithms
Fall 2015
Homework 1
Due September 9, 2016 by 2:00 p.m.
(1) Show that f rounds suffice for achieving consensus in presence of up to f crash failures in a synchronous system when number of processors n = f+1.
(2) Consider the proof of the lower bound of f+1 rounds for consensus with up to f failures when n>f+1. The proof shows that there exists an initial bivalent configuration.
Suppose that we weaken the validity requirement to only require that the output of the consensus algorithm be NOT a constant. In this case, show that there exists an initial bivalent configuration.
Suggested exercises:
https://courses.engr.illinois.edu/ECE526/fa2014/1hw.pdf