  In distributed systems, a group of $\textit{learners}$ achieve
$\textit{consensus}$ when, by observing the output of some
$\textit{acceptors}$, they all arrive at the same value. Consensus is crucial
for ordering transactions in failure-tolerant systems. Traditional consensus
algorithms are homogeneous in three ways:
  - all learners are treated equally,
  - all acceptors are treated equally, and
  - all failures are treated equally.
  These assumptions, however, are unsuitable for cross-domain applications,
including blockchains, where not all acceptors are equally trustworthy, and not
all learners have the same assumptions and priorities. We present the first
consensus algorithm to be heterogeneous in all three respects. Learners set
their own mixed failure tolerances over differently trusted sets of acceptors.
We express these assumptions in a novel $\textit{Learner Graph}$, and
demonstrate sufficient conditions for consensus. We present
$\textit{Heterogeneous Paxos}$: an extension of Byzantine Paxos. Heterogeneous
Paxos achieves consensus for any viable Learner Graph in best-case three
message sends, which is optimal. We present a proof-of-concept implementation,
and demonstrate how tailoring for heterogeneous scenarios can save resources
and latency.
