Fair Ordering via Streaming Social Choice Theory

We study the question of "fairly" ordering transactions in a replicated state machine. Each replica receives transactions over a network from clients in a possibly different order, and the system aggregates these orderings into a single, total order. This problem is akin to the classic problem of social choice theory, where rankings on candidates are aggregated into an election result. Three features make this problem novel and distinct. First, the number of transactions is unbounded, so an ordering must be defined over a countably infinite set. Second, decisions must be made quickly and with only partial information. Finally, some faulty replicas might alter reported observations; their influence should be bounded. We study the Ranked Pairs algorithm. Analysis of how missing information propagates through the algorithm enables our streaming version to know when it can output a transaction. Manipulation of a tiebreaking rule gives a protocol that (in a synchronous network) always outputs a transaction after a bounded time. Prior work proposes a "$\gamma$-batch-order-fairness" property on an output ordering, which divides the output into contiguous batches. If a $\gamma$ fraction of replicas receive a transaction $tx$ before another transaction $tx^\prime$, then $tx^\prime$ cannot be in an earlier batch than $tx$. We strengthen this definition to require that batches have minimal size, which must be handled carefully in the presence of faulty replicas. This gives the first notion of order-fairness that cannot be vacuously satisfied by arbitrarily large batches and that is satisfiable in the presence of faulty replicas. Prior work relies on a fixed choice of $\gamma$ and bound on the number of faulty replicas $f$, but we show that Ranked Pairs satisfies our definition for every $\gamma$ simultaneously and for any $f$, where fairness guarantees linearly degrade as $f$ increases.