CSCE 668: Review for Exam 1
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 188.8.131.52
- 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
Here are some suggestions for things to know:
- Importance of carefully modeling system assumptions
- Failure-free message passing models, both synchronous
- 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
- 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