  Prior work studies the question of ``fairly'' ordering transactions in a
replicated state machine. Each of $n$ replicas receives transactions in a
possibly different order, and the system must aggregate the observed orderings
into a single order. We argue that this problem is best viewed through the lens
of social choice theory, in which (in the preference aggregation problem)
rankings on candidates are aggregated into an election result.
  Two features make this problem novel. First, the number of transactions is
unbounded, and an ordering must be defined over a countably infinite set. And
second, decisions must be made quickly, with only partial information.
Additionally, some faulty replicas might alter their reported observations;
their influence on the output should be bounded and well understood.
  Prior work studies a ``$\gamma$-batch-order-fairness'' property, which
divides an ordering into contiguous batches. If a $\gamma$ fraction of replicas
receive $\tau$ before $\tau^\prime$, then $\tau^\prime$ cannot be in an earlier
batch than $\tau$. We strengthen this definition to require that batches have
minimal size ($\gamma$-batch-order-fairness can be vacuously satisfied by large
batches) while accounting for the possibility of faulty replicas.
  This social choice lens enables an ordering protocol with strictly stronger
fairness and liveness properties than prior work. We study the Ranked Pairs
method. Analysis of how missing information moves through the algorithm allows
our streaming version to know when it can output a transaction. Deliberate
construction of a tiebreaking rule ensures our algorithm outputs a transaction
after a bounded time (in a synchronous network). Prior work relies on a fixed
choice of $\gamma$ and bound on the number of faulty replicas $f$, but our
algorithm satisfies our definition for every $\frac{1}{2}<\gamma\leq 1$
simultaneously and for any $f$.
