Random walks in distributed networks are useful primitives with numerous applications. In this paper, we focus on efficient distributed algorithms for performing random walks and their application to generating random spanning trees (RST) in arbitrary networks. The goal is to minimize the number of rounds required to output the positions of vertices in a random walk starting from a given source and to generate an RST in the standard CONGEST model.

Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the message complexity of distributed computing problems and its relationship (if any) with round complexity is still quite limited. To illustrate, for many fundamental distributed graph optimization problems such as (exact) diameter computation, All-Pairs Shortest Paths (APSP), Maximum Matching etc., while (near) round-optimal algorithms are known, message-optimal algorithms are hitherto unknown. More importantly, the existing round-optimal algorithms are not message-optimal. This raises two important questions: (1) Can we design message-optimal algorithms for these problems? (2) Can we give message-time tradeoffs for these problems in case the message-optimal algorithms are not round-optimal?

We present the first sublinear-in-n round algorithm for sampling an approximately uniform spanning tree of an n-vertex graph in the CongestedClique model of distributed computing. In particular, our algorithm requires Õ (n0.657) rounds for sampling a spanning tree within total variation distance 1/nc, for arbitrary constant c > 0, from the uniform distribution. More precisely, our algorithm requires Õ (n1/2+α) rounds, where O (nα) is the running time of matrix multiplication in the CongestedClique model (currently α = 1-2/ω = 0.157, where ω is the sequential matrix multiplication time exponent). We can adapt our algorithm to give exact rather than approximate samples, but with a larger, though still o (n), runtime of Õ(n2/3+α) = O(n0.824).

As observed in the case of COVID-19, effective vaccines for an emerging pandemic tend to be in limited supply initially and must be allocated strategically. The allocation of vaccines can be modeled as a discrete optimization problem that prior research has shown to be computationally difficult (i.e., NP-hard) to solve even approximately. Using a combination of theoretical and experimental results, we show that this hardness result may be circumvented. We present our results in the context of a metapopulation model, which views a population as composed of geographically dispersed heterogeneous subpopulations, with arbitrary travel patterns between them. In this setting, vaccine bundles are allocated at a subpopulation level, and so the vaccine allocation problem can be formulated as a problem of maximizing an integer lattice function [Formula: see text] subject to a budget constraint [Formula: see text]. We consider a variety of simple, well-known greedy algorithms for this problem and show the effectiveness of these algorithms for three problem instances at different scales: New Hampshire (10 counties, population 1.4 million), Iowa (99 counties, population 3.2 million), and Texas (254 counties, population 30.03 million). We provide a theoretical explanation for this effectiveness by showing that the approximation factor (a measure of how well the algorithmic output for a problem instance compares to its theoretical optimum) of these algorithms depends on the submodularity ratio of the objective function g. The submodularity ratio of a function is a measure of how distant g is from being submodular; here submodularity refers to the very useful "diminishing returns" property of set and lattice functions, i.e., the property that as the function inputs are increased the function value increases, but not by as much.

The message complexity of a distributed algorithm is the total number of messages sent by all nodes over the course of the algorithm. This paper studies the message complexity of distributed algorithms for fundamental graph optimization problems. We focus on four classical graph optimization problems: Maximum Matching (MaxM), Minimum Vertex Cover (MVC), Minimum Dominating Set (MDS), and Maximum Independent Set (MaxIS). In the sequential setting, these problems are representative of a wide spectrum of hardness of approximation. While there has been some progress in understanding the round complexity of distributed algorithms (for both exact and approximate versions) for these problems, much less is known about their message complexity and its relation with the quality of approximation. We almost fully quantify the message complexity of distributed graph optimization by showing the following results: 1) Cubic regime: Our first main contribution is showing essentially cubic, i.e., Ω̃(n³) lower bounds (where n is the number of nodes in the graph) on the message complexity of distributed exact computation of Minimum Vertex Cover (MVC), Minimum Dominating Set (MDS), and Maximum Independent Set (MaxIS). Our lower bounds apply to any distributed algorithm that runs in polynomial number of rounds (a mild and necessary restriction). Our result is significant since, to the best of our knowledge, this are the first ω(m) (where m is the number of edges in the graph) message lower bound known for distributed computation of such classical graph optimization problems. Our bounds are essentially tight, as all these problems can be solved trivially using O(n³) messages in polynomial rounds. All these bounds hold in the standard CONGEST model of distributed computation in which messages are of O(log n) size. 2) Quadratic regime: In contrast, we show that if we allow approximate computation then Θ̃(n²) messages are both necessary and sufficient. Specifically, we show that Ω̃(n²) messages are required for constant-factor approximation algorithms for all four problems. For MaxM and MVC, these bounds hold for any constant-factor approximation, whereas for MDS and MaxIS they hold for any approximation factor better than some specific constants. These lower bounds hold even in the LOCAL model (in which messages can be arbitrarily large) and they even apply to algorithms that take arbitrarily many rounds. We show that our lower bounds are essentially tight, by showing that if we allow approximation to within an arbitrarily small constant factor, then all these problems can be solved using Õ(n²) messages even in the CONGEST model. 3) Linear regime: We complement the above lower bounds by showing distributed algorithms with Õ(n) message complexity that run in polylogarithmic rounds and give constant-factor approximations for all four problems on random graphs. These results imply that almost linear (in n) message complexity is achievable on almost all (connected) graphs of every edge density.

