Room 333 Wisenbaker Engr. Building (fishbowl)
Dr. Nitin Vaidya/University of Illinois at Urbana-Champaign
Abstract: Consider a network of agents 1 to N, where in each agent i has a local convex cost function Fi(x). For instance, the agents may be robots and each robot’s local cost function may represent its cost of moving to location x for a rendezvous with other robots. The objective here is to identify argument x that minimizes the total cost over all the agents. Similar problems arise in the context of machine learning as well where the goal is to determine the optima of a sum of many cost functions. This is a special case of convex optimization that has received significant attention over the past three decades. In particular, many distributed algorithms have been developed to determine the optima without requiring any single agent to be aware of all the cost functions.
Our work addresses a fault-tolerant version of the problem, allowing for some of the agents to crash during the computation, or suffer from Byzantine failures (which can result in malicious behavior). For brevity, this talk will focus on the case when up to f agents may suffer Byzantine failures. The ideal goal then is to determine the optima of the sum of local cost functions of just the fault-free agents. It is easy to show that this problem is not solvable unless the local cost functions exhibit some form of redundancy. The talk will consider the irredundant case, and show that despite the failure of f agents, it is possible to determine the optima of a global cost function obtained as the weighted average of the cost functions of just the fault-free agents, wherein all-but-f fault-free agents are assigned non-trivial weights.
The talk will provide the intuition behind our results, and discuss several algorithms, including a centralized solution as well as distributed algorithms. We will also discuss some related open problems.
Joint work with Lili Su, a Ph.D. candidate at the University of Illinois at Urbana-Champaign.
Bio: Nitin Vaidya received the Ph.D. from the University of Massachusetts at Amherst. He is a Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. He has held visiting positions at Technicolor Paris Lab, TU-Berlin, IIT-Bombay, Microsoft Research, and Sun Microsystems, as well as a faculty position at the Texas A&M University. Nitin Vaidya has co-authored papers that received awards at several conferences, including 2015 SSS, 2007 ACM MobiHoc and 1998 ACM MobiCom. He is a fellow of the IEEE. He presently serves the Chair of the Steering Committee for the ACM PODC conference, and has previously served as Editor-in-Chief for the IEEE Transactions on Mobile Computing, and Editor-in-Chief for ACM SIGMOBILE publication MC2R. More information at visit http://disc.ece.illinois.edu/.