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 "Asynchrony" (Show all)
2017

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.)
2014

The Generalized Loneliness Detector and Weak System Models for kSet Agreement
PDF
DOI
Martin Biely, Peter Robinson, Ulrich Schmid. IEEE Transactions on Parallel and Distributed Systems, vol. 25(4), 10781088 (IEEE TPDS).
Abstract...This paper presents two weak partially synchronous system models MAnti[nk] and MSink[nk], which are just strong enough for solving $k$set agreement: We introduce the generalized $(nk)$loneliness failure detector $\mathcal{L}(k)$, which we first prove to be sufficient for solving $k$set agreement, and show that $\mathcal{L}(k)$ but not $\mathcal{L}(k1)$ can be implemented in both models. MAnti[nk] and MSink[nk] are hence the first message passing models that lie between models where $\Omega$ (and therefore consensus) can be implemented and the purely asynchronous model. We also address $k$set agreement in anonymous systems, that is, in systems where (unique) process identifiers are not available. Since our novel $k$set agreement algorithm using $\mathcal{L}(k)$ also works in anonymous systems, it turns out that the loneliness failure detector $\mathcal{L}=\mathcal{L}(n1)$ introduced by Delporte et al. is also the weakest failure detector for set agreement in anonymous systems. Finally, we analyze the relationship between $\mathcal{L}(k)$ and other failure detectors suitable for solving $k$set agreement.
2011

Weak System Models for FaultTolerant Distributed Agreement Problems
Peter Robinson. PhD Thesis in Computer Science.
Abstract...This thesis investigates various aspects of weak system models for agreement problems in faulttolerant distributed computing. In Part~I we provide an introduction to the context of this work, discuss related literature and describe the basic system assumptions. In Part~II of this thesis, we introduce the Asynchronous BoundedCycle (ABC) model, which is entirely timefree. In contrast to existing system models, the ABC model does not require explicit timebased synchrony bounds, but rather stipulates a graphtheoretic synchrony condition on the relative lengths of certain causal chains of messages in the spacetime graph of a run. We compare the ABC model to other models in literature, in particular to the classic models by Dwork, Lynch, and Stockmeyer. Despite Byzantine failures, we show how to simulate lockstep rounds, and therefore make consensus solvable, and prove the correctness of a clock synchronization algorithm in the ABC model. We then present the technically most involved result of this thesis: We prove that any algorithm working correctly in the partially synchronous $\Theta$Model by Le Lann and Schmid, also works correctly in the timefree ABC model. In the proof, we use a variant of Farkas' Theorem of Linear Inequalities and develop a nonstandard cycle space on directed graphs in order to guarantee the existence of a certain message delay transformation for finite prefixes of runs. This shows that any timefree safety property satisfied by an algorithm in the $\Theta$Model also holds in the ABC model. By employing methods from pointset topology, we can extend this result to liveness properties. In Part~III, we shift our attention to the borderland between models where consensus is solvable and the purely asynchronous model. To this end, we look at the $k$set agreement problem where processes need to decide on at most $k$ distinct decision values. We introduce two very weak system models MAnti and MSink and prove that consensus is impossible in these models. Nevertheless, we show that $(n1)$set agreement is solvable in MAnti and MSink, by providing algorithms that implement the weakest failure detector $\mathcal{L}$. We also discuss how models MAnti and MSink relate to the $f$source models by Aguilera et al. for solving consensus. In the subsequent chapter, we present a novel failure detector $\mathcal{L}(k)$ that generalizes $\mathcal{L}$, and analyze an algorithm for solving $k$set agreement with $\mathcal{L}(k)$, which works even in systems without unique process identifiers. Moreover, We explore the relationship between $\mathcal{L}(k)$ and existing failure detectors for $k$set agreement. Some aspects of $\mathcal{L}(k)$ relating to anonymous systems are also discussed. Next, we present a generic theorem that can be used to characterize the impossibility of achieving $k$set agreement in various system models. This enables us to show that $(\Sigma_k,\Omega_k)$ is not sufficient for solving $k$set agreement. Furthermore, we instantiate our theorem with a partially synchronous system model. Finally, we consider the $k$set agreement problem in roundbased systems. First, we introduce a novel abstraction that encapsulates the perpetual synchrony of a run, the so called stable skeleton graph, which allows us to express the solvability power of a system via graphtheoretic properties. We then present an approximation algorithm where processes output an estimate of their respective component of the stable skeleton graph. We define a class of communication predicates PSources(k) in this framework, and show that PSources(k) tightly captures the amount of synchrony necessary for $k$set agreement, as $(k1)$set agreement is impossible with PSources(k). Based on the stable skeleton approximation, we present an algorithm that solves $k$set agreement when PSources(k) holds. 
Easy Impossibility Proofs for kSet Agreement in Message Passing Systems
PDF
DOI
Martin Biely, Peter Robinson, Ulrich Schmid. 15th International Conference On Principles Of Distributed Systems (OPODIS 2011).
Abstract...Despite of being quite similar agreement problems, distributed consensus ($1$set agreement) and general $k$set agreement require surprisingly different techniques for proving their impossibility in asynchronous systems with crash failures: Rather, than the relatively simple bivalence arguments as in the impossibility proof for consensus in the presence of a single crash failure, known proofs for the impossibility of $k$set agreement in shared memory systems with $f\geq k>1$ crash failures use algebraic topology or a variant of Sperner's Lemma. In this paper, we present a generic theorem for proving the impossibility of $k$set agreement in various message passing settings, which is based on a reduction to the consensus impossibility in a certain subsystem resulting from a partitioning argument. We demonstrate the broad applicability of our result by exploring the possibility/impossibility border of $k$set agreement in several message passing system models: (i) asynchronous systems with crash failures, (ii) partially synchronous processes with (initial) crash failures, and, most importantly, (iii) asynchronous systems augmented with failure detectors. Furthermore, by extending the algorithm for initial crashes of Fisher, Lynch and Patterson (1985) to general $k$set agreement, we show that the impossibility border of (i) is tightly matched. The impossibility proofs in cases (i), (ii), and (iii) are instantiations of our main theorem. Regarding (iii), applying our technique reveals the exact border for the parameter $k$ where $k$set agreement is solvable with the failure detector class $(\Sigma_k,\Omega_k)_{1\le k\le n1}$ of Bonnet and Raynal. As $\Sigma_k$ was shown to be necessary for solving $k$set agreement, this result yields new insights on the quest for the weakest failure detector 
The Asynchronous BoundedCycle Model
PDF
DOI
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 BoundedCycle (ABC) model just bounds the ratio of the number of forward and backwardoriented messages in certain ''relevant'' cycles in the spacetime diagram of an asynchronous execution. We show that clock synchronization and lockstep 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 nonstandard cyclespace of graphs. Using methods from pointset topology, we then prove that the existence of this delay assignment implies model indistinguishability for timefree 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 SystemsonChip.
2009

Weak Synchrony Models and Failure Detectors for Message Passing kSet Agreement
DOI
Martin Biely, Peter Robinson, Ulrich Schmid. 13th International Conference On Principles Of Distributed Systems (OPODIS 2009).
2008

The Asynchronous BoundedCycle Model
DOI
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 BoundedCycle (ABC) model just bounds the ratio of the number of forward and backwardoriented messages in certain ''relevant'' cycles in the spacetime diagram of an asynchronous execution. We show that clock synchronization and lockstep 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 nonstandard cyclespace of graphs. Using methods from pointset topology, we then prove that the existence of this delay assignment implies model indistinguishability for timefree 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 SystemsonChip.
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.