Recent News
UNM receives $1.5 million to support computational workforce development
May 8, 2023
Tapia elected to Computing Research Association Board of Directors
March 3, 2023
UNM computer science students take part in HPC competition
March 3, 2023
Computer science professor, student part of AI panel on March 8
February 24, 2023
News Archives
[Colloquium] Truth, Lies And Random Bits
January 13, 2015
Watch Colloquim:
- 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.