Hagen Völzer
Fairneß, Randomisierung und Konspiration in verteilten
Algorithmen
Dissertation,
dec 2000
Fairneß (d.h. faire Konfliktlösung), Randomisierung (d.h.
Münzwürfe) und partielle Synchronie sind verschiedene
Konzepte, die häufig zur Lösung zentraler Synchronisations-
und Koordinationsprobleme in verteilten Systemen verwendet
werden. Beispiele für solche Probleme sind das Problem des
wechselseitigen Ausschlusses (kurz: Mutex-Problem) sowie
das Konsens-Problem. Für einige solcher Probleme wurde
bewiesen, daß ohne die oben genannten Konzepte keine Lösung
für das betrachtete Problem existiert.
Unmöglichkeitsresultate dieser Art verbessern unser
Verständnis der Wirkungsweise verteilter Algorithmen sowie
das Verständnis des Trade-offs zwischen einem leicht
analysierbaren und einem ausdrucksstarken Modell für
verteiltes Rechnen. In dieser Arbeit stellen wir zwei neue
Unmöglichkeitsresultate vor. Darüberhinaus beleuchten wir
ihre Hintergründe. Wir betrachten dabei Modelle, die
Randomisierung einbeziehen, da bisher wenig über die
Grenzen der Ausdrucksstärke von Randomisierung bekannt ist.
Mit einer Lösung eines Problems durch Randomisierung meinen
wir, daß das betrachtete Problem mit Wahrscheinlichkeit 1
gelöst wird. Im ersten Teil der Arbeit untersuchen wir die
Beziehung von Fairneß und Randomisierung. Einerseits ist
bekannt, daß einige Probleme (z.B. das Konsens- Problem)
durch Randomisierung nicht aber durch Fairneß lösbar sind.
Wir zeigen nun, daß es andererseits auch Probleme gibt
(nämlich das Mutex-Problem), die durch Fairneß, nicht aber
durch Randomisierung lösbar sind. Daraus folgt, daß Fairneß
nicht durch Randomisierung implementiert werden kann. Im
zweiten Teil der Arbeit verwenden wir ein Modell, das
Fairneß und Randomisierung vereint. Ein solches Modell ist
relativ ausdrucksstark: Es erlaubt Lösungen für das
Mutex-Problem, das Konsens-Problem, sowie eine Lösung für
das allgemeine Mutex-Problem. Beim allgemeinen
Mutex-Problem (auch bekannt als Problem der speisenden
Philosophen) ist eine Nachbarschaftsrelation auf den
Agenten gegeben und ein Algorithmus gesucht, der das
Mutex-Problem für jedes Paar von Nachbarn simultan löst.
Schließlich betrachten wir das ausfalltolerante allgemeine
Mutex-Problem -- eine Variante des allgemeinen
Mutex-Problems, bei der Agenten ausfallen können. Wir
zeigen, daß sogar die Verbindung von Fairneß und
Randomisierung nicht genügt, um eine Lösung für das
ausfalltolerante allgemeine Mutex-Problem zu konstruieren.
Ein Hintergrund für dieses Unmöglichkeitsresultat ist ein
unerwünschtes Phänomen, für das in der Literatur der
Begriff Konspiration geprägt wurde. Konspiration wurde
bisher nicht adäquat charakterisiert. Wir charakterisieren
Konspiration auf der Grundlage nicht-sequentieller Abläufe.
Desweiteren zeigen wir, daß Konspiration für eine große
Klasse von Systemen durch die zusätzliche Annahme von
partieller Synchronie verhindert werden kann, d.h. ein
konspirationsbehaftetes System kann zu einem randomisierten
System verfeinert werden, das unter Fairneß und partieller
Synchronie mit Wahrscheinlichkeit 1 konspirationsfrei ist.
Partielle Synchronie fordert, daß alle relativen
Geschwindigkeiten im System durch eine Konstante beschränkt
sind, die jedoch den Agenten nicht bekannt ist. Die
Darstellung der Unmöglichkeitsresultate und die
Charakterisierung von Konspiration wird erst durch die
Verwendung nicht-sequentieller Abläufe möglich. Ein
nicht-sequentieller Ablauf repräsentiert im Gegensatz zu
einem sequentiellen Ablauf kausale Ordnung und nicht
zeitliche Ordnung von Ereignissen. Wir entwickeln in dieser
Arbeit eine nicht-sequentielle Semantik für randomisierte
verteilte Algorithmen, da es bisher keine in der Literatur
gibt. In dieser Semantik wird kausale Unabhängigkeit durch
stochastische Unabhängigkeit widergespiegelt.
close
Felix C. Gärtner, Hagen Völzer
Redundancy in Space in Fault-Tolerant Systems
Technical Report,
Department of Computer Science, Darmstadt University of
Technology,
jul 2000
Ekkart Kindler, Hagen Völzer
Algebraic Nets with Flexible Arcs
Theoretical Computer Science,
2000
Michael Weber, Rolf Walter, Hagen Völzer, Tobias Vesper, Wolfgang Reisig, Sibylle Peuker, Ekkart Kindler, Jörn Freiheit, Jörg Desel
DAWN: Petrinetzmodelle zur Verifikation Verteilter
Algorithmen
Informatik-Berichte,
Humboldt-Universität zu Berlin,
dec 1997
Ekkart Kindler, Hagen Völzer
Flexibility in algebraic nets
Informatik-Berichte,
Humboldt-Universität zu Berlin,
nov 1997
Hagen Völzer
Verifying fault tolerance of distributed algorithms
formally: A case study
Informatik-Berichte,
Humboldt-Universität zu Berlin,
may 1997
Ekkart Kindler, Wolfgang Reisig, Hagen Völzer, Rolf Walter
Petri Net Based Verification of Distributed Algorithms:
An Example
volume 9 of
Formal Aspects of Computing 9 (4),
Springer-Verlag,
1997
Rolf Walter, Hagen Völzer, Tobias Vesper, Wolfgang Reisig, Ekkart Kindler, Jörn Freiheit, Jörg Desel
Memorandum: Petrinetzmodelle zur Verifikation verteilter
Algorithmen
Informatik-Berichte,
Humboldt-Universität zu Berlin,
aug 1996
Ekkart Kindler, Wolfgang Reisig, Hagen Völzer, Rolf Walter
Petri Net Based Verification of Distributed Algorithms:
An Example
Informatik-Berichte,
Humboldt-Universität zu Berlin,
may 1996
Wolfgang Reisig, Ekkart Kindler, Tobias Vesper, Hagen Völzer, Rolf Walter
Distributed Algorithms for Networks of Agents.
In Petri Nets (2),
1996