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

Publications

2019
  • Network Size Estimation in Small-World Networks under Byzantine Faults.DOI
    Soumyottam Chatterjee, Gopal Pandurangan, Peter Robinson. 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2019).
2015
  • Fast Byzantine Leader Election in Dynamic Networks
    John Augustine, Gopal Pandurangan, Peter Robinson. 29th International Symposium on Distributed Computing (DISC 2015).
    Abstract
    Motivated 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.
2013
  • Fast Byzantine Agreement in Dynamic NetworksPDFDOI
    John Augustine, Gopal Pandurangan, Peter Robinson 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013).
    Abstract
    We 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.
2011
  • The Asynchronous Bounded-Cycle ModelPDFDOI
    Peter Robinson and Ulrich Schmid. Theoretical Computer Science 412 (2011) 5580–5601. (TCS).
    Abstract
    This 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.
2008
  • The Asynchronous Bounded-Cycle ModelDOI
    Peter Robinson and Ulrich Schmid. 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2008). Best Paper Award.
    Abstract
    This 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