## Peter Robinson

I'm an Assistant Professor in the Computer Science Department of the City University of Hong Kong. My 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.

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

## News

- New papers at SODA 2021 and PODC 2021
- General Chair of ACM PODC 2019
- On program committee of DISC 2021, ICDCS 2021, SIROCCO 2021, PODC 2020

## Tags (Show all)

Asynchrony Big Data Byzantine Failures Churn Communication Complexity Distributed Agreement Distributed Storage Dynamic Network Fault-Tolerance Gossip Communication Graph Algorithm Haskell Information Complexity Leader Election Machine Learning Mobile Ad-Hoc Network Natural Language Processing P2P Secure Computation in Networks Self-Healing Symmetry Breaking Wireless Networks## Publications

2018

- Breaking the $\Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late AdversaryDOI

Peter Robinson, Christian Scheideler, Alexander Setzer. 30th ACM Symposium on Parallelism in Algorithms and Architectures. (SPAA 2018).

AbstractWe study the consensus problem in a synchronous distributed system of $n$ nodes under an adaptive adversary that has a slightly outdated view of the system and can block all incoming and outgoing communication of a constant fraction of the nodes in each round. Motivated by a result of Ben-Or and Bar-Joseph (1998), showing that any consensus algorithm that is resilient against a linear number of crash faults requires $\tilde \Omega(\sqrt{n})$ rounds in an $n$-node network against an adaptive adversary, we consider a late adaptive adversary, who has full knowledge of the network state at the beginning of the previous round and unlimited computational power, but is oblivious to the current state of the nodes. Our main contributions are randomized distributed algorithms that achieve consensus with high probability among all except a small constant fraction of the nodes (i.e., ``almost-everywhere'') against a late adaptive adversary who can block up to $\epsilon n$ nodes in each round, for a small constant $\epsilon >0$. Our first protocol achieves binary almost-everywhere consensus and also guarantees a decision on the majority input value, thus ensuring plurality consensus. We also present an algorithm that achieves the same time complexity for multi-value consensus. Both of our algorithms succeed in $O(\log n)$ rounds with high probability, thus breaking the known $\tilde\Omega(\sqrt{n})$ lower bound for fully adaptive adversaries. Our algorithms are scalable to large systems as each node contacts only an (amortized) constant number of peers in each communication round. We show that our algorithms are optimal up to constant (resp. sub-logarithmic) factors by proving that every almost-everywhere consensus protocol takes $\Omega(\log_d n)$ rounds in the worst case, where $d$ is an upper bound on the number of communication requests initiated per node in each round. - Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks

Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, Kyrill Winkler. Theoretical Computer Science 726: 41-77 (2018) (TCS).

2015

- Fast Byzantine Leader Election in Dynamic Networks

John Augustine, Gopal Pandurangan, Peter Robinson. 29th International Symposium on Distributed Computing (DISC 2015).

AbstractMotivated by robust, secure, and efficient distributed computation in Peer-to-Peer (P2P) networks, we study fundamental Byzantine problems in dynamic networks where the topology can change from round to round and nodes can also experience heavy churn (i.e., nodes can join and leave the network continuously over time). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Byzantine protocols for fundamental distributed computing problems such as agreement and leader election have been studied extensively for the last three decades in static networks; however, these solutions do not work in dynamic networks which characterize many real-world networks such as P2P networks. Our main contribution is an $O(\log^3 n)$ round algorithm that achieves Byzantine leader election under the presence of up to $O({n}^{1/2 - \epsilon})$ Byzantine nodes (for a small constant $\epsilon > 0$) and a churn of up to $O(\sqrt{n}/\text{poly}\log(n))$ nodes per round (where $n$ is the stable network size). The algorithm elects a leader with probability at least $1-n^{-\Omega(1)}$ and guarantees that it is an honest node with probability at least $1-n^{-\Omega(1)}$; assuming the algorithm succeeds, the leader's identity will be known to a $1-o(1)$ fraction of the honest nodes. Our algorithm is fully-distributed, localized (does not require any global knowledge), lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic time and requires nodes to send and receive messages of only polylogarithmic size per round. To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way. We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest. In decentralized and dynamic P2P systems where a substantial part of the network may be controlled by malicious nodes, the presented algorithm and techniques can serve as building blocks for designing robust and secure distributed protocols. - Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic NetworksDOI

Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, Kyrill Winkler. 2nd International Conference on Networked Systems (NETYS 2015).

