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

Publications

2020
  • Latency, Capacity, and Distributed Minimum Spanning Tree.
    John Augustine, Seth Gilbert, Fabian Kuhn, Peter Robinson, Suman Sourav. 40th IEEE International Conference on Distributed Computing Systems (ICDCS 2020).
2019
  • Slow Links, Fast Links, and the Cost of Gossip.DOI
    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).
    Abstract
    We 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).
    Abstract
    Consider 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

  • Database Systems, Spring 2020.
  • Computer Networks, Fall 2019.
  • 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