Leslie Lamport reichte einen falschen Algorithmus ein. Ein Gutachter zerlegte ihn — dann fand er den Bakery Algorithm.

Leslie Lamport hielt das klassische Mutual-Exclusion-Problem einmal für ziemlich einfach. Er schrieb eine kurze Lösung, reichte sie bei einer Zeitschrift ein — und ein Gutachter zeigte ihm umgehend, dass sie falsch war.

Der Fehler beendete die Idee nicht.

Er ärgerte Lamport genug, um sich hinzusetzen und das Problem richtig zu lösen.

Das Ergebnis wurde zum Bakery Algorithm — einer der bekanntesten Ideen des Concurrent Computing und ein Ausgangspunkt für viele seiner späteren Arbeiten über verteilte Systeme.

Das Problem klingt einfach, bis zwei Dinge gleichzeitig passieren

Stell dir mehrere Prozesse vor, die dieselbe kritische Sektion betreten wollen.

Zu einem Zeitpunkt darf dort sicher nur einer sein.

Betreten zwei sie gleichzeitig, können gemeinsame Daten beschädigt werden.

Also braucht jeder Prozess eine faire Regel dafür, wer zuerst dran ist — ohne einen zentralen Schiedsrichter.

Lamport hielt veröffentlichte Lösungen zunächst für unnötig kompliziert.

Er schrieb einen einfacheren Algorithmus.

Der Gutachter fand den Fehler.

Lamport schrieb später, die Erfahrung habe ihn so sehr über sich selbst geärgert, dass er eine echte Lösung entwickelte. Gleichzeitig weckte sie sein dauerhaftes Interesse daran, die Korrektheit konkurrierender Algorithmen zu beweisen.

Die Lösung sah aus wie eine Bäckerei

Die Metapher ist fast peinlich alltäglich.

Du betrittst eine volle Bäckerei.

Du ziehst eine Nummer.

Du wartest, bis deine Nummer die kleinste unter allen Wartenden ist.

Dann bist du dran.

Lamport übersetzte diese soziale Regel in einen Algorithmus.

Jeder Prozess, der die kritische Sektion betreten will, wählt eine Nummer, die größer ist als die sichtbaren Nummern der anderen.

Die Prozesse warten in numerischer Reihenfolge.

Wählen zwei zufällig dieselbe Nummer, entscheidet ein fester Tie-Breaker wie die Prozess-ID.

Niemand muss in der Mitte stehen und alle koordinieren.

Die Reihenfolge entsteht aus den Nummern.

Das Bemerkenswerte ging über die Metapher hinaus

Der Bakery Algorithm hat eine ungewöhnliche Eigenschaft, die Lamport später besonders hervorhob.

Angenommen, ein Prozess schreibt gerade eine Zahl in den Speicher, während ein anderer sie exakt gleichzeitig liest.

Bei vielen Algorithmen wäre diese Überlappung gefährlich, wenn die Hardware keinen perfekt atomaren Lesevorgang garantiert.

Lamports Algorithmus toleriert eine deutlich schwächere Situation.

Der überlappende Lesevorgang kann einen seltsamen Zwischenwert sehen und der Algorithmus kann unter seinem Modell trotzdem Mutual Exclusion bewahren.

Lamport schrieb später, dass er diese Eigenschaft nicht absichtlich konstruiert habe.

Er habe das Gefühl, den Algorithmus nicht erfunden, sondern entdeckt zu haben.

Eine physische Analogie machte eine mathematische Struktur sichtbar

Die Bäckerei-Metapher funktioniert, weil sie zwei Fragen trennt, die Entwickler leicht vermischen.

Erstens: Wer möchte Zugriff?

Zweitens: In welcher Reihenfolge soll der Zugriff erfolgen?

Das Ticket erledigt nicht die Arbeit.

Es erzeugt eine Ordnung, die alle unabhängig beobachten können.

Dieses Designmuster geht weit über Bäckereien hinaus.

Queue-Nummer.

Timestamp.

Sequence Number.

Version Number.

Monotoner Zähler.

Sie alle verwandeln eine chaotische Diskussion darüber, „wer zuerst kam“, in etwas, worüber ein System reasoning kann.

Verteilte Systeme sind voller unsichtbarer Warteschlangen

Moderne Systeme sehen selten wie eine Bäckerei aus.

Sie sehen wie Datenbanken, Job-Worker, Message Broker, replizierte Services, Microservices und Cloud-Infrastruktur aus.

Aber das Koordinationsproblem ist überall.

Zwei Worker wollen denselben Datensatz aktualisieren.

Zwei Leader glauben, dieselbe Ressource kontrollieren zu sollen.

Mehrere Requests treffen ein, ohne dass eine perfekte globale Uhr jedem exakt sagt, welcher zuerst kam.

Verschiedene Maschinen sehen Events in unterschiedlicher Reihenfolge.

Der schwierige Teil ist nicht immer die Berechnung.

Der schwierige Teil ist Einigkeit über die Reihenfolge.

Lamports spätere Arbeiten — logische Uhren, Kausalität, replizierte Zustandsmaschinen, Paxos, Safety und Liveness — kehrten immer wieder zu Varianten dieses Problems zurück.

Sein erster Fehlschlag war vielleicht fast so wichtig wie die Lösung

Technikgeschichte wird gern so erzählt, als sähen brillante Menschen die Antwort sofort.

Lamports eigene Darstellung ist weniger schmeichelhaft und nützlicher.

Er sah ein berühmtes Problem.

Hielt es für einfach.

Reichte eine falsche Lösung ein.

Wurde korrigiert.

Und nahm danach Correctness sehr viel ernster.

Der Gutachter lehnte nicht nur einen Artikel ab.

Er half dabei, Lamports Arbeitsrichtung zu verändern.

In den folgenden Jahrzehnten wurde Lamport zu einer zentralen Figur in Theorie und Praxis konkurrierender und verteilter Systeme.

2013 erhielt er den ACM Turing Award für grundlegende Beiträge unter anderem zu Kausalität, logischen Uhren, Safety und Liveness, replizierten Zustandsmaschinen und sequentieller Konsistenz.

Die Lektion lautet nicht „Benutze Bäckerei-Tickets im Code“

Die tiefere Lektion handelt von Abstraktion.

Wenn ein Koordinationsproblem unübersichtlich wird, suche nach einer Regel, die jeder Teilnehmer lokal anwenden kann.

Gib dem System einen beobachtbaren Ordnungsmechanismus.

Mache Tie-Breaker explizit.

Dann reasoning über das Invariant, das erhalten bleiben muss.

Die elegantesten Ideen verteilter Systeme wirken oft einfach, nachdem sie entdeckt wurden.

Diese Einfachheit beweist nicht, dass das Problem leicht war.

Sie beweist, dass jemand das richtige Modell gefunden hat.

Welches komplizierte Koordinationsproblem in deinem System würde einfacher, wenn jeder Teilnehmer einfach „eine Nummer ziehen“ könnte?

Quellen

• Microsoft Research — A New Solution of Dijkstra’s Concurrent Programming Problem
• Microsoft Research — Proving the Correctness of Multiprocess Programs
• Leslie Lamport — My Writings
• ACM — Leslie Lamport, 2013 A.M. Turing Award
• Microsoft Research — Leslie Lamport Receives Turing Award
• Porträtquelle des Titelbilds — Leslie Lamport, Foto: Andrej Bauer, CC BY-SA 2.5 SI via Wikimedia Commons. Grafikkomposition und 16:9-Bearbeitung stehen unter derselben Lizenz.