  While the very first consensus protocols for the synchronous model were
designed to match the worst-case lower bound, deciding in exactly t+1 rounds in
all runs, it was soon realized that they could be strictly improved upon by
early stopping protocols. These dominate the first ones, by always deciding in
at most t+1 rounds, but often much faster. A protocol is unbeatable if it can't
be strictly dominated. Unbeatability is often a much more suitable notion of
optimality for distributed protocols than worst-case performance. Using a
knowledge-based analysis, this paper studies unbeatability for both consensus
and k-set consensus. We present unbeatable solutions to non-uniform consensus
and k-set consensus, and uniform consensus in synchronous message-passing
contexts with crash failures.
  The k-set consensus problem is much more technically challenging than
consensus, and its analysis has triggered the development of the topological
approach to distributed computing. Worst-case lower bounds for this problem
have required either techniques based on algebraic topology, or reduction-based
proofs. Our proof of unbeatability is purely combinatorial, and is a direct,
albeit nontrivial, generalization of the one for consensus. We also present an
alternative topological unbeatability proof that allows to understand the
connection between the connectivity of protocol complexes and the decision time
of processes.
  For the synchronous model, only solutions to the uniform variant of k-set
consensus have been offered. Based on our unbeatable protocols for uniform
consensus and for non-uniform k-set consensus, we present a uniform k-set
consensus protocol that strictly dominates all known solutions to this problem
in the synchronous model.