AbstractWe present the first consensus/k-set agreement algorithm for synchronous dynamic networks with unidirectional links, controlled by an omniscient message adversary, which automatically adapts to the actual network properties in a run: If the network is sufficiently well-connected, it solves consensus, while it degrades gracefully to general k-set agreement in less well-connected communication graphs. The actual number k of system-wide decision values is determined by the number of certain vertex-stable root components occurring in a run, which are strongly connected components without incoming links from outside. Related impossibility results reveal that our condition is reasonably close to the solvability border for k-set agreement.

2014

2013

- Fast Byzantine Agreement in Dynamic NetworksPDFDOI

John Augustine, Gopal Pandurangan, Peter Robinson 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013).

AbstractWe study Byzantine agreement in dynamic networks where topology can change from round to round and nodes can also experience heavy churn (i.e., nodes can join and leave the network continuously over time). Our main contributions are randomized distributed algorithms that guarantee almost-everywhere Byzantine agreement with high probability even under a large number of Byzantine nodes and continuous adversarial churn in a number of rounds that is polylogarithmic in $n$ (where $n$ is the stable network size). We show that our algorithms are essentially optimal (up to polylogarithmic factors) with respect to the amount of Byzantine nodes and churn rate that they can tolerate by showing lower bound. In particular, we present the following results: \begin{enumerate} \item An $O(\log^3 n)$ round randomized algorithm that achieves almost-everywhere Byzantine agreement with high probability under a presence of up to $O(\sqrt{n}/\text{polylog}(n))$ Byzantine nodes and up to a churn of $O(\sqrt{n}/\text{polylog}(n))$ nodes per round. We assume that the Byzantine nodes have knowledge about the entire state of network at every round (including random choices made by all the nodes) and can behave arbitrarily. We also assume that an adversary controls the churn --- it has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power (but is oblivious to the topology changes from round to round). Our algorithm requires only polylogarithmic in $n$ bits to be processed and sent (per round) by each node. \item We also present an $O(\log^3 n)$ round randomized algorithm that has same guarantees as the above algorithm, but works even when the churn and network topology is controlled by an adaptive adversary (that can choose the topology based on the current states of the nodes). However, this algorithm requires up to polynomial in $n$ bits to be processed and sent (per round) by each node. \item We show that the above bounds are essentially the best possible, if one wants fast (i.e., polylogarithmic run time) algorithms, by showing that any (randomized) algorithm to achieve agreement in a dynamic network controlled by an adversary that can churn up to $\Theta(\sqrt{ n \log n})$ nodes per round should take at least a polynomial number of rounds. \end{enumerate} Our algorithms are the first-known, fully-distributed, Byzantine agreement algorithms in highly dynamic networks. We view our results as a step towards understanding the possibilities and limitations of highly dynamic networks that are subject to malicious behavior by a large number of nodes.

2012

- Towards Robust and Efficient Computation in Dynamic Peer-to-Peer NetworksPDFDOI

John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).

AbstractMotivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results: \begin{enumerate} \item An $O(\log^2 n)$-round ($n$ is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i.e., $\epsilon n$, for some small constant $\epsilon > 0$), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm). \item An $O(\log m\log^3 n)$-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to $\epsilon \sqrt{n}$ churn per round (for some small $\epsilon > 0$), where $m$ is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). \item We also show that no deterministic algorithm can guarantee almost-everywhere agreement (regardless of the number of rounds), even under constant churn rate. \end{enumerate} Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks. - Agreement in Directed Dynamic NetworksPDFDOI

Martin Biely, Peter Robinson, Ulrich Schmid. 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012).

AbstractWe study distributed computation in synchronous dynamic networks where an omniscient adversary controls the unidirectional communication links. Its behavior is modeled as a sequence of directed graphs representing the active (i.e. timely) communication links per round. We prove that consensus is impossible under some natural weak connectivity assumptions and introduce vertex-stable root components as a means for circumventing this impossibility. Essentially, we assume that there is a short period of time during which an arbitrary part of the network remains strongly connected, while its interconnect topology may keep changing continuously. We present a consensus algorithm that works under this assumption and prove its correctness. Our algorithm maintains a local estimate of the communication graphs and applies techniques for detecting stable network properties and univalent system configurations. Our possibility results are complemented by several impossibility results and lower bounds for consensus and other distributed computing problems like leader election, revealing that our algorithm is asymptotically optimal.

2011

