Author name cluster

Peter Robinson 0002

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

SODA Conference 2021 Conference Paper

Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners

Peter Robinson 0002

We introduce a new measure for quantifying the amount of information that the nodes in a network need to learn to solve a graph problem. We show that the local information cost ( LIC ) presents a natural lower bound on the communication complexity of distributed algorithms. For the synchronous CONGEST-KT 1 model, where each node has initial knowledge of its neighbors' IDs, we prove that bits are required for solving a graph problem P with a τ -round algorithm that errs with probability at most γ. Our result is the first lower bound that yields a general trade-off between communication and time for graph problems in the CONGEST-KT 1 model. We demonstrate how to apply the local information cost by deriving a lower bound on the communication complexity of computing a multiplicative spanner with stretch 2 t – 1 that consists of at most edges, where ∊ = O (1/ t 2 ). Our main result is that any O (poly( n ))-time algorithm must send at least bits in the CONGEST model under the KT 1 assumption. Previously, only a trivial lower bound of bits was known for this problem; in fact, this is the first nontrivial lower bound on the communication complexity of a sparse subgraph problem in this setting. A consequence of our lower bound is that achieving both time- and communication-optimality is impossible when designing a distributed spanner algorithm. In light of the work of King, Kutten, and Thorup (2015), this shows that computing a minimum spanning tree can be done significantly faster than finding a spanner when considering algorithms with Õ ( n ) communication complexity. Our result also implies time complexity lower bounds for constructing a spanner in the node-congested clique of Augustine et al. (2019) and in the push-pull gossip model with limited bandwidth.

Details

STOC Conference 2017 Conference Paper

A time- and message-optimal distributed algorithm for minimum spanning trees

Gopal Pandurangan
Peter Robinson 0002
Michele Scquizzato

This paper presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ( D + √ n ) time and exchanges Õ( m ) messages (both with high probability), where n is the number of nodes of the network, D is the diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω( D + √ n ) [Elkin, SIAM J. Comput. 2006] and the message lower bound of Ω( m ) [Kutten et al., J. ACM 2015], which both apply to randomized Monte Carlo algorithms. The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both Ω( D + √ n ) rounds and Ω( m ) messages.

Details

SODA Conference 2015 Conference Paper

Distributed Computation of Large-scale Graph Problems

Hartmut Klauck
Danupon Nanongkai
Gopal Pandurangan
Peter Robinson 0002

Motivated by the increasing need for fast distributed processing of large-scale graphs such as the Web graph and various social networks, we study a number of fundamental graph problems in the message-passing model, where we have k machines that jointly perform computation on an arbitrary n -node (typically, n ≫ k) input graph. The graph is assumed to be randomly partitioned among the k ≥ 2 machines (a common implementation in many real world systems). The communication is point-to-point, and the goal is to minimize the time complexity, i. e. , the number of communication rounds, of solving various fundamental graph problems. We present lower bounds that quantify the fundamental time limitations of distributively solving graph problems. We first show a lower bound of Ω( n/k ) rounds for computing a spanning tree (ST) of the input graph. This result also implies the same bound for other fundamental problems such as computing a minimum spanning tree (MST), breadth-first tree (BFS), and shortest paths tree (SPT). We also show an Ω( n / k 2 ) lower bound for connectivity, ST verification and other related problems. Our lower bounds develop and use new bounds in random-partition communication complexity. To complement our lower bounds, we also give algorithms for various fundamental graph problems, e. g. , PageRank, MST, connectivity, ST verification, shortest paths, cuts, spanners, covering problems, densest subgraph, subgraph isomorphism, finding triangles, etc. We show that problems such as PageRank, MST, connectivity, and graph covering can be solved in Õ(n/k) time (the notation Õ hides polylog( n ) factors and an additive polylog( n ) term); this shows that one can achieve almost linear (in k ) speedup, whereas for shortest paths, we present algorithms that run in time (for (1 + ε)-factor approximation) and in time (for O (log n )-factor approximation) respectively. Our results step towards understanding the complexity of distributively solving large-scale graph problems.

Details

FOCS Conference 2015 Conference Paper

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

John Augustine 0001
Gopal Pandurangan
Peter Robinson 0002
Scott T. Roche
Eli Upfal

Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy churn (i. e. , Nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a constant degree graph with high expansion even under continuous high adversarial churn. Our protocol can tolerate a churn rate of up to O(n/polylog(n)) per round (where n is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only O(polylog(n)) overhead for topology maintenance: only polylogarithmic(in n) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

Details

SODA Conference 2012 Conference Paper

Towards robust and efficient computation in dynamic peer-to-peer networks

John Augustine 0001
Gopal Pandurangan
Peter Robinson 0002
Eli Upfal

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node churn (i. e. , nodes join and leave the network continuously over time). Our goal is to design fast algorithms (running in a small number of rounds) that guarantee, despite high node churn rate, that almost all nodes reach a stable agreement. Our main contributions are randomized distributed algorithms that guarantee stable almost-everywhere agreement with high probability even under high adversarial churn in a polylogarithmic number of rounds. In particular, we present the following results: 1. An O (log n )-round ( n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to linear churn per round (i. e. , ε n, for some small constant ε > 0), assuming that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm). 2. An O (log m log 3 n )-round randomized algorithm that achieves almost-everywhere agreement with high probability under up to ε√ n churn per round (for some small ε > 0), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm). Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i. e. , high churn rates per step). Furthermore, they are localized (i. e. , do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.

Details