Healthcare acquired infections (HAIs) (e.g., Methicillin-resistant Staphylococcus aureus infection) have complex transmission pathways, spreading not just via direct person-to-person contacts, but also via contaminated surfaces. Prior work in mathematical epidemiology has led to a class of models – which we call load sharing models – that provide a discrete-time, stochastic formalization of HAI-spread on temporal contact networks. The focus of this paper is the source detection problem for the load sharing model. The source detection problem has been studied extensively in SEIR type models, but this prior work does not apply to load sharing models. We show that a natural formulation of the source detection problem for the load sharing model is computationally hard, even to approximate. We then present two alternate formulations that are much more tractable. The tractability of our problems depends crucially on the submodularity of the expected number of infections as a function of the source set. Prior techniques for showing submodularity, such as the "live graph" technique are not applicable for the load sharing model and our key technical contribution is to use a more sophisticated "coupling" technique to show the submodularity result. We propose algorithms for our two problem formulations by extending existing algorithmic results from submodular optimization and combining these with an expectation propagation heuristic for the load sharing model that leads to orders-of-magnitude speedup. We present experimental results on temporal contact networks based on fine-grained EMR data from three different hospitals. Our results on synthetic outbreaks on these networks show that our algorithms outperform baselines by up to 5.97 times. Furthermore, case studies based on hospital outbreaks of Clostridioides difficile infection show that our algorithms identify clinically meaningful sources.

As hospitals move towards automating and integrating their computing systems, more fine-grained hospital operations data are becoming available. These data include hospital architectural drawings, logs of interactions between patients and healthcare professionals, prescription data, procedures data, and data on patient admission, discharge, and transfers. This has opened up many fascinating avenues for healthcare-related prediction tasks for improving patient care. However, in order to leverage off-the-shelf machine learning software for these tasks, one needs to learn structured representations of entities involved from heterogeneous, dynamic data streams. Here, we propose DECENT, an auto-encoding heterogeneous co-evolving dynamic neural network, for learning heterogeneous dynamic embeddings of patients, doctors, rooms, and medications from diverse data streams. These embeddings capture similarities among doctors, rooms, patients, and medications based on static attributes and dynamic interactions. DECENT enables several applications in healthcare prediction, such as predicting mortality risk and case severity of patients, adverse events (e.g., transfer back into an intensive care unit), and future healthcare-associated infections. The results of using the learned patient embeddings in predictive modeling show that DECENT has a gain of up to 48.1% on the mortality risk prediction task, 12.6% on the case severity prediction task, 6.4% on the medical intensive care unit transfer task, and 3.8% on the Clostridioides difficile (C.diff) Infection (CDI) prediction task over the state-of-the-art baselines. In addition, case studies on the learned doctor, medication, and room embeddings show that our approach learns meaningful and interpretable embeddings.

Healthcare associated infections (HAIs) impose a substantial burden, both on patients and on the healthcare system. Designing effective strategies by using interventions such as vaccination, isolation, cleaning, mobility modification, etc., to reduce HAI spread is an important computational challenge. Spectral approaches are quite useful for modeling and solving problems of reducing disease spread over contact networks, but they have not been used for disease-spread models and contact networks that are specific for HAIs. Our main contribution in this paper is to close this gap. We make 3 specific contributions. (i) We present the first epidemic threshold results on temporal bipartite networks, i.e., a time-varying sequence of bipartite people-location network, for the Susceptible-Infected-Susceptible (SIS) model. (ii) We leverage our epidemic threshold result to pose the HAI mitigation problem as minimizing the spectral radius of the system matrix, while removing few nodes or edges. We present a scalable combinatorial algorithm that provides approximation guarantees. (iii) Through extensive experiments on actual healthcare contact networks derived from operations data from the University of Iowa Hospitals and Clinics, Carilion Clinic, and several other healthcare facilities, we show that our algorithm consistently outperforms a number of baselines (random, degree, top-k, eigen centrality) both in terms of reducing the spectral radius of the system matrix and in terms of reducing infections.

In this paper we present a deterministic O(log log n)-round algorithm for the 2-ruling set problem in the Massively Parallel Computation model with Õ(n) memory; this algorithm also runs in O(log log n) rounds in the Congested Clique model. This is exponentially faster than the fastest known deterministic 2-ruling set algorithm for these models, which is simply the O(log Δ)-round deterministic Maximal Independent Set algorithm due to Czumaj, Davies, and Parter (SPAA 2020). Our result is obtained by derandomizing the 2-ruling set algorithm of Kothapalli and Pemmaraju (FSTTCS 2012).

The clustering problem, in its many variants, has numerous applications in operations research and computer science (e.g., in applications in bioinformatics, image processing, social network analysis, etc.). As sizes of data sets have grown rapidly, researchers have focused on designing algorithms for clustering problems in models of computation suited for large-scale computation such as MapReduce, Pregel, and streaming models. The k-machine model (Klauck et al., SODA 2015) is a simple, message-passing model for large-scale distributed graph processing. This paper considers three of the most prominent examples of clustering problems: the uncapacitated facility location problem, the p-median problem, and the p-center problem and presents O (1)-factor approximation algorithms for these problems running in Õ (n/k) rounds in the k -machine model. These algorithms are optimal upto polylogarithmic factors because this paper also shows Ω (n/k) lower bounds for obtaining poly(n)-factor approximation algorithms for these problems. These are the first results for clustering problems in the k -machine model.

