## Peter Robinson

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.

## News

- General Chair of ACM PODC 2019
- Program committee member of PODC 2020, SIROCCO 2020, DISC 2019

## 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

2019

- Slow Links, Fast Links, and the Cost of GossipDOI

Seth Gilbert, Peter Robinson, Suman Sourav. IEEE Transactions on Parallel and Distributed Systems (IEEE TPDS).

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. - Slow Links, Fast Links, and the Cost of GossipDOI

Seth Gilbert, Peter Robinson, Suman Sourav. 38th IEEE International Conference on Distributed Computing Systems (ICDCS 2018).

AbstractConsider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. In this paper, we study the cost of information dissemination in networks where edges have latencies, i.e., sending a message from one node to another takes some amount of time. We first generalize the idea of conductance to weighted graphs, defining $\phi_*$ to be the ``weighted conductance'' and $\ell_*$ to be the ``critical latency.'' One goal of this paper is to argue that $\phi_*$ characterizes the connectivity of a weighted graph with latencies in much the same way that conductance characterizes the connectivity of unweighted graphs. We give near tight upper and lower bounds on the problem of information dissemination, up to polylogarithmic factors. Specifically, we show that in a graph with (weighted) diameter $D$ (with latencies as weights), maximum degree $\Delta$, weighted conductance $\phi_*$ and critical latency $\ell_*$, any information dissemination algorithm requires at least $\Omega(\min(D+\Delta, \ell_*/\phi_*))$ time. We show several variants of the lower bound (e.g., for graphs with small diameter, graphs with small max-degree, etc.) by reduction to a simple combinatorial game. We then give nearly matching algorithms, showing that information dissemination can be solved in $O(\min((D + \Delta)\log^3{n}), (\ell_*/\phi_*)\log(n))$ time. % $O(\min(D\log^3(n), \ell_*\log(n)/\phi_*))$. The algorithm consists of two sub-algorithms: This is achieved by combining two cases. When nodes do not know the latency of the adjacent edges, we show that the classical push-pull algorithm is (near) optimal when the diameter or maximum degree is large. For the case where the diameter and maximum degree are small, we give an alternative strategy in which we first discover the latencies and then use an algorithm for known latencies based on a weighted spanner construction. (Our algorithms are within polylogarithmic factors of being tight both for known and unknown latencies.)

## 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

- CAS781 Randomized Algorithms, Fall 2018: More slides.Intro slides.
- CS5860 Advanced Distributed Systems, Fall 2016, 2017.
- CS5800 Computation with Data, Fall 2016.
- BI5632 Internet and Web Technologies, Spring 2016.
- CSC2008 Networks and Communications, Fall 2015.

## Misc

- Google scholar profile
- My profile on StackExchange