ECE 526 Distributed Algorithms (Fall 2015)
Homework 4
Due 2 p.m., November 4, 2015 (Thursday)


Please type your answers. You may submit your solution via e-mail, or slide a printout under my office door (456 CSL).


Some potentially useful references:

* Section II of the paper at http://www.mit.edu/~jnt/Papers/C-10-ISIT-benezit.pdf 
* Slides at http://disc.ece.illinois.edu/seminars_tutorials/distributed%20resilient%20consensus.pptx useful.
* Papers listed for reading for Lecture 16


(1) This question pertains to the paper "Robust Consensus over Unreliable Links: Analysis Using Coefficients of Ergodicity" in assigned readings (Lecture 16).

Consider a network consisting of three nodes, named 1, 2 and 3. (i,j) denotes a directed link from node i to node j. The nework contains directed links (1,2), (2,3) and (3,1). Assume that each link is reliable in each round with probability p = 0.9.

(a) Will the average consensus algorithm in the paper perform correctly in the above network?

(b) In a particular iteration, suppose that the link (1,2) is unreliable, and the other links are reliable. Determine the transition matrix M that includes entries for the "virtual buffers" as well. In the state vector, assume that the states are included in the following order: node 1, node 2, node 3, buffer (1,2), buffer (2,3), buffer (3,1). 

(c) Will the average consensus algorithm in the paper perform correctly in the above network if we replace link (1,2) by link (2,1)?



(2) Consider a network consisting of four nodes, named 1, 2, 3 and 4. The network contains only undirected (or bi-directional) links. Let (i,j) denotes an undirected link between nodes i and j. The network contains undirected links (1,2), (2,3) and (3,4). 

The nodes perform weighted averaging using weights that form a matrix M. With vector V[t] representing the state of the nodes after t iterations, the state updates can represented as follows:

V[t] = M * V[t-1]

where Vi[0] is the input (or initial state) of node i.

(a) Present a transition matrix that will achieve approximate average consensus using the above update repeatedly.

(b) Present a transition matrix that will achieve approximate consensus, but NOT average consensus, when using the above update repeatedly. Briefly explain why the chosen matrix will NOT lead to average consensus.

Recommended exercise: How many iterations will be needed using your choice of M above so that the state of the nodes will be within a given epsilon of each other?


(3) Consider the paper "Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs" (listed in readings for Lecture 16). Consider the following model for the faulty nodes: in any given round, a faulty node must send identical messages to all its outgoing neighbors. This modified model is weaker than the Byzantine model. For the modified model, show that the necessary condition in the above paper is no more necessary. (One possible solution is to show a network that does not satisfy the necessary condition in the above paper, and yet satisfies the correctness conditions in the paper.)


(4) Consider the paper "Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs" again. If the system contains only 4 nodes, is it possible for any network other than the complete graph to satisfy the necessary condition in the paper? Explain your answer.