This paper studies the problem of detecting asymptomatic cases in a temporal contact network in which multiple outbreaks have occurred. For many infections, asymptomatic cases present a major obstacle to obtaining a precise understanding of infection-spread. We show that the key to detecting asymptomatic cases well, is taking into account both individual risk as well as the likelihood of disease-flow along edges. Most related research has ignored the interplay between these dual aspects influencing disease-spread. We take both aspects into account by formulating the asymptomatic case detection problem as a Directed Prize-Collecting Steiner Tree (DIRECTED PCST) problem. We present an approximation-preserving reduction from this problem to the Directed Steiner Tree problem and use this reduction to obtain scalable algorithms for the DIRECTED PCST problem. Using these algorithms, we solve instances with more than 1.5M edges obtained from both synthetic and actual fine-grained hospital data. On synthetic data, we demonstrate that our detection methods significantly outperform various baselines (with a gain of $3.6 \times$). As an application of our methods, we use a measure of exposure to detected asymptomatic Clostridioides difficile (C. diff) infection (CDI) cases as an additional feature for the important task of predicting symptomatic CDI cases. In this application, our method outperforms all baselines, including those that don’t use asymptomatic CDI cases as a feature and those that use other methods for detecting asymptomatic CDI cases. We also demonstrate that the solutions returned by our approach are clinically meaningful by presenting a case study.

We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in understanding and improving the running time of such problems, much less is known about the message complexity of these problems. In fact, all known algorithms need at least Ω(m) communication for these problems, where m is the number of edges in the graph. We addressthe following question in this paper: can we solve problems such as coloring and MIS using sublinear, i.e., o(m) communication, and if sounder what conditions?

This paper describes a data-driven simulation study that explores the relative impact of several low-cost and practical non-pharmaceutical interventions on the spread of COVID-19 in an outpatient hospital dialysis unit. The interventions considered include: (i) voluntary self-isolation of healthcare personnel (HCPs) with symptoms; (ii) a program of active syndromic surveillance and compulsory isolation of HCPs; (iii) the use of masks or respirators by patients and HCPs; (iv) improved social distancing among HCPs; (v) increased physical separation of dialysis stations; and (vi) patient isolation combined with preemptive isolation of exposed HCPs. Our simulations show that under conditions that existed prior to the COVID-19 outbreak, extremely high rates of COVID-19 infection can result in a dialysis unit. In simulations under worst-case modeling assumptions, a combination of relatively inexpensive interventions such as requiring surgical masks for everyone, encouraging social distancing between healthcare professionals (HCPs), slightly increasing the physical distance between dialysis stations, and-once the first symptomatic patient is detected-isolating that patient, replacing the HCP having had the most exposure to that patient, and relatively short-term use of N95 respirators by other HCPs can lead to a substantial reduction in both the attack rate and the likelihood of any spread beyond patient zero. For example, in a scenario with R0 = 3.0, 60% presymptomatic viral shedding, and a dialysis patient being the infection source, the attack rate falls from 87.8% at baseline to 34.6% with this intervention bundle. Furthermore, the likelihood of having no additional infections increases from 6.2% at baseline to 32.4% with this intervention bundle.

Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al.~PODC 2019; Ghaffari-Uitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for large-scale distributed computing and it comes with the constraint that the memory-per-machine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming $\tildeΩ(n)$ memory-per-machine, where $n$ is the number of nodes in the graph (e.g., the $O(\log\log n)$ MIS algorithm of Ghaffari et al., PODC 2018). However, it has proven much more difficult to design fast MPC algorithms for graph problems in the low-memory MPC model, where the memory-per-machine is restricted to being strongly sublinear in the number of nodes, i.e., $O(n^\eps)$ for $0 < \eps < 1$. In this paper, we present an algorithm for the 2-ruling set problem, running in $\tilde{O}(\log^{1/6} Δ)$ rounds whp, in the low-memory MPC model. We then extend this result to $β$-ruling sets for any integer $β> 1$. Specifically, we show that a $β$-ruling set can be computed in the low-memory MPC model with $O(n^\eps)$ memory-per-machine in $\tilde{O}(β\cdot \log^{1/(2^{β+1}-2)} Δ)$ rounds, whp. From this it immediately follows that a $β$-ruling set for $β= Ω(\log\log\log Δ)$-ruling set can be computed in in just $O(β\log\log n)$ rounds whp. The above results assume a total memory of $\tilde{O}(m + n^{1+\eps})$. We also present algorithms for $β$-ruling sets in the low-memory MPC model assuming that the total memory over all machines is restricted to $\tilde{O}(m)$.

We prove three new lower bounds for graph connectivity in the $1$-bit broadcast congested clique model, BCC$(1)$. First, in the KT-$0$ version of BCC$(1)$, in which nodes are aware of neighbors only through port numbers, we show an $Ω(\log n)$ round lower bound for CONNECTIVITY even for constant-error randomized Monte Carlo algorithms. The deterministic version of this result can be obtained via the well-known "edge-crossing" argument, but, the randomized version of this result requires establishing new combinatorial results regarding the indistinguishability graph induced by inputs. In our second result, we show that the $Ω(\log n)$ lower bound result extends to the KT-$1$ version of the BCC$(1)$ model, in which nodes are aware of IDs of all neighbors, though our proof works only for deterministic algorithms. Since nodes know IDs of their neighbors in the KT-$1$ model, it is no longer possible to play "edge-crossing" tricks; instead we present a reduction from the 2-party communication complexity problem PARTITION in which Alice and Bob are give two set partitions on $[n]$ and are required to determine if the join of these two set partitions equals the trivial one-part set partition. While our KT-$1$ CONNECTIVITY lower bound holds only for deterministic algorithms, in our third result we extend this $Ω(\log n)$ KT-1 lower bound to constant-error Monte Carlo algorithms for the closely related CONNECTED COMPONENTS problem. We use information-theoretic techniques to obtain this result. All our results hold for the seemingly easy special case of CONNECTIVITY in which an algorithm has to distinguish an instance with one cycle from an instance with multiple cycles. Our results showcase three rather different lower bound techniques and lay the groundwork for further improvements in lower bounds for CONNECTIVITY in the BCC$(1)$ model.

