  Algorithms to solve fault-tolerant consensus in asynchronous systems often
rely on primitives such as crusader agreement, adopt-commit, and graded
broadcast, which provide weaker agreement properties than consensus. Although
these primitives have a similar flavor, they have been defined and implemented
separately in ad hoc ways. We propose a new problem called connected consensus
that has as special cases crusader agreement, adopt-commit, and graded
broadcast, and generalizes them to handle multi-valued inputs. The
generalization is accomplished by relating the problem to approximate agreement
on graphs.
  We present three algorithms for multi-valued connected consensus in
asynchronous message-passing systems, one tolerating crash failures and two
tolerating malicious (unauthenticated Byzantine) failures. We extend the
definition of binding, a desirable property recently identified as supporting
binary consensus algorithms that are correct against adaptive adversaries, to
the multi-valued input case and show that all our algorithms satisfy the
property. Our crash-resilient algorithm has failure-resilience and time
complexity that we show are optimal. When restricted to the case of binary
inputs, the algorithm has improved time complexity over prior algorithms. Our
two algorithms for malicious failures trade off failure resilience and time
complexity. The first algorithm has time complexity that we prove is optimal
but worse failure-resilience, while the second has failure-resilience that we
prove is optimal but worse time complexity. When restricted to the case of
binary inputs, the time complexity (as well as resilience) of the second
algorithm matches that of prior algorithms.
