Grenzen der Sicherheit von Münzwurf, wenn die Hälfte der Prozessoren fehlerhaft ist

Es werden Protokolle vorgeschlagen, die es einem asynchronen Netzwerk von Prozessoren ermöglichen, sich auf ein zufälliges (unvoreingenommenes) Bit zu einigen, wie in 1 und 4 beschrieben. Es wird behauptet, dass (vorausgesetzt, es existiert eine Hintertürenfunktion) die korrekten Prozessoren, wenn weniger als die Hälfte der Prozessoren fehlerhaft sind, dennoch auf ein Bit einigen, dessen Verzerrung vernachlässigbar klein ist (wenn die Laufzeit der Prozessoren poly(n) beträgt, ist die Verzerrung kleiner als O(~r) für alle k). Wenn die Hälfte der Prozessoren fehlerhaft ist, sind diese Protokolle nicht mehr wirksam: Die von den korrekten Prozessoren ausgegebenen Bits können stark verzerrt sein. Wir beweisen, dass die obigen Protokolle optimal sind, da kein Protokoll existiert, das Fehler in mindestens der Hälfte der Prozessoren toleriert. Das Ergebnis ist sehr allgemein, da nur wenige Einschränkungen hinsichtlich der Arten von Kommunikation zwischen korrekten Prozessoren (wie private Kanäle und globale Kanäle) gemacht werden und die korrekten Prozessoren sich nur in einem schwach probabilistischen Sinne auf ein Bit einigen müssen. Auch benötigen die fehlerhaften Prozessoren nicht viel Leistung. Sie können privat miteinander kommunizieren, aber sie können keine Nachrichten lesen, die privat zwischen zwei korrekten Prozessoren ausgetauscht werden. Ein interessantes Beispiel für das Problem entsteht, wenn die Anzahl der Prozessoren auf zwei festgelegt ist und einer von ihnen