We investigate graph problems in the following setting: we are given a graph G and we are required to solve a problem on G2. While we focus mostly on exploring this theme in the distributed CONGEST model, we also show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on G2 would be quite difficult to solve efficiently on G, due to congestion. However, we show that the picture is both more complicated and more interesting.

This paper presents a high-fidelity agent-based simulation of the spread of methicillin-resistant Staphylococcus aureus (MRSA), a serious hospital acquired infection, within the dialysis unit at the University of Iowa Hospitals and Clinics (UIHC). The simulation is based on ten days of fine-grained healthcare worker (HCW) movement and interaction data collected from a sensor mote instrumentation of the dialysis unit by our research group in the fall of 2013. The simulation layers a detailed model of MRSA pathogen transfer, die-off, shedding, and infection on top of agent interactions obtained from data. The specific question this paper focuses on is whether there are simple, inexpensive architectural or process changes one can make in the dialysis unit to reduce the spread of MRSA? We evaluate two architectural changes of the nurses' station: (i) splitting the central nurses' station into two smaller distinct nurses' stations, and (ii) doubling the surface area of the nursing station. The first architectural change is modeled as a graph partitioning problem on a HCW contact network obtained from our HCW movement data. Somewhat counter-intuitively, our results suggest that the first architectural modification and the resulting reduction in HCW-HCW contacts has little to no effect on the spread of MRSA and may in fact lead to an increase in MRSA infection counts in some cases. In contrast, the second modification leads to a substantial reduction - between 12% and 22% for simulations with different parameters - in the number of patients infected by MRSA. These results suggest that the dynamics of an environmentally mediated infection such as MRSA may be quite different from that of infections whose spread is not substantially affected by the environment (e.g., respiratory infections or influenza).

We prove three new lower bounds for graph connectivity in the 1-bit broadcast congested clique model, BCC(1). First, in the KT-0 version of BCC(1), in which nodes are aware of neighbors only through port numbers, we show an Ømega(log n) round lower bound for CONNECTIVITY even for constant-error randomized Monte Carlo algorithms. The deterministic version of this result can be obtained via the well-known "edge-crossing" argument, but, the randomized version of this result requires establishing new combinatorial results regarding the indistinguishability graph induced by inputs. In our second result, we show that the Ømega(log n) lower bound result extends to the KT-1 version of the BCC(1) model, in which nodes are aware of IDs of all neighbors, though our proof works only for deterministic algorithms. Since nodes know IDs of their neighbors in the KT-1 model, it is no longer possible to play "edge-crossing" tricks; instead we present a reduction from the 2-party communication complexity problem PARTITION in which Alice and Bob are give two set partitions on [n] and are required to determine if the join of these two set partitions equals the trivial one-part set partition. While our KT-1 CONNECTIVITY lower bound holds only for deterministic algorithms, in our third result we extend this Ømega(log n) KT-1 lower bound to constant-error Monte Carlo algorithms for the closely related CONNECTED COMPONENTS problem. We use information-theoretic techniques to obtain this result. All our results hold for the seemingly easy special case of CONNECTIVITY in which an algorithm has to distinguish an instance with one cycle from an instance with multiple cycles. Our results showcase three rather different lower bound techniques and lay the groundwork for further improvements in lower bounds for CONNECTIVITY in the BCC(1) model.

The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related $β$-ruling set problem, in two computational models suited for large-scale graph processing, namely the $k$-machine model and the graph streaming model. We present a number of results. For MIS in the $k$-machine model, we improve the $\tilde{O}(m/k^2 + Δ/k)$-round upper bound of Klauck et al. (SODA 2015) by presenting an $\tilde{O}(m/k^2)$-round algorithm. We also present an $\tildeΩ(n/k^2)$ round lower bound for MIS, the first lower bound for a symmetry breaking problem in the $k$-machine model. For $β$-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the $k$-machine model and also in the graph streaming model. More specifically, we obtain a $k$-machine algorithm that runs in $\tilde{O}(βnΔ^{1/β}/k^2)$ rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use $O(β\cdot n^{1+1/2^{β-1}})$ space. The latter result establishes a clear separation between MIS, which is known to require $Ω(n^2)$ space (Cormode et al., ICALP 2019), and $β$-ruling sets, even for $β= 2$. Finally, we present an even faster 2-ruling set algorithm in the $k$-machine model, one that runs in $\tilde{O}(n/k^{2-ε} + k^{1-ε})$ rounds for any $ε$, $0 \le ε\le 1$.

