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