This thesis is concerned with authenticated consensus and has been
developed in the context of project W2F, which aims towards integrating
wireless and wireline communication in a distributed fault-tolerant and
secure fieldbus with ad-hoc (i.e., flexible, decentralized and unknown)
network topology and mobile nodes.
Consensus is a well-known problem in distributed systems and is used
to find a common decision among a group of nodes. This is a fundamental
building block of redundant systems and thus a vital part of W2F.
Authentication is used to determine the identity of the sender of a
message, even if the message has been passed along by other nodes.
Attackers are thus deprived of the capability to mask their activities
under cover of different identities, which in general simplifies
achieving consensus and is an important asset in an ad-hoc
network like W2F.


The first part of this thesis is dedicated to authentication with
digital signatures and its special needs in W2F. In order to avoid or
at least diminish denial-of-service attacks and to minimize the cost
to the attacked node, we use message authentication codes and employ
substantial hardware support in the form of message filters. Our
algorithms also integrate the client puzzle technique to make the
attacker spend its time and resources before the attacked node does.

The second part addresses consensus in W2F. We will present the
failure model used in the W2F network and give some lower bounds on the
number of nodes required to mask link failures. We will then analyze
several Byzantine agreement algorithms which can be used to achieve
consensus. Apart from the well-known OMH algorithm (Lincoln and Rushby, 1993)
we will also examine two authenticated variants OMHA and ZA
(Gong, Lincoln and Rushby, 1995). As it turns out, it is indeed possible
to achieve consensus in systems with dominant link failures, despite the
well-known impossibility result of Jim Gray from 1978.