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, R_i INTERSECT R_j != NULLSET
      2. for all 1 <= i <= n, p_i IN R_i
      3. for all 1 <= i <= n, | R_i | = K
      4. p_j is contained in K number of R_i
   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 I_i is set of processes to be informed when p_i enters or leaves CS
   2. Status set ST_i contains pids for which p_i maintains status information; note: p_i IN I_j => p_j IN ST_i
   3. If p_i IN I_i for all i, then necessary and sufficient conditions to guarantee mutual exclusion are:
   4. I_i SUBSET R_i
   5. I_i INTERSECT I_j != NULLSET or (R_i IN R_j and p_j IN R_i)
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: [email protected]

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.