Scientific Reports:

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

English abstract:
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.

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.