##
CSCE 668: Review for Exam 1

Spring 2014

*You may use your own notes on one 8.5 by 11 inch sheet of paper (you might
write on both sides) during the exam, but no other resources.
*
Review the following:

- Lectures through Wed, Feb 5.
Powerpoint slides are available online.

- Readings from textbook:
- Chapter 1
- Chapter 2
- Chapter 3; skip 3.4.2.3
- Chapter 4

- Homeworks 1 and 2 and their solutions (gone over in class), including
the assigned papers.

The format of the exam will be some short answers and some
"work-out" problems.
Here are some suggestions for things to know:

- Importance of carefully modeling system assumptions
- Failure-free message passing models, both synchronous
and asynchronous
- Graph algorithms:
broadcast and convergecast on a spanning tree; building spanning
trees; complexities of these algorithms
- Leader election for asynchronous rings: O(n^2) messages algorithm;
O(n log n) messages algorithm; general idea of Omega(n log n)
messages lower bound
- Leader election for synchronous rings: O(n) messages algorithm;
general idea of Omega(n log n) messages lower bound
- Failure-free asynchronous shared memory model
- Mutual exclusion with powerful shared objects: test-and-set
algorithm; RMW algorithm; n lower bound on number of
memory states
- Mutual exclusion with read-write registers: bakery algorithm;
2-processor algorithm; tournament algorithm; general idea of
n lower bound on number of registers
- General concept of "fast" mutual exclusion