University Institute of Information Technology 2009 B.Tech Computer Science and Engineering CSC 5780 Theory of Distributed Computing - Question Paper

CSC 5780 Theory of Distributed Computing
Homework Assignment 1
Please attach this as a front page to your solution.
issues one and two are for 10 points each, and issue three is for 20 points.
A summary of your scores will be on the 2nd page.
YOUR NAME in capitals: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1. Consider the model of asynchronous message passing with crash failures. A broadcast
service is clean when it has the subsequent property: if a process p crashes, then the
message broadcast by p in the last broadcast event is received by either all or by
none of the remaining processes. For the sake of readability of a specication of an
implementation of a broadcast service, we may want to distinguish ranging from low-level
operation of receiving and the corresponding implemented `receiving' in a broadcast
service by calling it `accepting'. Show that the subsequent is an implementation of a
clean broadcast:
To enable a broadcast of message m, a process p sends hstart :mi to all the
processes.
When a process q receives such a begin message from p, then q accepts mes-
sage m as broadcast by p, if q has not accepted it yet, and next sends
hecho : p;mi to all the processes.
When a process r receives a message hecho : p;mi, then r accepts message m
as broadcast by p, if r has not accepted it yet, and next sends message
hecho : p;mi to all the processes, if r has not sent it yet.
2. Consider the subsequent algorithm for 4 processes. every process begins with an initial
value and uses a variable vote. every process sends a message to all processes in a
round, including a message to oneself.
First round: every process sends its initial value.
If a process p receives 3 identical values, then p sets the vote to this value,
otherwise p sets the vote to null.
Second round: every process sends its vote.
If a process p receives 3 votes with the identical value dierent from null
then p decides on this value, otherwise p decides on the default value.
Is this a accurate consensus algorithm for at most 1 Byzantine process?
3. Consider the subsequent algorithm to solve general Byzantine consensus, provided a solution
for binary consensus. Every process p uses 3 private variables: 1 to store the
initial value, secondary-valuep and votep. a few default value is xed across all the
processes. The subsequent is a code for process p.
Preliminary round: Process p broadcasts its initial value.
If at lowest n ?? f copies of a certain value were received by process p, then p
sets its votep to 1, otherwise to 0. Process p sets its secondary-valuep to
the majority of vote values received, if such a strict majority exists, otherwise
to a default value.
subsequent rounds: An algorithm, say, A for binary consensus is run, with the
values of vote treated as initial values.
If process p decides on vote value one in the execution of A, then p's nal
decision is on its secondary-valuep, otherwise the nal decision is on the
default value.
(a) Is this a accurate reduction for f < n=3?
If you believe that this is the case, then prove the fact, which completes your
solution, otherwise provide a counter-example and proceed to the next point.
(b) Is this a accurate reduction for f < n=4?
If you believe that this is the case, then prove the fact, which completes your
solution, otherwise provide a counter-example and proceed to the next point.
(c) Develop a accurate reduction of general Byzantine consensus to binary Byzantine
consensus, that uses only 1 preliminary round of communication, and is accurate
for f < n=4.
If you are at this point, then you do believe that the provided algorithm is not a
accurate reduction, as justied by your counter-examples.
Hint: The material of Lecture three may be helpful.

Earning:   Approval pending.