Ich habe ein Verständnisproblem mit der Definition der Funktion resolve(pi) auf Seite 350 des FGI-2 Skripts.

Falls pi kein Blatt ist und existiert, dann ist resolve(pi) = majority {resolve(pi') | pi' ist Sohn von pi}

Es wird also die Menge der Entscheidungen der Söhne gebildet. Das kann {0} oder {1} oder {0, 1} sein. Was bedeutet es jetzt, vor diese Menge "majority" zu schreiben? Eine Funktion ist majority nicht, sonst würden da runde Klammern stehen.

Und selbst wenn es eine Funktion wäre: wie soll man aus einer der drei oben genannten Mengen einen Mehrheitsentscheid treffen???

Ich denke mal, du kannst dir die Klammer dazu denken :)

für {0} wäre der Mehrheitsentscheid dann 0
und für {0,1} "undefiniert"

was mich bei diesen Algorithmus noch wundert, ist folgendes:

in der zweiten Runden soll ja jeder Prozessor seine ganze 1.Ebene an alle Prozessoren versenden. Dann würde z.B Prozessor 0 (S.351) den Knoten "0" auch an alle Prozessoren versenden. Also müssten die anderen Prozessoren in ihren Baum "0 sagt, das 0 den Wert X hat" intragen, aber solche Knoten gibt es ja gerade nicht.
(ich hoffe, ich habe mich verstänldich ausgedrückt)

Eine Funktion ist majority nicht, sonst würden da runde Klammern stehen.

Es gibt Autoren (z.B. Reynolds, siehe LOS) die schreiben anstelle von
f(x) bei einer Funktion f nur knapp fx.
Vielleicht ist es hier auch so?

Die Definition geht auf den Aufsatz "Shifting  Gears: Changing Algorithms  on the Fly To Expedite Byzantine Agreement" zurück. Dort gibt es nur eine nartürlich sprachliche Definition:

"resolve(x)=[…]
the majority value obtained by applying  resolve to
the children of x, if a majority exists;[…]"

demnach kann man sich "majority" als Funktion mit entsprechender Bedeutung denken. Die Klammern wurden wohl vergessen, oder wie oben angedeutet, wegen Vorlieben des Authors absichtlich weggelassen (ist es nicht auch üblich, dass man z.B "max{…}" anstelle von "max({…})" schreibt)

greetings chris

OK, aber der Hauptkritikgrund bleibt: aus einer Menge kann man keinen Mehrheitsentscheid bestimmen. Wenn 1200 Leute CDU wählen und 800 Leute SPD, und ich bilde die Menge der abgegebenen Stimmen, dann lautet sie: {CDU, SPD}. In einer Menge kommt eben kein Element mehr als einmal vor.

Hatte Herrn Valk auch schon darauf angesprochen, und er stimmte mir zu, dass das formal so einfach falsch ist, man müsste Multimengen statt Mengen benutzen.