CS 564, Distributed algorithms

This assignment can be solved in teams of no more than four students,

is worth three tokens, and
is due on 15 April at 11:59 pm

This assignment is on distributed algorithms, which are a layer on top of network communication. You
have already seen how communication takes place and how application protocols work; now it is time to
investigate how to put these to work in an algorithms that consists of pieces running on several machines.
This is a review work. There is no problem to solve, no new result to discover, and no program to write.
Instead you are asked to perform a review of the existing literature and present the results therein in an
organized fashion.
1 Distributed agreement
A fundamental problem in distributed computing is to achieve correct overall system functionality in the
presence of faulty processes. This often requires processes to agree on some data that is needed during
computation. This problem is referred to as distributed agreement or consensus. Since some processes may
fail, any distributed agreement protocol must be fault tolerant, so that the processes must provide their own
values, must communicate with each other, and must agree on a consensus value.
One of the simplest approaches to distributed agreement is for all processes to agree on a majority value,
meaning a value that receives least one more than half of the available process votes. Note however that
one or more faulty processes may skew the outcome such that an incorrect consensus is reached (or maybe
no consensus can be reached at all).
A correct distributed agreement protocol must have the following three properties: termination (each
correct process must eventually decide on some value), integrity (if all the correct processes propose the
same value v then they all must decide on v), and agreement (every correct process must agree on the same
value).
2 Your task
Your task for this assignment is to survey the existing agreement (or consensus) algorithms for distributed,

asynchronous systems, and present your findings in a coherent report. You must consider as many algo-
rithms as you can find. Address the correctness and complexity of all the algorithms you found (in the

presence of both crash and byzantine failures), and also provide a critical comparison of all of them.

The report must be written in your own words; copying and pasting from various papers is not accept-
able. It must present a coherent picture of the problem and must compare all the algorithms presented. You

do not need to find anything new, but whatever you find must be presented coherently and in your own
words.
Your report must include proper citations of primary references such as journal or conference papers.
Textbooks and other course material could be used (and are a useful resources), but are not considered
primary references and so must be complemented by primary references. Enciclopaedic reference (such
as to Wikipedia articles) are not suitable and should not be used (you must go instead to the primary
references). I expect a minimum of 5 primary references and perhaps a few more secondary references.

1

It is not enough to provide a list of references, you must also cite them in the text; in fact I will discard
any reference that is not cited.
3 What to submit
You must submit your findings in a report typeset to PDF. Submit using the submit program and the course
cs564 (not cs464 as for the other assignments).
Your report will be marked for completeness, the appropriateness of references, the organization of your
summary, and the clarity of presentation. The length of the report is not part of the marking scheme. As a
guideline on length I expect that the length of most reports will hover around 10 pages (with 1-inch margins
all around and typeset in 10- or 11-point font).