Maekawa-Algorithmus

Der von Mamoru Maekawa 1985 vorgestellte Maekawa-Algorithmus kommt in einem verteilten System zur Anwendung, um den Zugang zu einem kritischen Abschnitt zu regeln und dabei wechselseitigen Ausschluss zu garantieren. Die Grundidee dieses Algorithmus ist es, nicht alle Prozesse zu fragen (wie zum Beispiel der Ricart-Agrawala-Algorithmus), sondern nur eine Teilmenge.

Der Algorithmus garantiert die Safety-Eigenschaft (nur ein einziger Prozess befindet sich im kritischen Abschnitt, kann aber ohne Verwendung von Vektorzeitstempeln zu Deadlocks führen (verletzt die Lifeness-Eigenschaft)).

Dabei benutzt man Voting Sets, ${\displaystyle V_{i}}$. Jeder Prozess ${\displaystyle P_{i}}$ hat ein Voting Set (${\displaystyle P_{i}\in V_{i}}$) und liegt in mindestens 2 Voting Sets. In jedem Voting Set befinden sich K Prozesse (${\displaystyle \forall i\left|V_{i}\right|=K}$), und zwei verschiedene Voting Sets haben mindestens ein gemeinsames Element (${\displaystyle \forall i\forall j[V_{i}\bigcap V_{j}\neq \emptyset ]}$) Als Annäherung für das Optimum (möglichst kleines K) wird ${\displaystyle K=2{\sqrt {N}}-1}$ benutzt. Man ordnet die Prozesse in einer ${\displaystyle {\sqrt {N}}\times {\sqrt {N}}}$ Matrix an und definiert das Voting Set ${\displaystyle V_{i}}$ als alle Prozesse die in der gleichen Spalte oder Zeile liegen wie ${\displaystyle P_{i}}$.