Speaker: Dr. Jialin Zhang, University of Southern California
Inviter: Dr. Sun Xiaoming, Center for Advanced Computing Research, ICT
Time: 15:00pm—16:00pm, May 10th, 2012 (Thursday)
Place: Room 446, Institute of Computing Technology, Chinese Academy of Sciences

Abstract:
In traditional research of distributed problems, two types of failures are commonly considered: crash failure (agent stops executing the protocol) and malicious Byzantine failure (agent may do anything). Few works study the selfish agents in the system. This issue is more evident in systems spanning multiple administrative domains, such as peer-to-peer systems, mobile computing systems, and federated cloud computing systems, where each computing entity has selfish incentives. In this talk, we study distributed consensus problem in synchronous systems subject to both crash failures and strategic manipulations by rational agents in the system. We use ex-post Nash equilibrium to model protocols that are resilient to both crash failures and strategic manipulations of rational agents, and we consider collusions among rational agents. For a system with n distributed agents, we design a deterministic protocol that tolerates 2 colluding agents and a randomized protocol that tolerates n-1 colluding agents, and both tolerate any number of crash failures. We also show that if colluders have private channels of communication, there is no protocol that can tolerate even 2 colluding agents and 1 crash failure. These results are the first step of our effort to study richer and more real models in the distributed system.

Bio:
Jialin Zhang is a PostDoc in computer science department of University of Southern California, United States. Before that, she got her PhD in applied mathematics in Tsinghua University in 2010. Her interest of research includes fault tolerance in distributed computing, social and information networks, algorithmic game theory, smoothed analysis of algorithms and heuristics and combinatorial optimization.