- Easy Impossibility Proofs for k-Set Agreement in Message Passing SystemsPDFDOI

Martin Biely, Peter Robinson, Ulrich Schmid. 15th International Conference On Principles Of Distributed Systems (OPODIS 2011).

AbstractDespite of being quite similar agreement problems, distributed consensus ($1$-set agreement) and general $k$-set agreement require surprisingly different techniques for proving their impossibility in asynchronous systems with crash failures: Rather, than the relatively simple bivalence arguments as in the impossibility proof for consensus in the presence of a single crash failure, known proofs for the impossibility of $k$-set agreement in shared memory systems with $f\geq k>1$ crash failures use algebraic topology or a variant of Sperner's Lemma. In this paper, we present a generic theorem for proving the impossibility of $k$-set agreement in various message passing settings, which is based on a reduction to the consensus impossibility in a certain subsystem resulting from a partitioning argument. We demonstrate the broad applicability of our result by exploring the possibility/impossibility border of $k$-set agreement in several message passing system models: (i) asynchronous systems with crash failures, (ii) partially synchronous processes with (initial) crash failures, and, most importantly, (iii) asynchronous systems augmented with failure detectors. Furthermore, by extending the algorithm for initial crashes of Fisher, Lynch and Patterson (1985) to general $k$-set agreement, we show that the impossibility border of (i) is tightly matched. The impossibility proofs in cases (i), (ii), and (iii) are instantiations of our main theorem. Regarding (iii), applying our technique reveals the exact border for the parameter $k$ where $k$-set agreement is solvable with the failure detector class $(\Sigma_k,\Omega_k)_{1\le k\le n-1}$ of Bonnet and Raynal. As $\Sigma_k$ was shown to be necessary for solving $k$-set agreement, this result yields new insights on the quest for the weakest failure detector - The Asynchronous Bounded-Cycle ModelPDFDOI

Peter Robinson and Ulrich Schmid. Theoretical Computer Science 412 (2011) 5580–5601. (TCS).

AbstractThis paper shows how synchrony conditions can be added to the purely asynchronous model in a way that avoids any reference to message delays and computing step times, as well as any global constraints on communication patterns and network topology. Our Asynchronous Bounded-Cycle (ABC) model just bounds the ratio of the number of forward- and backward-oriented messages in certain ''relevant'' cycles in the space-time diagram of an asynchronous execution. We show that clock synchronization and lock-step rounds can easily be implemented and proved correct in the ABC model, even in the presence of Byzantine failures. Furthermore, we prove that any algorithm working correctly in the partially synchronous $\Theta$-Model also works correctly in the ABC model. In our proof, we first apply a novel method for assigning certain message delays to asynchronous executions, which is based on a variant of Farkas' theorem of linear inequalities and a non-standard cycle-space of graphs. Using methods from point-set topology, we then prove that the existence of this delay assignment implies model indistinguishability for time-free safety and liveness properties. Finally, we introduce several weaker variants of the ABC model and relate our model to the existing partially synchronous system models, in particular, the classic models of Dwork, Lynch and Stockmayer. Furthermore, we discuss aspects of the ABC model's applicability in real systems, in particular, in the context of VLSI Systems-on-Chip.

## Code

I'm interested in parallel and distributed programming and related technologies such as software transactional memory and the actor-model. Recently, I have been working on implementing a simulation environment for distributed algorithms in Elixir/Erlang, and implementing non-blocking data structures in Haskell suitable for multi-core machines. Below is a (non-comprehensive) list of software that I have written.

- concurrent hash table: a thread-safe hash table that scales to multicores.
- data dispersal: an implementation of an (m,n)-threshold information dispersal scheme that is space-optimal.
- secret sharing: an implementation of a secret sharing scheme that provides information-theoretic security.
- tskiplist: a data structure with range-query support for software transactional memory.
- stm-io-hooks: 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.
- I extended Haskell's Cabal, for using a "world" file to keep track of installed packages. (Now part of the main distribution.)

## Teaching

- Computer Networks, Fall 2020, 2019.
- Database Systems, Spring 2020.
- Distributed Computing, Spring 2019.
- Randomized Algorithms, Fall 2018: Intro slides. Part 1 on Concentration Bounds.
- Advanced Distributed Systems, Fall 2016, 2017.
- Computation with Data, Fall 2016.
- Internet and Web Technologies, Spring 2016.

## Misc

- Google scholar profile
- My profile on StackExchange