CSE 223a Winter 2004
Homework 4
Due March 12, 2004
Please submit your answers by 2:00 PM on March 12 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., Ivan Ivanov CSE223a Homework 4 solutions).
- In the
Masking Byzantine Quorum system algorithm of Malkhi and Reiter, the
replication requirement is n
> 4t. In their algorithm,
to write, a client sends an update to all of the servers. The write
operation returns when the client gets acknowledgements from some
quorum Qw
of servers. To read a value, the client gets a set of
values from some quorum Qr of servers. If B is the set of faulty servers,
then Qr - Qw - B are the servers
that can have "stale" values. This algorithm implements a multiple
writer, multiple reader safe register.
Notice that the write
operation will eventually send an update to all of the servers, including the
servers in Qr - B. Use this observation
to develop another Masking Byzantine Quorum System algorithm that
requires less replication than n
> 4t. Give the new
replication replication requirement and explain what semantics it
implements (such as a multiple writer, multiple reader safe
register).
- In the
indistinguishable failstop algorithm, indistinguishability
is based on a simple set of events: send, receive, and so
on. Suppose that we included events that represented reading and
writing to files. Show that the iFS
properties iFS1 and iFS2a-d are not sufficient to ensure that an
executions is indistinguishable from an execution in FS.