[Zurück]


Wissenschaftliche Berichte:

U. Schmid, B. Weiss:
"Synchronous Byzantine Agreement under Hybrid Process and Link Failures";
Bericht für Research Report 1/2004, Technische Universität Wien, Institut für Technische Informatik, Treitlstraße 3, A-1040 Vienna, Austria; 2004.



Kurzfassung englisch:
We introduce a novel hybrid failure model for synchronous distributed systems, which extends existing hybrid node/process failure models by adding communication failures. Every process in the system is allowed to commit up to $ls$ send link failures and experience up to $lr$ receive link failures per round here, without being considered faulty, where up to {abstract}leqlsaleqls$ and {abstract}leqlraleqlr$ links may even generate erroneous messages rather than just omissions. We show that all known ``oral messages" (non-authenticated) and ``written messages" (authenticated) Byzantine agreement algorithms can easily be adopted to work under this failure model, provided that the number of processes in the system is increased by small integer multiples of $ls$, $lr$, $lsa$, $lra$. This is a surprising result, given that consensus in presence of unrestricted link failures and mobile failures is well-known to be impossible. Our detailed analysis also includes uniform variants of Byzantine agreement algorithms, which guarantee validity and agreement even for benign faulty processes, and explores the power and limitations of authentication in presence of link failures.


Elektronische Version der Publikation:
http://www.vmars.tuwien.ac.at/php/pserver/docdetail.php?DID=1319&viewmode=paper&year=2004


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.