Homework 3
Due 2 p.m., October 14, 2015

(1) Consider a network (similar to Ethernet) that supports reliable broadcast.
If any node transmits on the network, then all the nodes (including the
transmitter) receive that transmission reliably and identically. 

(a) If the system is synchronous, how many rounds are necessary to solve
consensus in presence of up to f crash failures? Provide a justification.

(b) If the system is asynchronous, is consensus achievable in the
presence of up to 1 crash failure? Provide a justification.


(2) From the bakery algorithm for mutex, remove all the lines of code
that use variable "choosing". Explain why the resulting algorithm may not
perform correctly.  


(3) Is it possible to implement a multi-reader multi-writer register using an ASO object? Explain briefly.

(4) In the simulation of multi-valued single reader (SR single writer (SW)  
register named R from binary SR SW register, a Write(R,v) operation is implemented
by first writing 1 to B[v], and the writing 0 to B[v-1] down to B[0].
What if the order is reversed (i.e., write 0 to B[v-1] down to B[0], and then
1 written to B[v])? Will the resulting algorithm achieve linearizability?

(5) Present an example execution to show that sequential consistency is not composable.