How can we order transactions “fairly” in a replicated state machine (of which today’s blockchains are a prototypical example)? In the model of prior work [4, 18–20, 31], each of n replicas observes transactions in a different order, and the system aggregates these observed orderings into a single order. We argue that this problem is best viewed directly through the lens of the classic preference aggregation problem of social choice theory (instead of as a distributed computing problem), in which rankings on candidates are aggregated into an election result. Two features make this problem novel and distinct. 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 and with only partial information. Additionally, some faulty replicas might misreport their observations; the influence of faulty replicas on the output should be 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 a transaction \(\tau \) before another transaction \(\tau ^\prime \) , then \(\tau ^\prime \) cannot be in an earlier batch than \(\tau \) . This definition holds vacuously, so we strengthen it to require batches of minimal size, while accounting for faulty replicas. This lens gives a protocol with both strictly stronger fairness and better liveness properties than prior work. We specifically adapt the Ranked Pairs [30] method to this streaming setting. This algorithm can be applied on top of any of the communication protocols (in various network models) of prior work for immediate liveness and fairness improvements. Prior work relies on a fixed choice of \(\gamma \) and a bound on the number of faulty replicas f, but we show that Ranked Pairs satisfies our definition for every \(\frac{1}{2}<\gamma \le 1\) simultaneously and for any f, where fairness guarantees degrade as f increases.