This paper presents fast, distributed, $O(1)$-approximation algorithms for metric facility location problems with outliers in the Congested Clique model, Massively Parallel Computation (MPC) model, and in the $k$-machine model. The paper considers Robust Facility Location and Facility Location with Penalties, two versions of the facility location problem with outliers proposed by Charikar et al. (SODA 2001). The paper also considers two alternatives for specifying the input: the input metric can be provided explicitly (as an $n \times n$ matrix distributed among the machines) or implicitly as the shortest path metric of a given edge-weighted graph. The results in the paper are: - Implicit metric: For both problems, $O(1)$-approximation algorithms running in $O(\mbox{poly}(\log n))$ rounds in the Congested Clique and the MPC model and $O(1)$-approximation algorithms running in $\tilde{O}(n/k)$ rounds in the $k$-machine model. - Explicit metric: For both problems, $O(1)$-approximation algorithms running in $O(\log\log\log n)$ rounds in the Congested Clique and the MPC model and $O(1)$-approximation algorithms running in $\tilde{O}(n/k)$ rounds in the $k$-machine model. Our main contribution is to show the existence of Mettu-Plaxton-style $O(1)$-approximation algorithms for both Facility Location with outlier problems. As shown in our previous work (Berns et al., ICALP 2012, Bandyapadhyay et al., ICDCN 2018) Mettu-Plaxton style algorithms are more easily amenable to being implemented efficiently in distributed and large-scale models of computation.

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-standing Θ(log n) time-complexity barrier and the Θ(m) message-complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems?

