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(mij) IN LSi iff time of send(mij) < current time of LSi; similar for receive
    3. transit(LSi, LSj); inconsistent(LSi, LSj); consistent state is one with inconsistent set empty for all pairs LSi, LSj
    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 Ri for a process pi: set of nodes from which pi 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, Ri INTERSECT Rj != NULLSET
      2. equal effort rule: for all 1 <= i <= n, | Ri | = K
      3. equal responsibility rule: pj is contained in D number of Ri.
      4. for all 1 <= i <= n, pi IN Ri
  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.

Page last modified on 2/5/2001