Skip to content

README.md

Latest commit

 

History

History
33 lines (23 loc) · 1.41 KB

README.md

File metadata and controls

33 lines (23 loc) · 1.41 KB

Maekawa's algorithm: Generating request sets

EC60012 - Advanced Operating Systems Design - Assignment 3

Utkarsh Patel

Maekawa's algorithm

Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.

Quorum set (or request set) $R_i$ for each site $S_i$ must abide by the following rules:

  • $\forall i \forall j, R_i \cap R_j \ne \phi$
  • $\forall i, S_i \in R_i$
  • $\forall i, | R_i | = K$
  • Site $S_i$ is contained in exactly $K$ request sets

Therefore, $\forall i, | R_i | \geq \sqrt{N - 1}$

Generating request sets

If the number of site can be represented as $N = K(K - 1) + 1$, then the problem translates to generating a projective plane of order $K-1$. Solution exist if $K-1$ is a power of prime, $p^m$, for some prime $p$. For other cases, we can relax the last two conditions to create degenerate request sets.

Build and run

$ git clone https://github.com/utkarsh512/maekawa.git
$ cd maekawa
$ make
$ ./maekawa

References