  We develop deterministic algorithms for the problems of consensus, gossiping
and checkpointing with nodes prone to failing. Distributed systems are modeled
as synchronous complete networks. Failures are represented either as crashes or
authenticated Byzantine faults. The algorithmic goal is to have both linear
running time and linear amount of communication for as large an upper bound $t$
on the number of faults as possible, with respect to the number of nodes~$n$.
For crash failures, these bounds of optimality are $t=\mathcal{O}(\frac{n}{\log
n})$ for consensus and $t=\mathcal{O}(\frac{n}{\log^2 n})$ for gossiping and
checkpointing, while the running time for each algorithm is $\Theta(t+\log n)$.
For the authenticated Byzantine model of failures, we show how to accomplish
both linear running time and communication for $t=\mathcal{O}(\sqrt{n})$. We
show how to implement the algorithms in the single-port model, in which a node
may choose only one other node to send/receive a message to/from in a round,
such as to preserve the range of running time and communication optimality. We
prove lower bounds to show the optimality of some performance bounds.
