Speaker

Peter Robinson

Abstract

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.

Bio

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).