CSCE 668: Distributed Algorithms and Systems
Spring 2014
Homework
General Instructions:
 Check course
web page homework section
for more information, especially regarding use of LaTeX,
paper reviews and cover sheet.
 The numbered exercises are from the textbook.
 Do your best to give rigorous proofs of all the results.
 Be sure to explicitly list any assumptions that you
make (in case a question seems ambiguous and you are unable to get
clarification).
[Homework 1]
[Homework 2]
[Homework 3]
[Homework 4]
[Homework 5]
[Homework 6]
[Homework 7]
Homework 1: Due Fri, Jan 24, 10:20 AM
Problems:
 Exercise 2.2.
 Exercise 2.3.
 Exercise 3.3.
 Exercise 3.5.
Paper Review:
(If you are behind the TAMU firewall, following the links should
give you access to the full text of the papers.)

"A New Proof of the GHS Minimum Spanning Tree Algorithm,"
Y. Moses and B. Shimony,
International Symposium on Distributed Computing (DISC) 2006.

Johannes Schneider, Roger Wattenhofer: An optimal maximal independent set
algorithm for boundedindependence graphs. Distributed Computing 22(56):
349361 (2010)
Homework 2: Due Fri, Feb 7, 10:20 AM
Problems:
 Exercise 14.3.
 Prove that these three statements are invariants of Algorithm 9
(true in every configuration):
 At most one element in the Flags array is set to haslock.
 If no element in the Flags array is set to haslock, then
exactly one processor, say p_i, is in the critical section, and
exactly (Last  k) mod n processors are in the entry section,
each of them spinning on a different entry in the Flags array:
Flags[k], Flags[k+1 mod n], ..., Flags[Last1 mod n], where
k = myplace_i + 1 mod n.
 If Flags[k] is set to haslock, then no processor is in the
critical section, and exactly (Last  k) mod n processors are
in the entry section, each of them spinning on a different entry
of Flags: Flags[k], Flags[k+1 mod n], ..., Flags[Last1 mod n].
Then use these invariants to prove that Algorithm 9 provides mutual
exclusion and FIFO entry to the critical section.
 Exercise 4.8.
 Exercise 4.11. Do not simply appeal to Theorem 4.19. Instead, write
a proof from scratch. Model it after the proof of Theorem 4.19, but it
should be much simpler because there are only 2 processors, instead of n.
The point is make sure you understand the proof of Theorem 4.19 sufficiently
to write your own simplified version.
Paper Review:
(If you are behind the TAMU firewall, following the links should
give you access to the full text of the papers.)

Thomas Moscibroda and Rotem Oshman, "Resilience of mutual
exclusion algorithms to transient memory faults". In Proceedings of the
30th annual ACM SIGACTSIGOPS Symposium on Principles of Distributed
Computing (PODC), pp. 6978, 2011.

Ranganath Atreya, Neeraj Mittal, Sathya Peri: A QuorumBased Group
Mutual Exclusion Algorithm for a Distributed System with Dynamic Group
Set. IEEE Trans. Parallel Distrib. Syst. 18(10): 13451360 (2007)
Homework 3: Due Mon, Mar 3, 10:20 AM
Problems:
 Exercise 5.5
 For the case when f = 2 and n = 8, describe an execution of
the Phase King algorithm (Algorithm 16) that fails to solve the consensus
problem.
 Exercise 5.14
 Exercise 5.15
 Exercise 5.17
 Exercise 14.10
Paper Review:
(If you are behind the TAMU firewall, following the link should
give you access to the full text of the paper.)
Homework 4: Due Mon, Mar 24, 10:20 AM
Problems:
 Exercise 6.5
 Suppose we have a distributed system whose topology is an nelement r ing
instead of a clique. Assume the message delay on every link is in the
range [du,d]. What is the tight bound on the skew obtainable in this case?
Answering this requires two things: an algorithm for the upper bound
(together with a proof of its skew) and a matching lower bound on the skew.
 Exercise 13.2
 Exercise 13.5
 Using the model presented in Chapter 7, specify the binary consensus
problem (as in Section 5.1.2) for n processes, up to f of which
may crash.
 Prove that, in the failurefree case, if a broadcast service
provides both singlesource FIFO ordering and total ordering, then
it also provides causal ordering.
 Exercise 8.9
Paper Reviews:
(If you are behind the TAMU firewall, following the links should
give you access to the full text of the papers.)
Homework 5: Due Wed, Apr 2, 10:20 AM
Problems:
 Exercise 8.10
 Exercise 9.5
 Exercise 9.6
 Exercise 9.7
(No paper review)
Homework 6: Due Mon, Apr 21, 10:20 AM
This assignment has fewer problems and more paper reviews (3) than the
others. It is now complete.
Problems:
 Exercise 10.5. Justify your answers by either providing an
algorithm or proving an impossibility result.
 Exercise 10.11
 Exercise 15.5
 Exercise 15.7
Paper Reviews:
(If you are behind the TAMU firewall, following the links should
give you access to the full text of the papers.)

Dan Dobre, Ghassan Karame, Wenting Li, Matthias Majuntke, Neeraj Suri,
and Marko Vukolic. "PoWerStore: proofs of writing for efficient
and robust storage." In Proceedings of the 2013 ACM SIGSAC conference
on Computer & communications security (CCS '13). ACM, New York, NY,
USA, 285298. DOI=10.1145/2508859.2516750

Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin
Reed. 2010. ZooKeeper: waitfree coordination for internetscale
systems. In Proceedings of the 2010 USENIX conference on USENIX annual
technical conference (USENIXATC'10). USENIX Association, Berkeley, CA,
USA, 1111.

W. Chen, S. Toueg, M.K. Aguilera, "On the Quality of Service of
Failure Detectors," IEEE Transactions on Computers, pp. 561580, May,
2002.
Homework 7: Due Tue, Apr 29, 10:20 AM
Problems:
 Exercise 16.16
 Exercise 16.17
 Exercise 16.22
Paper Review:
(If you are behind the TAMU firewall, following the link should
give you access to the full text of the paper.)

N. Alon, H. Attiya, S. Dolev, S. Dubois, M. PotopButucaru, S. Tixeuil.
"Pragmatic Selfstabilization of Atomic Memory in MessagePassing Systems."
Stabilization, Safety, and Security of Distributed Systems (SSS),
Lecture Notes in Computer Science Vol. 6976, 2011, pp. 1931.