CSE 223a Winter 2004
Homework 2
Due January 30, 2004
Please submit your answers by 2pm on January 30 via e-mail to marzullo@cs.ucsd.edu. Use as a
subject line your name and that the message is a solution to this
homework (e.g., Johann Johannsen CSE223a Homework 2 solutions).
- Using
the round-based protocol
for solving reliable broadcast for crash failures as a guide, give a
protocol
for uniform reliable broadcast for receive omission failures.
Do not use digital signatures.
Be sure to prove your protocol correct. Your proof need not be formal,
but it should be a valid argument.
- The
following is written in Fred B. Schneider's State Machine Approach
paper:
... If
processors
experience only failstop failures, then an ensemble containing t +
1 replicas suffices, and the output of the ensemble can be the output
produced
by any of its members.
Argue
that for this
statement to be true, a uniform failstop agreement protocol is needed
to
disseminate the commands to the state machine. If (nonuniform) failstop
agreement is used instead, what should the output of the ensemble be as
a function of the outputs of the members? The points you receive will
depend
on the degree of repliation you require; having n closer to t
is better.