Jarad Saia. Courtesy photo
SFI News:
The Santa Fe Institute will present a seminar titled “Truth, Lies and Randomness” by presenter Jarad Saia from the University of New Mexico at 12:15 p.m. Friday, July 26 in the Collins Conference Room at SFI.
SFI is at 1399 Hyde Park Road in Santa Fe. The talk is free and open to the public
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, Saia will 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, he will describe a new, faster algorithm that requires expected polynomial time. His 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.
