How can a group of agents achieve a goal despite efforts by some of the agents to prevent this? This important question cuts across many disciplines including political science, economics, mathematics and computer science. In this proposal, we are exploring this question by focusing on the following problem. A set of n agents wants to compute the value of a function, f, of n inputs, where each agent holds a unique input of f. Our goal is to create a distributed algorithm that ensures that each agent learns the output of f. Our algorithm will be attack-resistant in that it works correctly even when up to a constant fraction of the agents are controlled by an omniscient adversary that tries to prevent the function from being computed. Our algorithm will also be scalable in the sense that each node in the network sends and receives a number of messages and bits that is only polylogarithmic in n i.e. O(logc n) where c is a fixed constant. We are making use of several tools to solve this problem including: the use of expander-like graphs to enable robust communication; the use of small randomly chosen committees as single trustworthy functional units; and algorithmic techniques to harden against denial of service attacks. Solving this problem will likely have broader impact in such diverse areas as voting, spam detection, worm and malware detection, distributed file systems, auction and mechanism enforcement, collaborative filtering, and web search.
Intellectual Merit: This project had outcomes in two major areas related to intellectial merit. The first main area was designing efficient algorithms for the problem of Byzantine agreement. Intuitively, the Byzantine agreement problem asks if a group of processors can come to agreement on a single bit, despite the efforts of a hidden fraction of processors to subvert this goal. Byzantine agreement is one of the most fundamental problems in computer science and has applications in areas as diverse as airplane flight systems, data base systems, computer auctions, peer-to-peer systems and cloud computing. We have two major results on Byzantine agreement. Our first result resolves a problem that has been open since 1983: does there exist an polynomial time algorithm for Byzantine agreement in the hard model? Intuitively, polynomial time means efficient in terms of the amount of time the algorithm requires to terminate. In the hard model, the adversary is adaptive: it can take over processors at any point during the protocol, up to the point of taking over a certain threshold. Communication is asynchronous: the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm. Finally, the adversary has full information: it knows the states of all processors at any time, and is assumed to be computationally unbounded. Our paper on this result was published in the prestigious conferences Foundations of Computer Science (FOCS) and Symposium on Discrete Algorithms (SODA). Our second major result in Byzantine agreement is an algorithm that is efficient in terms of badwidth i.e. the total number of messages that must be communicated among the processors. Previous algorithms for Byzantine agreement required each processor to send at least n messages , where n is the number of processors. Our algorithm reduces this amount to roughly square root of n. The second major area of results was for the problem of secure multiparty computation. The secure multiparty computation (MPC) problem is a generalization of the Byzantine agreement problem. In MPC, there are n processors, each with a private input that want to compute a function f over all of their inputs, without revealing any more information about the private inputs than what is revealed by the output of f. The problem is complicated by the fact that a hidden fraction of the players are controlled by an adversary that is actively trying to corrupt the output and/or obtain information about the inputs. This problem has application in many areas of computer security. Our result in this area is an algorithm that is scalable in the sense that the number of messages sent by each processor is essentially the square root of n, the number of processors. This contrasts with previous results for this problem where the number of messages sent is linear in n. Our result used mathematical and algorithmic tools that we previously developed in solving the Byzantine agreement problem. Our paper describing this result won a best paper award at the International Conference on Distributed Computing and Networking (ICDCN), 2014. In all, this grant has generater over 20 papers, 1 best paper award and one article in the Journal of the ACM. Broader Impact: This grant supported four PhD students, two of whom have graduated and two of whom are within one year of graduation. PhD student Muyiwa Olumuyiwasa, graduated in the spring of 2011. Muyiwa is a minority student (native Nigerian) and is now working at Intel Corporation. PhD student Navin Rustagi graduated in the summer of 2010 and became a post doc in the Statistics department at Rice University. PhD student George Saad will be graduating in the Spring of 2014 and plans to find a job in industry. Finally, PhD student Jeffrey Knockel will likely graduate in 2015 or 2016. The grant also supported one female MS student, Jenny Chen, who is graduating in the fall of 2014. Research completed under this grant has received coverage in the popular press. It has been featured in the ACM Technical News and UNM Today under the title ``Professor Fights a Mathematical Battle to Keep the Virtual World Running Smoothly'' and was on the front page of the UNM Daily Lobo under the title ``Professor Goes to War''. The research in this grant has been disseminated through invited presentations and talks at both universities and research labs, including an upcoming keynote talk at the SOFSEM conference in January of 2015. PI Saia's research blog "Machinations", which focuses on research on distributed algorithms and network security, had roughly 100 posts and received over 20,000 page views during the course of this grant.
