Maekawa's Mutual Exclusion Algorithm:
Key Invariants

  1. Mutual Exclusion:
    Only one processor can be in the critical region at the same time.
  2. Voting for at most one candidate:
    Every processor can not cast his vote for more than one candidate at the same time, i.e., it casts its vote only if either it has not already cast its vote before for any candidate or it retrieved its vote from a processor or a processor for which it voted (processor-candidate) after leaving critical section gave this vote back.
  3. Vote Districts:
    Let P be a processor. Only a processor from P's district can vote for P.
Igor Rents
Last modified: Mon Mar 1 17:47:05 CET 1999
{ <=] [DAJ ] [RISC-Linz] [ University] [Search]