Hallo!

Ich bin gerade beim Nacharbeiten, inzwischen sind die Punkte bei den Übungsaufgaben ja nicht mehr so kritisch.

Dabei bin ich über Satz 8.8 (Skript S. 312) gestolpert, der da besagt:

Es gibt keinen synchronen, nicht-uniformen anonymen Auswahlalgorithmus.

Ein Auswahlalgorithmus soll ja dazu dienen, in einem Netzwerk verteilter Rechner genau einen Rechner zu bestimmen, der sich dann als einziges ausgewählt fühlt.
An diesem Satz 8.8 stört mich jetzt der Zusatz "nicht-uniform". Ein Netzwerk ist uniform, wenn die Anzahl seiner Knoten (d.h. der Prozesse/Prozessoren) nicht bekannt ist - bzw. ein Algorithmus ist uniform, wenn er die Größe des Netzwerkes nicht kennt oder nicht benutzt. Der Satz suggeriert nun, dass es zwar keinen synchronen, nicht-uniformen, anonymen Auswahlalgorithmus gibt, wohl aber einen uniformen (sonst hätte das nicht explizit dort stehen müssen - in Satz 8.9 wird extra gesagt, dass Satz 8.9 sowohl für uniforme als auch für nicht-uniforme Netzwerke gilt).
Wie kann es aber sein, dass es zwar einen Algorithmus gibt, der die Anzahl der Knoten nicht benutzt, jedoch keinen, der die Anzahl der Knoten benutzt?

Vielen Dank für alle Hinweise.

IIRC wird erst der Satz so wie von Dir zitiert gezeigt, und dann als Korollar gesagt, dass es dann auch keinen uniformen geben kann. So wars zumindest in PNL.

Ich würde darauf tippen, dass die uniformen Algorithmen als Spezialfall
von nicht-uniformen betrachtet werden (schließlich sind uniforme Algorithmen
ja auch nicht-uniform). Dann haben nämlich beide Sätze (abgesehen von
synchron/asynchron) die gleiche Aussage, wobei halt der eine (8.9) explizit
sagt, dass er für uniforme und für nicht-uniforme gilt und der andere (8.8)
nur implizit.

Valk hat das meines Wissens auch in der Vorlesung gesagt.
Es heißt eben nicht "uniforme gibt es", sondern "es gibt nichtmal nicht uniforme" (mal ganz platt und ungenau ausgedrückt). Wenn du es so liest sieht es gleich viel netter aus.

Alles klar, danke für die Antworten!

Es heißt eben nicht "uniforme gibt es", sondern "es gibt nichtmal nicht uniforme" (mal ganz platt und ungenau ausgedrückt). Wenn du es so liest sieht es gleich viel netter aus.

Ich dachte, wenn ich es so lesen sollte, hätte er es genau so geschrieben wie Satz 8.9.
Außerdem lassen sich Satz 8.8 und 8.9 dann ja vereinfachen zu "Es gibt keinen anonymen Auswahlalgorithmus." (was noch ein bisschen ungenau wäre - es gibt ja nur keinen deterministischen anonymen Auswahlalgorithmus).

IIRC wird erst der Satz so wie von Dir zitiert gezeigt […]

Stimmt, das macht vielleicht noch Sinn. Erstmal nur einen Teil aufschreiben, weil wir dafür einen Beweis haben, und den Rest unbewiesen dazu. Dass "egal ob uniform oder nicht-uniform" aber durch zwei verschiedene Formulierungen ausgedrückt wird, finde ich immer noch verwirrend.