We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the long-standing O(log n)-round "barrier" achieved by Luby's algorithm, but these yield o(log n)-round complexity only when the maximum degree Delta is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby's algorithm) even for moderately small Delta (i.e., for Delta = Omega(log n) and Delta = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby's algorithm takes O(m) messages on m-edge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the Theta(log n) time complexity barrier and the Theta(m) message complexity barrier in the Congest model for MIS or closely-related symmetry breaking problems? This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A beta-ruling set is an independent set such that every node in the graph is at most beta hops from a node in the independent set. We present the following results: - Time Complexity: We show that we can break the O(log n) "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in O(log n/log log n) rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O(log Delta (log n)^(1/2 + epsilon) + log n/log log n) rounds for any epsilon > 0, which is o(log n) for a wide range of Delta values (e.g., Delta = 2^(log n)^(1/2-epsilon)). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby's algorithm in the Congest model. - Message Complexity: We show an Omega(n^2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log^2 n) messages and runs in O(Delta log n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor).

In a sequence of recent results (PODC 2015 and PODC 2016), the running time of the fastest algorithm for the minimum spanning tree (MST) problem in the Congested Clique model was first improved to O(log(log(log(n)))) from O(log(log(n))) (Hegeman et al., PODC 2015) and then to O(log^*(n)) (Ghaffari and Parter, PODC 2016). All of these algorithms use Theta(n^2) messages independent of the number of edges in the input graph. This paper positively answers a question raised in Hegeman et al., and presents the first "super-fast" MST algorithm with o(m) message complexity for input graphs with m edges. Specifically, we present an algorithm running in O(log^*(n)) rounds, with message complexity ~O(sqrt{m * n}) and then build on this algorithm to derive a family of algorithms, containing for any epsilon, 0 < epsilon <= 1, an algorithm running in O(log^*(n)/epsilon) rounds, using ~O(n^{1 + epsilon}/epsilon) messages. Setting epsilon = log(log(n))/log(n) leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only ~O(n) messages. Our primary tools in achieving these results are (i) a component-wise bound on the number of candidates for MST edges, extending the sampling lemma of Karger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and (ii) Theta(log(n))-wise-independent linear graph sketches (Cormode and Firmani, Dist. Par. Databases, 2014) for generating MST candidate edges.

Until recently, the fastest distributed MIS algorithm, even for simple graph classes such as unoriented trees that can contain large independent sets within neighborhoods, has been the simple randomized algorithm discovered independently by several researchers in the late 80s. This algorithm (commonly called Luby’s algorithm) computes an MIS of an n-node graph in O(log n) communication rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a distributed (randomized) MIS algorithm for unoriented treesrunning in O( sqrt (log n * log log n)) rounds. This algorithm was slightly improved by Barenboim et al. (FOCS 2012), resulting in an O( sqrt (log n * log log n))-round (randomized) MIS algorithm for trees. At their core, these algorithms still run Luby's algorithm, but only up to the point at which the graph has been "shattered" into small connected components that can be independently processed in parallel. The analyses of these tree MIS algorithms critically depends on "near independence" among probabilistic events, a feature that arises from the tree structure of the network. In their paper, Lenzen and Wattenhofer express hope that their algorithm and analysis could be extended to graphs with bounded arboricity. We show how to do this in the current paper. By using a new tail inequality for read-k families of random variables due to Gavinsky et al. (Random Struct Algorithms, 2015), we show how to deal with dependencies induced by the recent tree MIS algorithms when they are executed on bounded arboricity graphs. Specifically, we analyze a version of the tree MIS algorithm of Barenboim et al. and show that it runs in O(poly(a) * sqrt ( log n * log log n)) rounds in the CONGEST model for graphs with arboricity a. While the main thrust of this paper is the new probabilistic analysis via read-k inequalities, we point out that for small values of a, this algorithm is faster than the MIS algorithm of Barenboim et al. specifically designed for bounded arboricity graphs. In this context, it should be noted that recently (in SODA 2016) Ghaffari presented a novel distributed MIS algorithm for general graphs that runs in O (log d) + 2^O(sqrt(log log n)) rounds and a corollary of this algorithm is an O(log d + sqrt (log n))-round MIS algorithm on graphs with arboricity a.

Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees, has been the simple randomized algorithm discovered in the 80s. This algorithm (commonly called Luby's algorithm) computes an MIS in O(log n) rounds (with high probability). This situation changed when Lenzen and Wattenhofer (PODC 2011) presented a randomized O(√log n} ⋅ log\log n)-round MIS algorithm for unoriented trees. This algorithm was improved by Barenboim et al. (FOCS 2012), resulting in an MIS algorithm running in O(√log n ⋅ log\log n) rounds.

We study two fundamental graph problems, Graph Connectivity (GC) and Minimum Spanning Tree (MST), in the well-studied Congested Clique model, and present several new bounds on the time and message complexities of randomized algorithms for these problems. No non-trivial (i.e., super-constant) time lower bounds are known for either of the aforementioned problems; in particular, an important open question is whether or not constant-round algorithms exist for these problems. We make progress toward answering this question by presenting randomized Monte Carlo algorithms for both problems that run in O(log log log n) rounds (where n is the size of the clique). Our results improve by an exponential factor on the long-standing (deterministic) time bound of O(log log n) rounds for these problems due to Lotker et al. (SICOMP 2005). Our algorithms make use of several algorithmic tools including graph sketching, random sampling, and fast sorting.

A t-ruling set of a graph G = (V, E) is a vertex-subset S ⊆ V that is independent and satisfies the property that every vertex v ∈ V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al. (FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O(t ⋅ log1/(t-1)n) rounds for 2 < t ≤ √(log log n) and in (O(√(log log n))) rounds for t > √(log log n).

A t-ruling set of a graph G = (V, E) is a vertex-subset S that is independent and satisfies the property that every vertex v in V is at a distance of at most t from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. The problem of computing an MIS on a network is a fundamental problem in distributed algorithms and the fastest algorithm for this problem is the O(log n)-round algorithm due to Luby (SICOMP 1986) and Alon et al. (J. Algorithms 1986) from more than 25 years ago. Since then the problem has resisted all efforts to yield to a sub-logarithmic round algorithm. There has been recent progress on this problem, most importantly an O(log Delta . sqrt(log n))-round algorithm on graphs with n vertices and maximum degree Delta, due to Barenboim et al. (to appear FOCS 2012). The time complexity of this algorithm is sub-logarithmic for Delta =2^{o(sqrt{log n})}. We approach the MIS problem from a different angle and ask if O(1)-ruling sets can be computed faster than the currently known fastest algorithm for an MIS? As an answer to this question, we show how to compute a 2-ruling set of an n-vertex graph in O((log n)^{3/4}) rounds. We also show that the above result can be improved for special classes of graphs. For instance, on high girth graphs (girth 6 or more), trees, and graphs of bounded arboricity, we show how to compute 3-ruling sets in exp(O({sqrt{loglog n}})) rounds, O((log log n)^2 .logloglog n) rounds, and O((loglog n)^3) rounds, respectively. Our main technique involves randomized sparsification that rapidly reduces the graph degree while ensuring that every deleted vertex is close to some vertex that remains. This technique may have further applications in other contexts, e.g., in designing sub-logarithmic distributed approximation algorithms. Our results raise intriguing questions about how quickly an MIS (or 1-ruling sets) can be computed, given that 2-ruling sets can be computed in sub-logarithmic rounds.

This paper considers the question of how many colors a distributed graph coloring algorithm would need to use if it had only k rounds available, for any positive integer k. In our main result, we present an algorithm that runs in O(k) rounds for any k bounded below by ©(log log n) and bounded above by O(√log n), and uses O(a Å n1/k) colors to color a graph with arboricity a. This result is optimal since the palette size matches the lower bound of Barenboim and Elkin (PODC 2008). This result is achieved via the use of several new results developed in this paper on coloring graphs whose edges have been acyclically oriented. For example, suppose that G is an n-vertex, acyclically oriented graph with maximum out-degree Δo. We present an algorithm that, for any k ≥ 2 loglog n, runs in O(k) rounds on G to produce an (i) O(Δo)-coloring when Δo Δ ©(maxkn2/k2log1+1/k n, 2k) and an (ii) O(Δo Å n2/k2)-coloring when Δo ∈ Ω(maxk log1+1/k n, 2k). These results are useful in any setting where it is possible to efficiently compute acyclic orientations of a graph with Δo << Δ. We derive non-trivial bounds on the palette size even when k < 2 loglog n.

Given a graph G = ( V, E ) and positive integral vertex weights w : V → N , the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C 1 , C 2 , …, C k , minimize ∑ i =1 k max v ∈ C i w ( v ). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system. Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 ċ χ( G ) colors, significantly improving the bound of 26 ċ χ( G ) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard. The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i ∈ I having an associated bandwidth b ( i ) ∈ (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r , the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.

The Emerging Infections Network (EIN) (http://ein.idsociety.org/) is a CDC supported “sentinel” network of over 1400 members (currently), designed to connect clinical infectious disease specialists and public health officials. Members primarily communicate through an EIN managed listserv and discuss disease outbreaks, treatment protocols, effectiveness of vaccinations and other disease-control and prevention mechanisms, etc. Recently, researchers at Google and Yahoo! Research have used search engine query logs to tap into the online “wisdom of crowds” and produce disease outbreak trends for flu. Following this work, there is now interest in trying to monitor EIN discussions more carefully to disseminate timely and accurate information on clinical events of possible interest to health officials. We model the problem of monitoring a listserv, such as the EIN, as a type of budgeted maximum coverage problem that we call Budgeted Maximization with Overlapping Costs (BMOC). Even though BMOC seems superficially similar to the budgeted maximum coverage problem considered by Khuller et al. (Inf. Process. Lett., 1999), our problem is fundamentally different from an algorithmic point of view, due to its cost structure. We observe that the greedy algorithm that provides a constant-factor approximation to the budgeted maximum coverage problem can be arbitrarily bad for BMOC. We also present a reduction to BMOC from the k-densest subgraph problem that provides evidence indicating that obtaining a constant-factor approximation for our problem might be quite challenging. Nevertheless, experimental runs of the greedy algorithm on the EIN data show that greedy performs remarkably well relative to OPT. We identify a feature of our EIN data, that we call the overlap condition, and show that the greedy algorithm does indeed yield a constant-factor approximation guarantee if the overlap condition is satisfied. Using an implementation of the greedy algorithm for BMOC on the EIN data, we identify small sets of “bellwether” users who are good predictors of important discussions. We provide evidence to show that tracking just these users reduces the cost of monitoring the EIN significantly without causing any important discussions to be missed.

We describe a simple framework, called the transitive closure framework (TCF), for the self-stabilizing construction of any overlay network. The TCF is easy to reason about and algorithms derived from it stabilize within O(log n) more rounds than the optimal. As evidence of the power of this framework, we derive from the TCF a simple, self-stabilizing protocol for constructing Skip + graphs in O(log n) rounds.

We start by defining a pruning process involving sellers on one side and buyers on the other. The goal is to quickly select a subset of the sellers so that the products that these sellers bring to the market has small cost ratio, i.e., the ratio of the total cost of the selected sellers' products to amount that interested buyers are willing to pay. As modeled here, the pruning process can be used to speed up distributed implementations of greedy algorithms (e.g., for minimum dominating set, facility location, etc). We present a randomized instance of the pruning process that, for any positive k, runs in O(k) communication rounds with O(log N)-sized messages, yielding a cost ratio of O(Nc/k). Here N is the product of the number of sellers and number of buyers and c is a small constant. Using this O(k)-round pruning algorithm as the basis, we derive several simple, greedy, O(k)-round distributed approximation algorithms for MDS and facility location (both metric and non-metric versions). Our algorithms achieve optimal approximation ratios in polylogarithmic rounds and shave a "logarithmic factor" off the best, known, approximation factor, typically achieved using LP-rounding techniques.

Greedy routing is a novel routing paradigm where messages are always forwarded to the neighbor that is closest to the destination. Our main result is a polynomial-time algorithm that embeds combinatorial unit disk graphs (CUDGs - a CUDG is a UDG without any geometric information) into O(log2n)- dimensional space, permitting greedy routing with constant stretch. To the best of our knowledge, this is the first greedy embedding with stretch guarantees for this class of networks. Our main technical contribution involves extracting, in polynomial time, a constant number of isometric and balanced tree separators from a given CUDG. We do this by extending the celebrated Lipton-Tarjan separator theorem for planar graphs to CUDGs. Our techniques extend to other classes of graphs; for example, for general graphs, we obtain an O(log n)-stretch greedy embedding into O(log2n)-dimensional space. The greedy embeddings constructed by our algorithm can also be viewed as a constant-stretch compact routing scheme in which each node is assigned an O(log3n)-bit label. To the best of our knowledge, this result yields the best known stretch-space trade-off for compact routing on CUDGs. Extensive simulations on random wireless networks indicate that the average routing overhead is about 10%; only few routes have a stretch above 1.5.

In this paper we present fast, distributed approximation algorithms for the metric facility location problem in the CONGEST model, where message sizes are bounded by O(log N) bits, N being the network size. We first show how to obtain a 7-approximation in O(log m + log n) rounds via the primal-dual method; here m is the number of facilities and n is the number of clients. Subsequently, we generalize this to a k-round algorithm, that for every constant k, yields an approximation factor of O(m2/√k ∙ n3/√k). These results answer a question posed by Moscibroda and Wattenhofer (PODC 2005). Our techniques are based on the primal-dual algorithm due to Jain and Vazirani (JACM 2001) and a rapid randomized sparsification of graphs due to Gfeller and Vicari (PODC 2007). These results complement the results of Moscibroda and Wattenhofer (PODC 2005) for non-metric facility location and extend the results of Gehweiler et al. (SPAA 2006) for uniform metric facility location.

Using a dominating set as a coordinator in wireless networks has been proposed in many papers as an energy conservation technique. Since the nodes in a dominating set have the extra burden of coordination, energy resources in such nodes will drain out more quickly than in other nodes. To maximize the lifetime of nodes in the network,it has been proposed that the role of coordinators be rotated among the nodes in the network. One abstraction that has been considered for the problem of picking a collection of coordinators and cycling through them, is the domatic partition problem. This is the problem of partitioning the set of the nodes of the network into dominating sets with the aim of maximizing the number of dominating sets. In this paper,we consider the k -domatic partition problem. A k -dominating set is a subset D of nodes such that every node in the network is at distance at most k from D. The k-domatic partition problem seeks to partition the network into maximum number of k-dominating sets.We point out that from the point of view of saving energy,it may be better to construct a k-domatic partition for k >1.We present three deterministic, distributed algorithms for finding large k-domatic partitions for k > 1. Each of our algorithms constructs a k-domatic partition of size at least a constant fraction of the largest possible (k 1)-domatic partition. Our first algorithm runs in constant time on unit ball graphs (UBGs) in Euclidean space assuming that all nodes know their positions in a global coordinate system. Our second algorithm drops knowledge of global coordinates and instead assumes that pairwise distances between neighboring nodes are known. This algorithm runs in O(log* n ) time on UBGs in a metric space with constant doubling dimension. Our third algorithm drops all reliance on geometric information, using connectivity information only. This algorithm runs in O(log Δ · log *n) time on growth-bounded graphs. Euclidean UBGs, UBGs in metric spaces with constant doubling dimension, and growth-bounded graphs are successively more general models of wireless networks and all three models include the well-known, but somewhat simplistic wireless network models such as unit disk graphs.

This paper presents a distributed algorithm for wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a lightweight, linear size, (1+ε)-spanner for any given ε> 0. A wireless network is modeled by a d-dimensional α-quasi unit ball graph (α-UBG), which is a higher dimensional generalization of the standard unit disk graph (UDG) model. The d-dimensional α-UBG model goes beyond the unrealistic “flat world ” as-sumption of UDGs and also takes into account transmission errors, fading signal strength, and physical obstructions. The main result in the paper is this: for any fixed ε> 0, 0 < α ≤ 1, and d ≥ 2 there is a distributed algorithm run-ning in O(log n·log ∗ n) communication rounds on an n-node, d-dimensional α-UBG G that computes a (1+ε)-spanner G′ of G with maximum degree Δ(G′) = O(1) and total weight w(G′) = O(w(MST (G)). This result is motivated by the topology control problem in wireless ad-hoc networks and improves on existing topology control algorithms along sev-eral dimensions. The technical contributions of the paper include a new, sequential, greedy algorithm with relaxed edge ordering and lazy updating, and clustering techniques for filtering out unnecessary edges.

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. A d-degenerate graph is a graph G in which every subgraph has a vertex with degree at most d. A star S m with m rays is an example of a 1-degenerate graph with maximum degree m that needs at least 1+m/2 colors for an equitable coloring. Our main result is that every n-vertex d-degenerate graph G with maximum degree at most n/15 can be equitably k-colored for each $k \ge 16d$. The proof of this bound is constructive. We extend the algorithm implied in the proof to an O(d)-factor approximation algorithm for equitable coloring of an arbitraryd -degenerate graph. Among the implications of this result is an O(1)-factor approximation algorithm for equitable coloring of planar graphs with fewest colors. A variation of equitable coloring (equitable partitions) is also discussed.

Locating a center or a median in a graph is a fundamental graph-theoretic problem. Centers and medians are especially important in distributed systems because they are ideal locations for placing resources that need to be shared among different processes in a network. This paper presents simple self-stabilizing algorithms for locating centers and medians of trees. Since these algorithms are self-stabilizing, they can tolerate transient failures. In addition, they can automatically adjust to a dynamically changing tree topology. After the algorithms are presented, their correctness is proven and upper bounds on their time complexity are established. Finally, extensions of our algorithms to trees with arbitrary, positive edge costs are sketched.

Stack layouts and queue layouts of undirected graphs have been used to model problems in fault tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modeled by stack and queue layouts of directed acyclic graphs (dags). A stack layout of a dag is similar to a stack layout of an undirected graph, with the additional requirement that the nodes of the dag be in some topological order. A queue layout is defined in an analogous manner. The stacknumber (queuenumber) of a dag is the smallest number of stacks (queues) required for its stack layout (queue layout). This paper presents algorithmic results---in particular, linear time algorithms for recognizing 1-stack dags and 1-queue dags, and proofs of NP-completeness for the problem of recognizing a 4-queue dag and the problem of recognizing a 6-stack dag. The companion paper (Part I [SIAM J. Comput., 28 (1999), pp. 1510--1539.]) presents combinatorial results.

Stack layouts and queue layouts of undirected graphs have been used to model problems in fault-tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modeled by stack and queue layouts of directed acyclic graphs (dags). A stack layout of a dag is similar to a stack layout of an undirected graph, with the additional requirement that the nodes of the dag be in some topological order. A queue layout is defined in an analogous manner. The stacknumber ( queuenumber) of a dag is the smallest number of stacks (queues) required for its stack layout (queue layout). In this paper, bounds are established on the stacknumber and queuenumber of two classes of dags: tree dags and unicyclic dags. In particular, any tree dag can be laid out in 1 stack and in at most 2 queues; and any unicyclic dag can be laid out in at most 2 stacks and in at most 2 queues. Forbidden subgraph characterizations of 1-queue tree dags and 1-queue cycle dags are also presented. Part II of this paper presents algorithmic results---in particular, linear time algorithms for recognizing 1-stack dags and 1-queue dags and proof of NP-completeness for the problem of recognizing a 4-queue dag and the problem of recognizing a 9-stack dag.

No abstract available.

The stacknumber (queuenumber) of a poset is defined as the stacknumber (queuenumber) of its Hasse diagram viewed as a directed acyclic graph. Upper bounds on the queuenumber of a poset are derived in terms of its jumpnumber, its length, its width, and the queuenumber of its covering graph. A lower bound of $\Omega(\sqrt n)$ is shown for the queuenumber of the class of n-element planar posets. The queuenumber of a planar poset is shown to be within a small constant factor of its width. The stacknumber of n-element posets with planar covering graphs is shown to be $\Theta(n)$. These results exhibit sharp differences between the stacknumber and queuenumber of posets as well as between the stacknumber (queuenumber) of a poset and the stacknumber (queuenumber) of its covering graph.

. Self-stabilization provides a non-masking approach to fault tolerance. Given this fact, one would hope that in a self-stabilizing system, the amount of disruption caused by a fault is proportional to the severity of the fault. However, this is not true for many self-stabilizing systems. Our paper addresses this weakness of distributed self-stabilizing systems by introducing the notion of fault containment. Informally, a fault-containing self-stabilizing algorithm is one that contains the effects of limited transient faults while retaining the property of self-stabilization. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. Then, it is shown that self-stabilization and fault containment are goals that can conflict. For example, it is shown that imposing a O(1) bound on the worst case recovery time from a 1-faulty state necessitates added overhead for stabilization: for some tasks, the O(1) recovery time implies stabiliz...

No abstract available.