Peter Robinson
I'm interested in designing new distributed and parallel algorithms, the distributed processing of big data, achieving faulttolerance in networks, and secure distributed computing in dynamic environments such as peertopeer networks and mobile adhoc networks.
News
 General Chair of ACM PODC 2019
 Program committee member of BGP 2017, SPAA 2016 and of SIROCCO 2016
 Giving a talk at a workshop on Dynamic Graphs in Distributed Computing (colocated with DISC 2016)
 Cochairing the program committee of ICDCN 2016
 Giving a talk at ADGA 2015, (4th Workshop on Advances in Distributed Graph Algorithms, colocated with DISC 2015 )
Keywords (Show all)
«Asynchrony» «Big Data» «Byzantine Failures» «Churn» «Communication Complexity» «Distributed Agreement» «Distributed Storage» «Dynamic Network» «FaultTolerance» «Gossip Communication» «Graph Algorithm» «Haskell» «Leader Election» «Machine Learning» «Mobile AdHoc Network» «Natural Language Processing» «P2P» «Secure Computation» «SelfHealing» «Symmetry Breaking»Publications tagged with "Gossip Communication" (Show all)
2017

Breaking the $\tilde \Omega(\sqrt{n})$ Barrier: Fast Consensus under a Late Adversary
Peter Robinson, Christian Scheideler, Alexander Setzer. (under review)
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 BenOr and BarJoseph (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., ``almosteverywhere'') 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 almosteverywhere 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 multivalue 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. sublogarithmic) factors by proving that every almosteverywhere 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. 
Gossiping with Latencies
Seth Gilbert, Peter Robinson, Suman Sourav. (under review)
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 maxdegree, 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 subalgorithms: This is achieved by combining two cases. When nodes do not know the latency of the adjacent edges, we show that the classical pushpull 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. Below is a (noncomprehensive) list of software that I have written.
 I extended Haskell's Cabal, for using a "world" file to keep track of installed packages. (Now part of the main distribution.)
 data dispersal: an implementation of an (m,n)threshold information dispersal scheme that is spaceoptimal.
 secret sharing: an implementation of a secret sharing scheme that provides informationtheoretic security.
 diceentropy: a library that provides cryptographically secure dice rolls implemented by bitefficient rejection sampling.
 TSkipList: a data structure with rangequery support for software transactional memory.
 stmiohooks: 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.
 In my master thesis I developed a system for automatically constructing events out of log files produced by various system programs. One of the core components of my work was a partofspeech (POS) tagger, which assigns word classes (e.g. noun, verb) to the previously parsed tokens of the log file. To cope with noisy input data, I modeled the POS tagger as a hidden Markov model. I developed (and proved the correctness of) a variant of the maximum likelihood estimation algorithm for training the Markov model and smoothing the state transition distributions.