The Taub Faculty of Computer Science Events and Talks

In this talk, I will discuss results from our recent work of last year (i.e. 2013!) on the classic problem of Leader Election. It is perhaps surprising that this classic problem still yields such rich results. We look at Leader Election in the synchronous message passing setting. Most of this work deals with randomization and we have discovered definitive lower bounds and efficient algorithms.

Majority of this talk will focus on [1], in which we introduce the first sublinear messages randomized Leader Election (w.h.p.) that runs in O(1) time on complete networks and mixing time on any connected graph. We also show a lower bound of sqrt(n) for any leader election algorithm that succeeds with probability at least $1/e + \eps$, for any small constant $\eps > 0$. We will also, time permitting, briefly touch upon the slew of results we obtained in [2] for Universal Leader Election (algorithms that work for all graphs) which includes formal proofs of fundamental lower bounds for time and messages in randomized algorithms and randomized and deterministic algorithms that try to simultaneously achieve both.

[1] Sublinear Bounds for Randomized Leader Election. ICDCN 2013, Best Paper Award
[2] On the complexity of universal leader election. PODC 2013

Joint works with Shay Kutten, Gopal Pandurangan, David Peleg, and Peter Robinson

Bio:
Amitabh Trehan is a Lecturer (Assistant Professor) in Computer Science at Queen's University Belfast (High Performance and Distributed Computing cluster). Before joining QUB, he held an I-CORE postdoc fellowship with Danny Dolev at Hebrew University. Recently, he was also awarded the prestigious Newton Incoming Fellowship of the Royal Society, UK, which he had to decline in favour of his present position.

He has also held a postdoc with Shay Kutten and Ron Lavi at the information systems group at the faculty of Industrial Engineering at Technion and a postdoc with Valerie King (at UVIC, Canada). His Ph.D. Advisor was Jared Saia (University of New Mexico, USA) with whom he worked on algorithms for self-healing networks.

His broad research interests are in theory and algorithms with specific interests in distributed algorithms, networks, and game theory. His interest includes designing efficient distributed algorithms for robustness/self-healing/ self-* properties in systems under adversarial attack, classic distributed problems such as Leader Election, and studying game theoretic and other mechanisms for evolving networks, such as social networks or distributed systems (P2P networks etc).