Outline for February 6, 2001

1. Greetings and felicitations!
   1. Friday times good, also Tuesday 3-4:30. Please send me your preferences!
2. Global state
   1. Show problem of slicing state when something is in transit
   2. Define local state; send(m_ij) IN LS_i iff time of send(m_ij) < current time of LS_i; similar for receive
   3. transit(LS_i, LS_j); inconsistent(LS_i, LS_j); consistent state is one with inconsistent set empty for all pairs LS_i, LS_j
   4. Consistent global state: Chandry-Lamport
3. Termination detection
   1. Haung
4. Differences with non-distributed algorithms
   1. no shared memory, no common clock
   2. unpredictable message delays
5. Types of algorithms
   1. non-token algorithms: Lamport, Ricart and Agrawala, Maekawa
   2. token-based: Singhal, Raymond
   3. detection and recovery
6. System model
   1. states: requesting (entry section), executing (critical section), idle (remainder section), idle token (like idle, but you have the token)
   2. site: many others requesting entry, all are queued and served one at a time
7. Solution assumptions
   1. process names can be integers
   2. messages received in the order sent, in a finite amount of time, and correctly
   3. any process can communicate with any other process
8. Solution requirements
   1. mutual exclusion
   2. no deadlocks (progress)
   3. no starvation (bounded wait)
   4. fairness (requests executed in the order made, or in the order they arrive in system)
   5. fault tolerance (if a system fails, the algorithm can recover and continue to function)
9. Performance measures
   1. Performance under varying loads (low, high)
   2. Best, average, worst case performance
10. Terminology for non-token based protocols
    1. Request set R_i for a process p_i: set of nodes from which p_i must obtain permission to enter critical section
    2. Requests ordered bytimestamps: (time, pid); the pid is used to disambiguate equal timestamps
    3. Request sets satisfy the following conditions:
       1. pairwise non-null intersection property: for all 1 <= i, j <= n with i != j, R_i INTERSECT R_j != NULLSET
       2. equal effort rule: for all 1 <= i <= n, | R_i | = K
       3. equal responsibility rule: p_j is contained in D number of R_i.
       4. for all 1 <= i <= n, p_i IN R_i
11. Obvious solution: pick a single controlling site
    1. Advantages: 3 messages per request (site REQUEST, controller REPLY, site RELEASES)
    2. Disadvantages: single point of failure, congestion, controller does all the work
12. Lamport's
    1. Request set is all processes
    2. Performance: 3(n-1) messages
13. Ricart and Agrawala's
    1. Request set is all processes
    2. Performance: 2(n-1) messages

The handouts do not translate into HTML well because of the notations. Please download the PDF or Postscript version from the class home page.

Matt Bishop Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060 Fax: +1 (530) 752-4767 Email: bishop@cs.ucdavis.edu

Copyright Matt Bishop, 2001. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print.