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.
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
- Fault-Tolerant Consensus with an Abstract MAC Layer.
Calvin Newport and Peter Robinson. 32nd International Symposium on Distributed Computing (DISC 2018).
AbstractIn this paper, we study fault-tolerant distributed consensus in wireless systems. In more detail, we produce two new randomized algorithms that solve this problem in the abstract MAC layer model, which captures the basic interface and communication guarantees provided by most wireless MAC layers. Our algorithms work for any number of failures, require no advance knowledge of the network participants or network size, and guarantee termination with high probability after a number of broadcasts that are polynomial in the network size. Our first algorithm satisfies the standard agreement property, while our second trades a faster termination guarantee in exchange for a looser agreement property in which most nodes agree on the same value. These are the first known fault-tolerant consensus algorithms for this model. In addition to our main upper bound results, we explore the gap between the abstract MAC layer and the standard asynchronous message passing model by proving fault-tolerant consensus is impossible in the latter in the absence of information regarding the network participants, even if we assume no faults, allow randomized solutions, and provide the algorithm a constant-factor approximation of the network size.
- 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.)
- 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.