  We consider deterministic distributed algorithms solving Consensus in
synchronous networks of arbitrary topologies. Links are prone to failures.
Agreement is understood as holding in each connected component of a network
obtained by removing faulty links. We introduce the concept of stretch, which
is a function of the number of connected components of a network and their
respective diameters. Fast and early-stopping algorithms solving Consensus are
defined by referring to stretch resulting in removing faulty links. We develop
algorithms that rely only on nodes knowing their own names and the ability to
associate communication with local ports. A network has $n$ nodes and it starts
with $m$ functional links. We give a general algorithm operating in time $n$
that uses messages of $O(\log n)$ bits. If we additionally restrict executions
to be subject to a bound $\Lambda$ on stretch, then there is a fast algorithm
solving Consensus in time $O(\Lambda)$ using messages of $O(\log n)$ bits. Let
$\lambda$ be an unknown stretch occurring in an execution; we give an algorithm
working in time $(\lambda+2)^3$ and using messages of $O(n\log n)$ bits. We
show that Consensus can be solved in the optimal $O(\lambda)$ time, but at the
cost of increasing message size to $O(m\log n)$. We also demonstrate how to
solve Consensus by an algorithm that uses only $O(n)$ non-faulty links and
works in time $O(n m)$, while nodes start with their ports mapped to neighbors
and messages carry $O(m\log n)$ bits. We prove lower bounds on performance of
Consensus solutions that refer to parameters of evolving network topologies and
the knowledge available to nodes.
