Outline for February 8, 2001

  1. Greetings and felicitations!
  2. Maekawa's Algorithm
    1. Request sets satisfy the following conditions:
      1. for all 1 <= i, j <= n with i != j, Ri INTERSECT Rj != NULLSET
      2. for all 1 <= i <= n, pi IN Ri
      3. for all 1 <= i <= n, | Ri | = K
      4. pj is contained in K number of Ri
    2. Idea: every pair of processes has has a mediator (in both request sets) to mediate conflicts
    3. Only one outstanding REPLY per process, so each process gives permission to enter to only one other process
    4. Assumes messages delivered in order which they are sent
    5. To avoid deadlock, can INQUIRE whether someone cannot get it
    6. A FAILED message just means someone else is going in out of order
    7. Performance: between 3N and 5N messages
  3. Sanders' generalized protocol
    1. Inform set Ii is set of processes to be informed when pi enters or leaves CS
    2. Status set STi contains pids for which pi maintains status information; note: pi IN Ij => pj IN STi
    3. If pi IN Ii for all i, then necessary and sufficient conditions to guarantee mutual exclusion are:
    4. Ii SUBSET Ri
    5. Ii INTERSECT Ij != NULLSET or (Ri IN Rj and pj IN Ri)
  4. Suzuki-Kasami's broadcast protocol
    1. token-based
    2. uses sequence numbers, not clocks
    3. token has sequence numbers, associated queue
    4. how to handle stale requests? token's sequence number too high
  5. Raymond's tree-based protocol
    1. token-based
    2. think of token as at root of tree, root moves around

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/12/2001