CS Colloquium - Trade-offs between Time and Communication for Distributed Leader Election


Peter Robinson


We consider the leader election problem in a clique network, where n nodes are connected by bidirectional point-to-point communication links. For the synchronous clique under simultaneous wake-up, i.e., where all nodes start executing the algorithm at the same time in lock-step rounds, we show new tradeoffs between the number of required messages and the amount of time. For the synchronous clique under adversarial wake-up, we show that a message complexity of Θ(n^{3/2}) is a tight lower bound for 2-round algorithms, even randomized ones. Finally, we turn our attention to the asynchronous clique: Assuming adversarial wake-up, we give a randomized algorithm that achieves a message complexity of O(n^{1+1/k}) and a time complexity of k+8, for a given parameter k.


Peter Robinson is an Associate Professor in the AU School of Computer & Cyber Sciences. His research focuses on designing new distributed and parallel algorithms, the distributed processing of big data, achieving fault-tolerance in communication networks against adversarial attacks, and developing robust protocols that work in highly dynamic environments such as peer-to-peer Blockchain networks and mobile ad-hoc networks.

His research has been supported by the General Research Fund (Hong Kong), the Natural Sciences and Engineering Research Council (Canada), IBM Research, and the London Mathematical Society (UK).

Friday, September 22, 2023 3:30pm to 4:30pm
MacLean Hall
2 West Washington Street, Iowa City, IA 52240
View on Event Calendar
Individuals with disabilities are encouraged to attend all University of Iowa–sponsored events. If you are a person with a disability who requires a reasonable accommodation in order to participate in this program, please contact Computer Science Dept. in advance at 319-335-0713 or matthieu-biger@uiowa.edu.