Jarad Saia (University of New Mexico)
Abstract. Random bits are used in algorithms to: break symmetry and deadlock, ensure load-balancing, find a representative sample, maximize utility, and foil an adversary. Unfortunately, true randomness is difficult to guarantee, especially in a decentralized setting where some agents may not be trustworthy. What happens if a hidden cabal is generating bits that are not "random enough"? Can we detect and neutralize such behavior?
In this talk, we address this question in the context of a classic problem in distributed computing: Byzantine agreement. In the Byzantine agreement problem, n agents, each with a private input, must agree on a single common output that is equal to some agent's input. Randomization is provably necessary to solve this problem, but past random algorithms required expected exponential time. In this talk, we describe a new, faster algorithm that requires expected polynomial time. Our algorithm is designed so that in order to thwart it, corrupted agents must engage in statistically deviant behavior that is detectable by other agents. This suggests a new paradigm for reliable distributed computing: the design of algorithms that force an attacker into behavior that is statistically deviant in a way that is computationally detectable.