Peter Robinson
I'm interested in designing new distributed and parallel algorithms, the distributed processing of big data, achieving faulttolerance in networks, and secure distributed computing in dynamic environments such as peertopeer networks and mobile adhoc networks.
News
 General Chair of ACM PODC 2019
 Program committee member of BGP 2017, SPAA 2016 and of SIROCCO 2016
 Giving a talk at a workshop on Dynamic Graphs in Distributed Computing (colocated with DISC 2016)
 Cochairing the program committee of ICDCN 2016
 Giving a talk at ADGA 2015, (4th Workshop on Advances in Distributed Graph Algorithms, colocated with DISC 2015 )
Keywords (Show all)
«Asynchrony» «Big Data» «Byzantine Failures» «Churn» «Communication Complexity» «Distributed Agreement» «Distributed Storage» «Dynamic Network» «FaultTolerance» «Gossip Communication» «Graph Algorithm» «Haskell» «Leader Election» «Machine Learning» «Mobile AdHoc Network» «Natural Language Processing» «P2P» «Secure Computation» «SelfHealing» «Symmetry Breaking»Publications tagged with "Leader Election" (Show all)
2015

On the Complexity of Universal Leader Election
PDF
DOI
Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, Amitabh Trehan. Journal of the ACM, vol. 62(1), 7:17:27 (JACM).
Abstract...Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most ''obvious'' complexity bounds have not been proven for randomized algorithms. The ``obvious'' lower bounds of $\Omega(m)$ messages ($m$ is the number of edges in the network) and $\Omega(D)$ time ($D$ is the network diameter) are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even $\Omega(n)$ ($n$ is the number of nodes in the network) is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms (except for the limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that $D$ and $n$ were not known). We establish these fundamental lower bounds in this paper for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (such algorithms should work for all graphs), apply to every $D$, $m$, and $n$, and hold even if $D$, $m$, and $n$ are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an $O(m)$ messages algorithm. An $O(D)$ time algorithm is known. An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. (The answer is known to be negative in the deterministic setting). We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.
2014

Optimal Bounds for Randomized Leader Election
PDF
DOI
Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, Amitabh Trehan. Special Issue of Theoretical Computer Science, Elsevier. (TCS).
Abstract...This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete $n$node networks that runs in $O(1)$ rounds and (with high probability) uses only $O(\sqrt{n}\log^{3/2} n)$ messages to elect a unique leader (with high probability). When considering the ''explicit'' variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of $O(1)$ rounds and $O(n)$ messages. This algorithm is then extended to one solving leader election on any connected nonbipartite $n$node graph $G$ in $O(\tau(G))$ time and $O(\tau(G)\sqrt{n}\log^{3/2} n)$ messages, where $\tau(G)$ is the mixing time of a random walk on $G$. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, superlinear message lower bounds are known for timeefficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that $\Omega(\sqrt{n})$ messages are needed for any leader election algorithm that succeeds with probability at least $1/e + \epsilon$, for any small constant $\epsilon > 0$. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.
2013

