News Archives

[Colloquium] Truth, Lies And Random Bits

January 13, 2015

Watch Colloquim: 

MOV FILE

  • Date: Tuesday 1/13/15
  • Time:
  • Place: Mechanical Engineering, Room 218

Title: Truth, Lies and Random Bits
Speaker: Jared Saia, Professor
UNM Department of Computer Science


Abstract:

Random bits are used in computer science 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 distributed setting where some agents may not be trustworthy. What happens if a hidden cabal is generating bits that are not random? 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 Byzantine agreement, 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. We describe a new spectral 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 examining the top eigenvector of a certain matrix. This suggests a new paradigm for reliable distributed computing: the design of algorithms that force an attacker into behavior that is statistically deviant and computationally detectable.