Was ist das Problem der byzantinischen Generäle?

Das Problem der byzantinischen Generäle ist ein Gedankenexperiment, das sich mit einer Schlüsselfrage der Informatik beschäftigt: Ist es möglich, in einem Computernetzwerk, das aus unabhängigen, geografisch verteilten Knoten besteht, einen Konsens zu bilden?

Das Problem wurde 1982 von Forschern des SRI International Research Institute vorgeschlagen.

Es geht wie folgt: Es gibt eine Reihe byzantinischer Generäle, die eine Stadt belagern. Sie können nur kommunizieren, indem sie sich gegenseitig Boten schicken. Die Generäle müssen sich auf einen gemeinsamen Aktionsplan einigen: ob sie die Stadt angreifen oder sich zurückziehen sollen. Allerdings sind einige der Generäle verräterisch und arbeiten aktiv gegen die Konsensbildung; Ihre Anzahl und Identität ist unbekannt.

Die Frage, die das Problem aufwirft, ist, welchen Entscheidungsalgorithmus die Generäle verwenden sollten, um einen gemeinsamen Plan auszuarbeiten – unabhängig von der Einmischung der Verräter – und ob ein solcher Algorithmus überhaupt existiert.

Nach eigener Analyse der Forscher ist ein solches System zwar machbar, allerdings muss die Zahl der loyalen Generäle unbedingt mehr als zwei Drittel betragen. In einer Situation mit drei Generälen, von denen einer ein Verräter ist, können die Loyalen beispielsweise niemals garantieren, dass sie einen Konsens erzielen können.

Dieses Problem ist für Kryptowährungen von großer Bedeutung, da es sich im Wesentlichen um verteilte Computersysteme handelt: Sie bestehen aus Transaktionsverarbeitungsknoten, die voneinander und von zentralen Autoritäten unabhängig sind und nur aus der Ferne kommunizieren können. Sie sind die „Generäle“, die einen Konsens darüber erzielen müssen, welche Transaktionen wann stattgefunden haben.

Knoten können freiwillig oder versehentlich fehlerhafte Daten über Transaktionen liefern, und ihre Informationen müssen aussortiert werden. Bitcoin (BTC) und andere Kryptowährungen lösen dieses Problem durch technische Lösungen wie die Proof-of-Work- und Proof-of-Stake-Algorithmen.

Siehe Byzantinische Fehlertoleranz (BFT).