Sublinear Bounds for Randomized Leader Election
PDF
DOI
Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, Amitabh Trehan. 14th International Conference on Distributed Computing and Networking (ICDCN 2013).Best Paper Award.
Abstract...This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete nnode networks that runs in $O(1)$ rounds and (with high probability) takes only $O(\sqrt{n}\log^{3/2}n)$ messages to elect a unique leader (with high probability). This algorithm is then extended to solve leader election on any connected nonbipartite nnode graph $G$ in $O(\tau(G))$ time and $O(\tau(G)\sqrt{n}\log^{3/2}n)$ messages, where $\tau(G)$ is the mixing time of a random walk on $G$. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, superlinear message lower bounds are known for timeefficient deterministic leader election algorithms. Finally, an almosttight lower bound is presented for randomized leader election, showing that $\Omega(\sqrt{n})$ messages are needed for any $O(1)$ time leader election algorithm which succeeds with high probability. It is also shown that $\Omega(n^{1/3})$ messages are needed by any leader election algorithm that succeeds with high probability, regardless of the number of the rounds. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks. 
On the Complexity of Universal Leader Election
PDF
DOI
Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, Amitabh Trehan. 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013).
Abstract...Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most ''obvious'' complexity bounds have not been proven for randomized algorithms. The ``obvious'' lower bounds of $\Omega(m)$ messages ($m$ is the number of edges in the network) and $\Omega(D)$ time ($D$ is the network diameter) are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even $\Omega(n)$ ($n$ is the number of nodes in the network) is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms (except for the limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that $D$ and $n$ were not known). We establish these fundamental lower bounds in this paper for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (such algorithms should work for all graphs), apply to every $D$, $m$, and $n$, and hold even if $D$, $m$, and $n$ are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an $O(m)$ messages algorithm. An $O(D)$ time algorithm is known. An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. (The answer is known to be negative in the deterministic setting). We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks. 
Robust Leader Election in a FastChanging World
John Augustine, Tejas Kulkarni, Paresh Nakhe, Peter Robinson. 9th International Workshop on Foundations of Mobile Computing (FOMC 2013).
Abstract...We consider the problem of electing a leader among nodes in a highly dynamic network where the adversary has unbounded capacity to insert and remove nodes (including the leader) from the network and change connectivity at will. We present a randomized algorithm that (re)elects a leader in $O(D\log n)$ rounds with high probability, where $D$ is a bound on the dynamic diameter of the network and $n$ is the maximum number of nodes in the network at any point in time. We assume a model of broadcastbased communication where a node can send only $1$ message of $O(\log n)$ bits per round and is not aware of the receivers in advance. Thus our results also apply to mobile wireless adhoc networks, improving over the optimal (for deterministic algorithms) $O(Dn)$ solution presented at FOMC 2011. We show that our algorithm is optimal by proving that any randomized algorithm takes at least $\Omega(D\log n)$ rounds to elect a leader with high probability, which shows that our algorithm yields the best possible (up to constants) termination time.
2011

Optimal Regional Consecutive Leader Election in Mobile AdHoc Networks
PDF
DOI
Hyun Chul Chung, Peter Robinson, Jennifer L. Welch. 7th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (part of FCRC 2011).
Abstract...The regional consecutive leader election (RCLE) problem requires mobile nodes to elect a leader within bounded time upon entering a specific region. We prove that any algorithm requires $\Omega(Dn)$ rounds for leader election, where D is the diameter of the network and $n$ is the total number of nodes. We then present a faulttolerant distributed algorithm that solves the RCLE problem and works even in settings where nodes do not have access to synchronized clocks. Since nodes set their leader variable within $O(Dn)$ rounds, our algorithm is asymptotically optimal with respect to time complexity. Due to its low message bit complexity, we believe that our algorithm is of practical interest for mobile wireless adhoc networks. Finally, we present a novel and intuitive constraint on mobility that guarantees a bounded communication diameter among nodes within the region of interest.
2010

Regional Consecutive Leader Election in Mobile AdHoc Networks
Hyun Chul Chung, Peter Robinson, Jennifer L. Welch. 6th ACM SIGACT/SIGMOBILE Workshop on Foundations of Mobile Computing (DIALMPOMC 2010).
Code
I'm interested in parallel and distributed programming and related technologies such as software transactional memory. Below is a (noncomprehensive) list of software that I have written.
 I extended Haskell's Cabal, for using a "world" file to keep track of installed packages. (Now part of the main distribution.)
 data dispersal: an implementation of an (m,n)threshold information dispersal scheme that is spaceoptimal.
 secret sharing: an implementation of a secret sharing scheme that provides informationtheoretic security.
 diceentropy: a library that provides cryptographically secure dice rolls implemented by bitefficient rejection sampling.
 TSkipList: a data structure with rangequery support for software transactional memory.
 stmiohooks: An extension of Haskell's Software Transactional Memory (STM) monad with commit and retry IO hooks.
 Mathgenealogy: Visualize your (academic) genealogy! A program for extracting data from the Mathematics Genealogy project.
 In my master thesis I developed a system for automatically constructing events out of log files produced by various system programs. One of the core components of my work was a partofspeech (POS) tagger, which assigns word classes (e.g. noun, verb) to the previously parsed tokens of the log file. To cope with noisy input data, I modeled the POS tagger as a hidden Markov model. I developed (and proved the correctness of) a variant of the maximum likelihood estimation algorithm for training the Markov model and smoothing the state transition distributions.