2-27-07 -- Jared Saia, assistant professor of computer science at the University of New Mexico School of Engineering, is using mathematics to construct a defense against the spammers, hackers, worm builders, virus constructors and all the other villains of the virtual world. His work is based on a familiar puzzle in the computer science world called the Byzantine Agreement.
A group of Byzantine generals in a range of camps surrounding Constantinople are preparing to attack the city. No general can hope to succeed alone. Almost all must co-operate to be successful. The generals begin to exchange messages, trying to agree on a plan for coordinated attack of the city.
Unfortunately, there is a secret and traitorous faction of the generals that is trying to sabotage the attack. These traitorous generals change the content of messages they are asked to pass along to other generals, send messages proposing different attack plans to different generals, and generally try to prevent a convergence on a single plan. How can the rest of the generals agree on a single plan and win the battle, when the this secret traitorous faction is trying to hard to prevent this?
Computer scientists have spent decades working out answers to variations of this problem first posed in a couple of seminal papers by Lamport, Pease and Shostak. It's a critical question because the virtual world is packed with people bent on disruption of the World Wide Web for fun or profit. So how can people collaborate on projects using the web even if many of the participants are destructive?
A Solution to Defeat the Traitorous Generals
Saia believes web-based projects can survive and function reliably even if up to one third of the people involved in collaboration are working to disrupt it. He's spent years working on algorithms that use powerful mathematical tools such as expander and extractor graphs, and the probabilistic method. Those tools can be used to create large-scale distributed systems that work reliably even when they are under malicious assault.
Saia says the algorithms are complete and tested; now the mathematics must be translated into a workable, commercially viable program. He has just received a National Science Foundation Career award for $400,000 over the next five years. This and past grants he has received from the NSF and Sandia National Labs will allow him to continue his research.
Saia is excited about progress so far. He says the algorithms are robust and are scalable to support systems even if hundreds of millions - a group as large as the entire population of Japan -are participating. But the Saia, the most exciting part is the systems great resistance to attack.
He works with several collaborators including Valerie King at the University of Victoria and Microsoft Research, Vishal Sanalani, a former student at UNM and now at Microsoft Research, and Erik Vee at Yahoo Research.