PODC ’19- Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing<\/h1>\n![\"Digital](\"https:\/\/dl.acm.org\/img\/dllogo.png\")
Full Citation in the ACM Digital Library<\/a><\/div>\n\nSESSION: Awards<\/h2>\n\u00a0<\/div>\n2019 Edsger W. Dijkstra Prize in Distributed Computing<\/a><\/h3>\n\n- Lorenzo Alvisi<\/li>\n
- Shlomi Dolev<\/li>\n
- Faith Ellen (chair)<\/li>\n
- Idit Keidar<\/li>\n
- Fabian Kuhn<\/li>\n
- Jukka Suomela<\/li>\n<\/ul>\n\n\n
The committee decided to award the 2019 Edsger W. Dijkstra Prize in Distributed Computing to Alessandro Panconesi and Aravind Srinivasan for their paper Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, SIAM Journal on Computing, volume 26, number 2, 1997, pages 350-368. A preliminary version of this paper appeared as Fast Randomized Algorithms for Distributed Edge Coloring, Proceedings of the Eleventh Annual ACM Symposium Principles of Distributed Computing (PODC), 1992, pages 251-262.<\/p>\n
The paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6\u0394 + O(log1+\u03b6<\/sup>n) colors and O(log n) rounds with high probability for any constant \u03b6>0, where n is the number of nodes and is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource allocation.<\/p>\nIn spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff-Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff-Hoeffding bounds to certain random variables they call \u03bb-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.<\/p>\n<\/div>\n<\/div>\n
2019 Principles of Distributed Computing Doctoral Dissertation Award<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Nancy A. Lynch<\/li>\n
- Boaz Patt-Shamir<\/li>\n
- Ulrich Schmid (chair)<\/li>\n<\/ul>\n\n\n
The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi for his dissertation Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation, written under the supervision of Prof. Sanjeev Khanna at the University of Pennsylvania.<\/p>\n
The thesis resolves a number of long-standing problems in the exciting and still relatively new area of sublinear computation. The area of sublinear computation focuses on design of algorithms that use sublinear space, time, or communication to solve global optimization problems on very large datasets. In addition to addressing a wide range of different problems, comprising graph optimization problems (matching, vertex cover, and connectivity), submodular optimization (set cover and maximum coverage), and resource-constrained optimization (combinatorial auctions and learning), these problems are studied in three different models of computation, namely, streaming algorithms, multiparty communication, and massively parallel computation (MPC). The thesis also reveals interesting relations between these different models, including generic algorithmic and analysis techniques that can be applied in all of them.<\/p>\n
For many fundamental optimization problems, the thesis gives asymptotically matching algorithmic and intractability results, completely resolving several long-standing problems. This is accomplished by using a broad spectrum of mathematical methods in very detailed and intricate proofs. In addition to a wide variety of classic techniques, ranging from graph theory, combinatorics, probability, linear algebra and calculus, it also makes heavy use of communication complexity and information theory, for example.<\/p>\n
Sepehr’s dissertation work has been published in a remarkably large number of top-conference papers. It received multiple best paper awards and multiple special issue invitations, as well as two invitations to the Highlights of Algorithms (HALG) conference. Due to its contributions to the field of distributed computing and all the merits mentioned above, the award committee unanimously selected this thesis as the winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award.<\/p>\n<\/div>\n<\/div>\n
SESSION: Keynote Lecture 1<\/h2>\n\u00a0<\/div>\nLocal Computation Algorithms<\/a><\/h3>\n\n- Ronitt Rubinfeld<\/li>\n<\/ul>\n\n\n
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of “local computation algorithms” which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms.<\/p>\n
In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed — we will give special focus to finding maximal independent sets and sparse spanning graphs.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 1<\/h2>\n\u00a0<\/div>\nSymmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes<\/a><\/h3>\n\n- Jurek Czyzowicz<\/li>\n
- Leszek Gasieniec<\/li>\n
- Ryan Killick<\/li>\n
- Evangelos Kranakis<\/li>\n<\/ul>\n\n\n
We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and “measuring instruments” of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.<\/p>\n
We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.<\/p>\n<\/div>\n<\/div>\n
Composable Computation in Discrete Chemical Reaction Networks<\/a><\/h3>\n\n- Eric E. Severson<\/li>\n
- David Haley<\/li>\n
- David Doty<\/li>\n<\/ul>\n\n\n
We study the composability of discrete chemical reaction networks (CRNs) that stably compute (i.e., with probability 0 of error) integer-valued functions \u0192:Nd<\/sup>\u2192 N. We consider output-oblivious CRNs in which the output species is never a reactant (input) to any reaction. The class of output-oblivious CRNs is fundamental, appearing in earlier studies of CRN computation, because it is precisely the class of CRNs that can be composed by simply renaming the output of the upstream CRN to match the input of the downstream CRN.<\/p>\nOur main theorem precisely characterizes the functions f stably computable by output-oblivious CRNs with an initial leader. The key necessary condition is that for sufficiently large inputs, f is the minimum of a finite number of nondecreasing quilt-affine functions. (An affine function is linear with a constant offset; a quilt-affine function is linear with a periodic offset).<\/p>\n<\/div>\n<\/div>\n
How to Spread a Rumor: Call Your Neighbors or Take a Walk?<\/a><\/h3>\n\n- George Giakkoupis<\/li>\n
- Frederik Mallmann-Trenn<\/li>\n
- Hayk Saribekyan<\/li>\n<\/ul>\n\n\n
We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is disseminated by a collection of agents performing independent random walks. In the VISIT-EXCHANGE protocol, both nodes and agents store information, and each time an agent visits a node, the two exchange all the information they have. In the MEET-EXCHANGE protocol, only the agents store information, and exchange their information with each agent they meet.<\/p>\n
We consider the broadcast time of a single piece of information in an n-node graph for the above three protocols, assuming a linear number of agents that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols are significantly faster than PUSH-PULL, and graphs where the converse is true. We attribute the good performance of agent-based algorithms to their inherently fair bandwidth utilization, and conclude that, in certain settings, agent-based information dissemination, separately or in combination with PUSH-PULL, can significantly improve the broadcast time.<\/p>\n
The graphs considered above are highly non-regular. Our main technical result is that on any regular graph of at least logarithmic degree, PUSH-PULL and VISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novel coupling argument which relates the random choices of vertices in PUSH-PULL with the random walks in VISIT-EXCHANGE. Further, we show that the broadcast time of MEET-EXCHANGE is asymptotically at least as large as the other two’s on all regular graphs, and strictly larger on some regular graphs.<\/p>\n
As far as we know, this is the first systematic and thorough comparison of the running times of these very natural information dissemination protocols.<\/p>\n<\/div>\n<\/div>\n
Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols<\/a><\/h3>\n\n- David Doty<\/li>\n
- Mahsa Eftekhari<\/li>\n<\/ul>\n\n\n
We study uniform population protocols: networks of anonymous agents whose pairwise interactions are chosen at random, where each agent uses an identical transition algorithm that does not depend on the population size n. Many existing polylog(n) time protocols for leader election and majority computation are nonuniform: to operate correctly, they require all agents to be initialized with an approximate estimate of n (specifically, the value \u0142floor\u0142og n\\rfloor). Our first main result is a uniform protocol for calculating \u0142og(n) \\pm O(1) with high probability in O(\u0142og^2 n) time and O(\u0142og^4 n) states (O(\u0142og \u0142og n) bits of memory). The protocol is not terminating : it does not signal when the estimate is close to the true value of \u0142og n. If it could be made terminating with high probability, this would allow composition with protocols requiring a size estimate initially. We do show how our main protocol can be indirectly composed with others in a simple and elegant way, based on leaderless phase clocks, demonstrating that those protocols can in fact be made uniform. However, our second main result implies that the protocol cannot be made terminating, a consequence of a much stronger result: a uniform protocol for any task requiring more than constant time cannot be terminating even with probability bounded above 0, if infinitely many initial configurations are dense : any state present initially occupies \u00d8mega(n) agents. (In particular no leader is allowed.) Crucially, the result holds no matter the memory or time permitted.<\/p>\n<\/div>\n<\/div>\n
On Counting the Population Size<\/a><\/h3>\n\n- Petra Berenbrink<\/li>\n
- Dominik Kaaser<\/li>\n
- Tomasz Radzik<\/li>\n<\/ul>\n\n\n
We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using \u00d5 (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.<\/p>\n<\/div>\n<\/div>\n
Self-Stabilizing Leader Election<\/a><\/h3>\n\n- Hsueh-Ping Chen<\/li>\n
- Ho-Lin Chen<\/li>\n<\/ul>\n\n\n
In this paper, we study the self-stabilizing leader election (SSLE) problem in population protocols. We construct a non-deterministic population protocol that can solve SSLE on directed rings of all sizes. Our algorithm uses a constant number of states and can be converted to a deterministic population protocol on undirected rings using previous techniques [8]. Furthermore, we extend our algorithm to perform SSLE on directed and undirected tori of arbitrary sizes.<\/p>\n<\/div>\n<\/div>\n
Logarithmic Expected-Time Leader Election in Population Protocol Model<\/a><\/h3>\n\n- Yuichi Sudo<\/li>\n
- Fukuhito Ooshita<\/li>\n
- Taisuke Izumi<\/li>\n
- Hirotsugu Kakugawa<\/li>\n
- Toshimitsu Masuzawa<\/li>\n<\/ul>\n\n\n
In this paper, we present a leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m \u2265 = log2<\/sub> n and m=O(log n), this protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.<\/p>\n<\/div>\n<\/div>\nOn Site Fidelity and the Price of Ignorance in Swarm Robotic Central Place Foraging Algorithms<\/a><\/h3>\n\n- Abhinav Aggarwal<\/li>\n
- G. Matthew Fricke<\/li>\n
- Diksha Gupta<\/li>\n
- Melanie E. Moses<\/li>\n<\/ul>\n\n\n
A key factor limiting the performance of central place foraging algorithms is the awareness of the agent(s) about the location of food items around the nest. We study the ratio of how much time an ignorant agent takes relative to an omniscient forager for complete collection of food items in the arena. This effectively quantifies the penalty each algorithm pays for not knowing (or choosing to ignore information gained about) where the resources are located. We model the effect of depletion of food items from the arena on the foraging efficiency over time and analytically verify that returning to the location of the last food item found strongly helps in counteracting this effect. To the best of our knowledge, these results have only been empirically argued so far.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 2<\/h2>\n\u00a0<\/div>\nImproved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration<\/a><\/h3>\n\n- Yi-Jun Chang<\/li>\n
- Thatchaphol Saranurak<\/li>\n<\/ul>\n\n\n
An(\u03b5,\u03c6)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1<\/sub>\u222a\u2026\u222a Vx<\/sub> such that (1) each cluster Vi<\/sub> induces subgraph with conductance at least \u03c6, and (2) the number of inter-cluster edges is at most \u03b5|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.<\/p>\nSpecifically, we construct an (\u03b5,\u03c6)-expander decomposition with \u03c6=(\u03b5\/log n)2 O(k)<\/sup> in O(n2\/k<\/sup> \u22c5 poly (1\/\u03c6, log n))rounds for any \u03b5 \u2208(0,1) and positive integer k. For example, a (1\/no(1)<\/sup>, 1\/no(1)<\/sup>)-expander decomposition only requires O(no(1)<\/sup>) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1\/poly log n)-expander decomposition can be computed in O(n\u03b3<\/sup>) rounds, for any arbitrarily small constant \u03b3 > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1\/6,1\/poly log n)-expander decomposition using \u00d5 (n1-\u03b4<\/sup>) rounds for any \u03b4 > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most n\u03b4<\/sup>. Our algorithm does not have this caveat.<\/p>\nBy slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC’17], we obtain a triangle enumeration algorithm using \u00d5(n1\/3<\/sup>) rounds. This matches the lower bound by Izumi and LeGall [PODC’17] and Pandurangan, Robinson and Scquizzato [SPAA’18] of \u00d8(n1\/3<\/sup>) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.<\/p>\nThe key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.<\/p>\n<\/div>\n<\/div>\n
Fast Approximate Shortest Paths in the Congested Clique<\/a><\/h3>\n\n- Keren Censor-Hillel<\/li>\n
- Michal Dory<\/li>\n
- Janne H. Korhonen<\/li>\n
- Dean Leitersdorf<\/li>\n<\/ul>\n\n\n
We design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:<\/p>\n
\n- A (2+\u03b5)-approximation for all-pairs shortest paths problem in O(log2<\/sup>n \/ \u03b5) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.<\/li>\n
- A (1+\u03b5)-approximation for multi-source shortest paths problem from O(\u221an) sources in O(log2<\/sup> n \/ \u03b5) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.<\/li>\n<\/ul>\n
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in \u00d5 (n1\/6<\/sub>) rounds.<\/p>\n<\/div>\n<\/div>\nQuantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model<\/a><\/h3>\n\n- Taisuke Izumi<\/li>\n
- Fran{c c}ois Le Gall<\/li>\n<\/ul>\n\n\n
The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(\u0142og n) bits in synchronous rounds, the best known general algorithm for APSP uses \u00d5(n1\/3<\/sub>) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a \u00d5(n1\/4<\/sub>)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.<\/p>\nOur quantum algorithm is based on a relationship discovered by Vassilevska Williams and Williams (JACM 2018) between the APSP and the detection of negative triangles in a graph. The quantum part of our algorithm exploits the framework for quantum distributed search recently developed by Le Gall and Magniez (PODC 2018). Our main technical contribution is a method showing how to implement multiple quantum searches (one for each edge in the graph) in parallel without introducing congestions.<\/p>\n<\/div>\n<\/div>\n
Deterministic Distributed Dominating Set Approximation in the CONGEST Model<\/a><\/h3>\n\n- Janosch Deurer<\/li>\n
- Fabian Kuhn<\/li>\n
- Yannic Maus<\/li>\n<\/ul>\n\n\n
We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For \u03b5 1\/ poly log \u0394 we obtain two algorithms with approximation factor (1 + \u03b5)(1 + \u0142 n (\u0394 + 1)) and with runtimes 2O<\/sup>(\u221a log n log log n) and O(\u0394 poly log \u0394 + poly log \u0394 log* n), respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic O(log \u0394)-approximation algorithm for the minimum connected dominating set with time complexity 2O(\u221a log n log log n).<\/p>\n<\/div>\n<\/div>\nOptimal Distributed Covering Algorithms<\/a><\/h3>\n\n- Ran Ben Basat<\/li>\n
- Guy Even<\/li>\n
- Ken-ichi Kawarabayashi<\/li>\n
- Gregory Schwartzman<\/li>\n<\/ul>\n\n\n
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank \u0192. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by \u0192. The approximation factor of our algorithm is (\u0192 + \u03b5). Let \u0394 denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log \u0394\/log log \u0394) rounds, for constants \u03b5 \u2208 (0,1] and \u0192 \u2208 N+<\/sup>. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.<\/p>\nFor constant values of \u0192 and \u03b5, our algorithm improves over the (&3402; + \u03b5)-approximation algorithm of [16] whose running time is O(log \u0394 + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an \u0192-approximation for the problem in O(\u0192 log n) rounds, improving over the classical result of [13] that achieves a running time of O(\u0192 log 2<\/sup> n). Finally, for weighted vertex cover (\u0192=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [14].<\/p>\nWe also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (\u0192 + \u03b5)-approximate integral solution in O(1 + \u0192 \/log n)\u22c5 log \u0394 over log log \u0394+(\u0192 \u22c5 log M)1.01<\/sup>\u22c5 log \u03b5-1<\/sup> \u22c5(log \u0394)0.01<\/sup>)) rounds, where \u0192 bounds the number of variables in a constraint, \u0394 bounds the number of constraints a variable appears in, and M=max{1,1\/a min},, amin<\/sub>, where amin<\/sub> is the smallest normalized constraint coefficient. This significantly improves over the results of [16] for the integral case, which achieves the same guarantees in O(\u03b5-4<\/sup> \u22c5 \u01924<\/sup> \u22c5 log \u0192 \u22c5 log(M \u22c5 \u0394)) rounds.<\/p>\n<\/div>\n<\/div>\nSESSION: Session 3<\/h2>\n\u00a0<\/div>\nSecure Distributed Computing Made (Nearly) Optimal<\/a><\/h3>\n\n- Merav Parter<\/li>\n
- Eylon Yogev<\/li>\n<\/ul>\n\n\n
In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes.<\/p>\n
A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees : a collection of n trees T(u1<\/sub>), \u2026, T(un<\/sub>) such that each tree T(ui<\/sub>) spans the neighbors of ui<\/sub> without going through ui<\/sub>. Intuitively, each tree T(ui<\/sub>) allows all neighbors of ui<\/sub> to exchange a secret that is hidden from ui<\/sub>. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d,c)-private neighborhood trees each tree T(ui<\/sub>) has depth O(d) and each edge e \u2208 G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d=O(\u0394 \u2026 D) and c=\u00d5 (D) was presented therein. We make two key contributions:<\/p>\nUniversally Optimal Private Trees:<\/b> We show a combinatorial construction of nearly (universally) optimal (d,c)-private neighborhood trees with d + c=\u00d5 (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees.<\/p>\n
Optimal Secure Computation:<\/b> Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is \u00d5 (poly(\u0394)\u2026 OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely \u00d5 (OPT(G)) per round for a class of “simple” algorithms. This class includes many standard distributed algorithms such as Luby-MIS, the standard logarithmic-round algorithms for matching and \u0394 + 1-coloring, as well as the computation of aggregate functions.<\/p>\n<\/div>\n<\/div>\nWith Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing<\/a><\/h3>\n\n- Avery Miller<\/li>\n
- Boaz Patt-Shamir<\/li>\n
- Will Rosenbaum<\/li>\n<\/ul>\n\n\n
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 \u2264 \u03c1 \u2264 1 and burstiness \u03c3 \u2264 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(\u2113 d1\/\u2113<\/sup> + \u03c3) space suffice, where d is the number of distinct destinations and \u2113=\u230b1\/\u03c1\u230a and we show that \u03a9(1 over \u2113 d1\/\u2113<\/sup> + \u03c3) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d’ + \u03c3 where d’ is the maximum number of destinations on any root-leaf path.<\/p>\n<\/div>\n<\/div>\nPlain SINR is Enough!<\/a><\/h3>\n\n- Magnus M. Halldorsson<\/li>\n
- Tigran Tonoyan<\/li>\n<\/ul>\n\n\n
We develop randomized distributed algorithms for many of the most fundamental communication problems in the wireless SINR model, including (multi-message) broadcast, local broadcast, coloring, MIS, and aggregation. The complexity of the algorithms is optimal up to polylogarithmic preprocessing time. It shows — contrary to expectation — that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and GPS location. A key component of the algorithms is an efficient simulation of CONGEST algorithms on a constant-density SINR backbone.<\/p>\n<\/div>\n<\/div>\n
Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions<\/a><\/h3>\n\n- Ran Gelles<\/li>\n
- Yael Tauman Kalai<\/li>\n
- Govind Ramnarayan<\/li>\n<\/ul>\n\n\n
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate).<\/p>\n
In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel.<\/p>\n
We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most \u03b5 over m fraction of the total communication, where m is the number of links in the network and \u03b5 is a small constant. This scheme assumes an oblivious adversary which is independent of the parties’ inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to \u03b5 over m log m errors.<\/p>\n
While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.<\/p>\n<\/div>\n<\/div>\n
Multiparty Interactive Communication with Private Channels<\/a><\/h3>\n\n- Abhinav Aggarwal<\/li>\n
- Varsha Dani<\/li>\n
- Thomas P. Hayes<\/li>\n
- Jared Saia<\/li>\n<\/ul>\n\n\n
A group of n players wants to run a distributed protocol \u2118 over a network where communication occurs via private point-to-point channels. Can we efficiently simulate \u2118 in the presence of an adversary who knows \u2118 and is able to maliciously flip bits on the channels? We show that this is possible, even when L, the number of bits sent in \u2118, the average message size \u03b1 in \u2118, and T, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of \u2118, \u2118 such that 1) \u2118’ fails with probability at most \u03b4, for any \u03b4>0; and 2) \u2118’ sends O( L (1 + (1\/\u03b1) \u0142og (n L\/\u03b4)) + T) bits. We note that if \u03b1 is \u03a9 (log (n L\/\u03b4), then \u2118 sends only O(L+T) bits, and is therefore within a constant factor of optimal. Critically, our result requires that \u2118 runs correctly in an asynchronous network and our protocol \u2118 must run in a synchronous network.<\/p>\n<\/div>\n<\/div>\n
Coded State Machine — Scaling State Machine Execution under Byzantine Faults<\/a><\/h3>\n\n- Songze Li<\/li>\n
- Saeid Sahraei<\/li>\n
- Mingchao Yu<\/li>\n
- Salman Avestimehr<\/li>\n
- Sreeram Kannan<\/li>\n
- Pramod Viswanath<\/li>\n<\/ul>\n\n\n
We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.<\/p>\n<\/div>\n<\/div>\n
On Termination of a Flooding Process<\/a><\/h3>\n\n- Walter Hussak<\/li>\n
- Amitabh Trehan<\/li>\n<\/ul>\n\n\n
Flooding is a fundamental distributed algorithms technique. Consider the following flooding process, for simplicity, in a synchronous message passing network: A distinguished node begins the flooding process by sending the (same) message to all its neighbours in the first round. In subsequent rounds, every node receiving the message relays a copy of the message further to all those, and only those, nodes it did not receive the message from in the previous round. However, the nodes do not remember if they’ve taken part in the flooding before and therefore will repeat the process every time they get a message. In other words, they execute an amnesiac flooding process with memory only of the present round. The flooding process terminates in a particular round when no edge in the network carries the message in that, and, hence, subsequent, rounds. We call this process Amnesiac Flooding (AF).<\/p>\n
In this work, the main question we address is whether AF will terminate on an arbitrary network (graph) and in what time? We show that, indeed, AF terminates on any arbitrary graph. Further, AF terminates in at most D rounds in bipartite graphs and at most 2D + 1 rounds in non-bipartite graphs – in this brief announcement, we show this for the bipartite case only.<\/p>\n
We also show that in a natural asynchronous variant of AF, an adversary can always ensure non-termination.<\/p>\n<\/div>\n<\/div>\n
SESSION: Keynote Lecture 2<\/h2>\n\u00a0<\/div>\nTowards a Theory of Randomized Shared Memory Algorithms<\/a><\/h3>\n\n- Philipp Woelfel<\/li>\n<\/ul>\n\n\n
Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms.<\/p>\n
For many years, linearizability [6] has been the gold standard of distributed correctness conditions, and the corner stone of modular programming. In deterministic algorithms, implemented linearizable methods can be assumed to be atomic. But when processes can make random choices, the situation is not the same: Probability distributions of outcomes of algorithms using linearizable methods may be very different from those using equivalent atomic operations [4]. In general, modular algorithm design is much more difficult for randomized algorithms than for deterministic ones. The first part of the talk will present a correctness condition [2, 5] that is suitable for randomized algorithms in certain settings, and will explain why in other settings no such correctness condition exists [3] and what we can do about that.<\/p>\n
To this date, almost all randomized shared memory algorithms are Las Vegas, meaning they permit no error. Monte Carlo algorithms, which allow errors to occur with small probability, have been studied thoroughly for sequential systems. But in the shared memory world such algorithms have been neglected. The second part of this talk will discuss recent attempts to devise Monte Carlo algorithms for fundamental shared memory problems (e.g., [1]). It will also present some general techniques, that have proved useful in the design of concurrent randomized algorithms.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 4<\/h2>\n\u00a0<\/div>\nOptimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion<\/a><\/h3>\n\n- Zahra Aghazadeh<\/li>\n
- Damien Imbs<\/li>\n
- Michel Raynal<\/li>\n
- Gadi Taubenfeld<\/li>\n
- Philipp Woelfel<\/li>\n<\/ul>\n\n\n
The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B \u2260 A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y \u2260 X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: \u2200 \u2113: (1) < \u2113 \u2264 n: gcd(\u2113,m)=1). Symmetric means here that,process identities define a specific data type which allows a process to check only if two identities are equal or not.<\/p>\n
The present paper presents two optimal deadlock-free symmetric mutual exclusion algorithms for n-process systems where communication is through m registers. The first algorithm, which considers anonymous read\/write registers, works for any m which is \u2265 n and belongs to the set M(n). It follows that this condition on m is both necessary and sufficient for symmetric deadlock-free mutual exclusion in this anonymity context, and this algorithm is optimal with respect to m The second algorithm, which considers anonymous read\/modify\/write atomic registers, works for any m\u2208 M(n), which is shown to be necessary and sufficient for anonymous read\/modify\/write registers. It follows that, when m > 1, m \u2208 M(n) is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the registers read\/write or read\/modify\/write.<\/p>\n<\/div>\n<\/div>\n
Constant Amortized RMR Abortable Mutex for CC and DSM<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Siddhartha Jayanti<\/li>\n<\/ul>\n\n\n
The Abortable mutual exclusion problem, proposed by Scott and Scherer in response to the needs in real time systems and databases, is a variant of mutual exclusion that allows processes to abort from their attempt to acquire the lock. Worst-case constant remote memory reference (RMR) algorithms for mutual exclusion using hardware instructions such as Fetch&Add or Fetch&Store have long existed for both Cache Coherent (CC) and Distributed Shared Memory (DSM) multiprocessors, but no such algorithms are known for abortable mutual exclusion. Even relaxing the worst-case requirement to amortized, algorithms are only known for the CC model.<\/p>\n
In this paper, we improve this state-of-the-art by designing a deterministic algorithm that uses Fetch&Store (FAS) to achieve amortized O(1) RMR in both the CC and DSM models. Our algorithm supports Fast Abort (a process aborts within six steps of receiving the abort signal), and has the following additional desirable properties: it supports an arbitrary number of processes of arbitrary names, requires only O(1) space per process, and satisfies a novel fairness condition that we call “Airline FCFS”. Our algorithm is short and practical with fewer than a dozen lines of code.<\/p>\n<\/div>\n<\/div>\n
A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Both CC and DSM<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Siddhartha Jayanti<\/li>\n
- Anup Joshi<\/li>\n<\/ul>\n\n\n
In light of recent advances in non-volatile main memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(\u221a log n log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors.<\/p>\n
We answer this question affirmatively by designing an algorithm for a system with n processes, such that, it satisfies the same complexity bound as Golab and Hendler’s for both CC and DSM multiprocessors. Our algorithm has some additional advantages over Golab and Hendler’s: (i) its Exit section is wait-free, (ii) it uses only the Fetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each process to have a cache of only O(1) words, while their algorithm needs a cache of size that is a function of n.<\/p>\n<\/div>\n<\/div>\n
Randomized Concurrent Set Union and Generalized Wake-Up<\/a><\/h3>\n\n- Siddhartha Jayanti<\/li>\n
- Robert E. Tarjan<\/li>\n
- Enric Boix-Adser\u00e0<\/li>\n<\/ul>\n\n\n
We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (\u03b1(n, m\/(np)) + log(np\/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler.<\/p>\n
We use Jayanti’s Wake Up problem and our newly defined Generalized Wake Up problem to prove several lower bounds on concurrent set union. We show an \u03a9(log min {n,p}) expected work lower bound on the cost of any single operation on a set union algorithm. This shows that our single-operation upper bound is optimal across all algorithms when p = n\u03a9(1)<\/sup>. Furthermore, we identify a class of “symmetric algorithms” that captures the complexities of all the known algorithms for the disjoint set union problem, and prove an \u03a9(m\u2022(\u03b1(n, m(np)) + log(np\/m + 1))) expected total work lower bound on algorithms of this class, thereby showing that our algorithm has optimal total work complexity for this class. Finally, we prove that any randomized algorithm, symmetric or not, cannot breach an \u03a9(m \u2022(\u03b1(n, m\/n) + log log(np\/m + 1))) expected total work lower bound.<\/p>\n<\/div>\n<\/div>\nStrongly Linearizable Implementations of Snapshots and Other Types<\/a><\/h3>\n\n- Sean Ovens<\/li>\n
- Philipp Woelfel<\/li>\n<\/ul>\n
SESSION: Awards<\/h2>\n\u00a0<\/div>\n2019 Edsger W. Dijkstra Prize in Distributed Computing<\/a><\/h3>\n\n- Lorenzo Alvisi<\/li>\n
- Shlomi Dolev<\/li>\n
- Faith Ellen (chair)<\/li>\n
- Idit Keidar<\/li>\n
- Fabian Kuhn<\/li>\n
- Jukka Suomela<\/li>\n<\/ul>\n\n\n
The committee decided to award the 2019 Edsger W. Dijkstra Prize in Distributed Computing to Alessandro Panconesi and Aravind Srinivasan for their paper Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, SIAM Journal on Computing, volume 26, number 2, 1997, pages 350-368. A preliminary version of this paper appeared as Fast Randomized Algorithms for Distributed Edge Coloring, Proceedings of the Eleventh Annual ACM Symposium Principles of Distributed Computing (PODC), 1992, pages 251-262.<\/p>\n
The paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6\u0394 + O(log1+\u03b6<\/sup>n) colors and O(log n) rounds with high probability for any constant \u03b6>0, where n is the number of nodes and is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource allocation.<\/p>\nIn spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff-Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff-Hoeffding bounds to certain random variables they call \u03bb-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.<\/p>\n<\/div>\n<\/div>\n
2019 Principles of Distributed Computing Doctoral Dissertation Award<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Nancy A. Lynch<\/li>\n
- Boaz Patt-Shamir<\/li>\n
- Ulrich Schmid (chair)<\/li>\n<\/ul>\n\n\n
The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi for his dissertation Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation, written under the supervision of Prof. Sanjeev Khanna at the University of Pennsylvania.<\/p>\n
The thesis resolves a number of long-standing problems in the exciting and still relatively new area of sublinear computation. The area of sublinear computation focuses on design of algorithms that use sublinear space, time, or communication to solve global optimization problems on very large datasets. In addition to addressing a wide range of different problems, comprising graph optimization problems (matching, vertex cover, and connectivity), submodular optimization (set cover and maximum coverage), and resource-constrained optimization (combinatorial auctions and learning), these problems are studied in three different models of computation, namely, streaming algorithms, multiparty communication, and massively parallel computation (MPC). The thesis also reveals interesting relations between these different models, including generic algorithmic and analysis techniques that can be applied in all of them.<\/p>\n
For many fundamental optimization problems, the thesis gives asymptotically matching algorithmic and intractability results, completely resolving several long-standing problems. This is accomplished by using a broad spectrum of mathematical methods in very detailed and intricate proofs. In addition to a wide variety of classic techniques, ranging from graph theory, combinatorics, probability, linear algebra and calculus, it also makes heavy use of communication complexity and information theory, for example.<\/p>\n
Sepehr’s dissertation work has been published in a remarkably large number of top-conference papers. It received multiple best paper awards and multiple special issue invitations, as well as two invitations to the Highlights of Algorithms (HALG) conference. Due to its contributions to the field of distributed computing and all the merits mentioned above, the award committee unanimously selected this thesis as the winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award.<\/p>\n<\/div>\n<\/div>\n
SESSION: Keynote Lecture 1<\/h2>\n\u00a0<\/div>\nLocal Computation Algorithms<\/a><\/h3>\n\n- Ronitt Rubinfeld<\/li>\n<\/ul>\n\n\n
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of “local computation algorithms” which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms.<\/p>\n
In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed — we will give special focus to finding maximal independent sets and sparse spanning graphs.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 1<\/h2>\n\u00a0<\/div>\nSymmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes<\/a><\/h3>\n\n- Jurek Czyzowicz<\/li>\n
- Leszek Gasieniec<\/li>\n
- Ryan Killick<\/li>\n
- Evangelos Kranakis<\/li>\n<\/ul>\n\n\n
We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and “measuring instruments” of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.<\/p>\n
We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.<\/p>\n<\/div>\n<\/div>\n
Composable Computation in Discrete Chemical Reaction Networks<\/a><\/h3>\n\n- Eric E. Severson<\/li>\n
- David Haley<\/li>\n
- David Doty<\/li>\n<\/ul>\n\n\n
We study the composability of discrete chemical reaction networks (CRNs) that stably compute (i.e., with probability 0 of error) integer-valued functions \u0192:Nd<\/sup>\u2192 N. We consider output-oblivious CRNs in which the output species is never a reactant (input) to any reaction. The class of output-oblivious CRNs is fundamental, appearing in earlier studies of CRN computation, because it is precisely the class of CRNs that can be composed by simply renaming the output of the upstream CRN to match the input of the downstream CRN.<\/p>\nOur main theorem precisely characterizes the functions f stably computable by output-oblivious CRNs with an initial leader. The key necessary condition is that for sufficiently large inputs, f is the minimum of a finite number of nondecreasing quilt-affine functions. (An affine function is linear with a constant offset; a quilt-affine function is linear with a periodic offset).<\/p>\n<\/div>\n<\/div>\n
How to Spread a Rumor: Call Your Neighbors or Take a Walk?<\/a><\/h3>\n\n- George Giakkoupis<\/li>\n
- Frederik Mallmann-Trenn<\/li>\n
- Hayk Saribekyan<\/li>\n<\/ul>\n\n\n
We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is disseminated by a collection of agents performing independent random walks. In the VISIT-EXCHANGE protocol, both nodes and agents store information, and each time an agent visits a node, the two exchange all the information they have. In the MEET-EXCHANGE protocol, only the agents store information, and exchange their information with each agent they meet.<\/p>\n
We consider the broadcast time of a single piece of information in an n-node graph for the above three protocols, assuming a linear number of agents that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols are significantly faster than PUSH-PULL, and graphs where the converse is true. We attribute the good performance of agent-based algorithms to their inherently fair bandwidth utilization, and conclude that, in certain settings, agent-based information dissemination, separately or in combination with PUSH-PULL, can significantly improve the broadcast time.<\/p>\n
The graphs considered above are highly non-regular. Our main technical result is that on any regular graph of at least logarithmic degree, PUSH-PULL and VISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novel coupling argument which relates the random choices of vertices in PUSH-PULL with the random walks in VISIT-EXCHANGE. Further, we show that the broadcast time of MEET-EXCHANGE is asymptotically at least as large as the other two’s on all regular graphs, and strictly larger on some regular graphs.<\/p>\n
As far as we know, this is the first systematic and thorough comparison of the running times of these very natural information dissemination protocols.<\/p>\n<\/div>\n<\/div>\n
Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols<\/a><\/h3>\n\n- David Doty<\/li>\n
- Mahsa Eftekhari<\/li>\n<\/ul>\n\n\n
We study uniform population protocols: networks of anonymous agents whose pairwise interactions are chosen at random, where each agent uses an identical transition algorithm that does not depend on the population size n. Many existing polylog(n) time protocols for leader election and majority computation are nonuniform: to operate correctly, they require all agents to be initialized with an approximate estimate of n (specifically, the value \u0142floor\u0142og n\\rfloor). Our first main result is a uniform protocol for calculating \u0142og(n) \\pm O(1) with high probability in O(\u0142og^2 n) time and O(\u0142og^4 n) states (O(\u0142og \u0142og n) bits of memory). The protocol is not terminating : it does not signal when the estimate is close to the true value of \u0142og n. If it could be made terminating with high probability, this would allow composition with protocols requiring a size estimate initially. We do show how our main protocol can be indirectly composed with others in a simple and elegant way, based on leaderless phase clocks, demonstrating that those protocols can in fact be made uniform. However, our second main result implies that the protocol cannot be made terminating, a consequence of a much stronger result: a uniform protocol for any task requiring more than constant time cannot be terminating even with probability bounded above 0, if infinitely many initial configurations are dense : any state present initially occupies \u00d8mega(n) agents. (In particular no leader is allowed.) Crucially, the result holds no matter the memory or time permitted.<\/p>\n<\/div>\n<\/div>\n
On Counting the Population Size<\/a><\/h3>\n\n- Petra Berenbrink<\/li>\n
- Dominik Kaaser<\/li>\n
- Tomasz Radzik<\/li>\n<\/ul>\n\n\n
We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using \u00d5 (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.<\/p>\n<\/div>\n<\/div>\n
Self-Stabilizing Leader Election<\/a><\/h3>\n\n- Hsueh-Ping Chen<\/li>\n
- Ho-Lin Chen<\/li>\n<\/ul>\n\n\n
In this paper, we study the self-stabilizing leader election (SSLE) problem in population protocols. We construct a non-deterministic population protocol that can solve SSLE on directed rings of all sizes. Our algorithm uses a constant number of states and can be converted to a deterministic population protocol on undirected rings using previous techniques [8]. Furthermore, we extend our algorithm to perform SSLE on directed and undirected tori of arbitrary sizes.<\/p>\n<\/div>\n<\/div>\n
Logarithmic Expected-Time Leader Election in Population Protocol Model<\/a><\/h3>\n\n- Yuichi Sudo<\/li>\n
- Fukuhito Ooshita<\/li>\n
- Taisuke Izumi<\/li>\n
- Hirotsugu Kakugawa<\/li>\n
- Toshimitsu Masuzawa<\/li>\n<\/ul>\n\n\n
In this paper, we present a leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m \u2265 = log2<\/sub> n and m=O(log n), this protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.<\/p>\n<\/div>\n<\/div>\nOn Site Fidelity and the Price of Ignorance in Swarm Robotic Central Place Foraging Algorithms<\/a><\/h3>\n\n- Abhinav Aggarwal<\/li>\n
- G. Matthew Fricke<\/li>\n
- Diksha Gupta<\/li>\n
- Melanie E. Moses<\/li>\n<\/ul>\n\n\n
A key factor limiting the performance of central place foraging algorithms is the awareness of the agent(s) about the location of food items around the nest. We study the ratio of how much time an ignorant agent takes relative to an omniscient forager for complete collection of food items in the arena. This effectively quantifies the penalty each algorithm pays for not knowing (or choosing to ignore information gained about) where the resources are located. We model the effect of depletion of food items from the arena on the foraging efficiency over time and analytically verify that returning to the location of the last food item found strongly helps in counteracting this effect. To the best of our knowledge, these results have only been empirically argued so far.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 2<\/h2>\n\u00a0<\/div>\nImproved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration<\/a><\/h3>\n\n- Yi-Jun Chang<\/li>\n
- Thatchaphol Saranurak<\/li>\n<\/ul>\n\n\n
An(\u03b5,\u03c6)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1<\/sub>\u222a\u2026\u222a Vx<\/sub> such that (1) each cluster Vi<\/sub> induces subgraph with conductance at least \u03c6, and (2) the number of inter-cluster edges is at most \u03b5|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.<\/p>\nSpecifically, we construct an (\u03b5,\u03c6)-expander decomposition with \u03c6=(\u03b5\/log n)2 O(k)<\/sup> in O(n2\/k<\/sup> \u22c5 poly (1\/\u03c6, log n))rounds for any \u03b5 \u2208(0,1) and positive integer k. For example, a (1\/no(1)<\/sup>, 1\/no(1)<\/sup>)-expander decomposition only requires O(no(1)<\/sup>) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1\/poly log n)-expander decomposition can be computed in O(n\u03b3<\/sup>) rounds, for any arbitrarily small constant \u03b3 > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1\/6,1\/poly log n)-expander decomposition using \u00d5 (n1-\u03b4<\/sup>) rounds for any \u03b4 > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most n\u03b4<\/sup>. Our algorithm does not have this caveat.<\/p>\nBy slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC’17], we obtain a triangle enumeration algorithm using \u00d5(n1\/3<\/sup>) rounds. This matches the lower bound by Izumi and LeGall [PODC’17] and Pandurangan, Robinson and Scquizzato [SPAA’18] of \u00d8(n1\/3<\/sup>) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.<\/p>\nThe key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.<\/p>\n<\/div>\n<\/div>\n
Fast Approximate Shortest Paths in the Congested Clique<\/a><\/h3>\n\n- Keren Censor-Hillel<\/li>\n
- Michal Dory<\/li>\n
- Janne H. Korhonen<\/li>\n
- Dean Leitersdorf<\/li>\n<\/ul>\n\n\n
We design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:<\/p>\n
\n- A (2+\u03b5)-approximation for all-pairs shortest paths problem in O(log2<\/sup>n \/ \u03b5) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.<\/li>\n
- A (1+\u03b5)-approximation for multi-source shortest paths problem from O(\u221an) sources in O(log2<\/sup> n \/ \u03b5) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.<\/li>\n<\/ul>\n
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in \u00d5 (n1\/6<\/sub>) rounds.<\/p>\n<\/div>\n<\/div>\nQuantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model<\/a><\/h3>\n\n- Taisuke Izumi<\/li>\n
- Fran{c c}ois Le Gall<\/li>\n<\/ul>\n\n\n
The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(\u0142og n) bits in synchronous rounds, the best known general algorithm for APSP uses \u00d5(n1\/3<\/sub>) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a \u00d5(n1\/4<\/sub>)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.<\/p>\nOur quantum algorithm is based on a relationship discovered by Vassilevska Williams and Williams (JACM 2018) between the APSP and the detection of negative triangles in a graph. The quantum part of our algorithm exploits the framework for quantum distributed search recently developed by Le Gall and Magniez (PODC 2018). Our main technical contribution is a method showing how to implement multiple quantum searches (one for each edge in the graph) in parallel without introducing congestions.<\/p>\n<\/div>\n<\/div>\n
Deterministic Distributed Dominating Set Approximation in the CONGEST Model<\/a><\/h3>\n\n- Janosch Deurer<\/li>\n
- Fabian Kuhn<\/li>\n
- Yannic Maus<\/li>\n<\/ul>\n\n\n
We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For \u03b5 1\/ poly log \u0394 we obtain two algorithms with approximation factor (1 + \u03b5)(1 + \u0142 n (\u0394 + 1)) and with runtimes 2O<\/sup>(\u221a log n log log n) and O(\u0394 poly log \u0394 + poly log \u0394 log* n), respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic O(log \u0394)-approximation algorithm for the minimum connected dominating set with time complexity 2O(\u221a log n log log n).<\/p>\n<\/div>\n<\/div>\nOptimal Distributed Covering Algorithms<\/a><\/h3>\n\n- Ran Ben Basat<\/li>\n
- Guy Even<\/li>\n
- Ken-ichi Kawarabayashi<\/li>\n
- Gregory Schwartzman<\/li>\n<\/ul>\n\n\n
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank \u0192. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by \u0192. The approximation factor of our algorithm is (\u0192 + \u03b5). Let \u0394 denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log \u0394\/log log \u0394) rounds, for constants \u03b5 \u2208 (0,1] and \u0192 \u2208 N+<\/sup>. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.<\/p>\nFor constant values of \u0192 and \u03b5, our algorithm improves over the (&3402; + \u03b5)-approximation algorithm of [16] whose running time is O(log \u0394 + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an \u0192-approximation for the problem in O(\u0192 log n) rounds, improving over the classical result of [13] that achieves a running time of O(\u0192 log 2<\/sup> n). Finally, for weighted vertex cover (\u0192=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [14].<\/p>\nWe also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (\u0192 + \u03b5)-approximate integral solution in O(1 + \u0192 \/log n)\u22c5 log \u0394 over log log \u0394+(\u0192 \u22c5 log M)1.01<\/sup>\u22c5 log \u03b5-1<\/sup> \u22c5(log \u0394)0.01<\/sup>)) rounds, where \u0192 bounds the number of variables in a constraint, \u0394 bounds the number of constraints a variable appears in, and M=max{1,1\/a min},, amin<\/sub>, where amin<\/sub> is the smallest normalized constraint coefficient. This significantly improves over the results of [16] for the integral case, which achieves the same guarantees in O(\u03b5-4<\/sup> \u22c5 \u01924<\/sup> \u22c5 log \u0192 \u22c5 log(M \u22c5 \u0394)) rounds.<\/p>\n<\/div>\n<\/div>\nSESSION: Session 3<\/h2>\n\u00a0<\/div>\nSecure Distributed Computing Made (Nearly) Optimal<\/a><\/h3>\n\n- Merav Parter<\/li>\n
- Eylon Yogev<\/li>\n<\/ul>\n\n\n
In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes.<\/p>\n
A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees : a collection of n trees T(u1<\/sub>), \u2026, T(un<\/sub>) such that each tree T(ui<\/sub>) spans the neighbors of ui<\/sub> without going through ui<\/sub>. Intuitively, each tree T(ui<\/sub>) allows all neighbors of ui<\/sub> to exchange a secret that is hidden from ui<\/sub>. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d,c)-private neighborhood trees each tree T(ui<\/sub>) has depth O(d) and each edge e \u2208 G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d=O(\u0394 \u2026 D) and c=\u00d5 (D) was presented therein. We make two key contributions:<\/p>\nUniversally Optimal Private Trees:<\/b> We show a combinatorial construction of nearly (universally) optimal (d,c)-private neighborhood trees with d + c=\u00d5 (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees.<\/p>\n
Optimal Secure Computation:<\/b> Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is \u00d5 (poly(\u0394)\u2026 OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely \u00d5 (OPT(G)) per round for a class of “simple” algorithms. This class includes many standard distributed algorithms such as Luby-MIS, the standard logarithmic-round algorithms for matching and \u0394 + 1-coloring, as well as the computation of aggregate functions.<\/p>\n<\/div>\n<\/div>\nWith Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing<\/a><\/h3>\n\n- Avery Miller<\/li>\n
- Boaz Patt-Shamir<\/li>\n
- Will Rosenbaum<\/li>\n<\/ul>\n\n\n
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 \u2264 \u03c1 \u2264 1 and burstiness \u03c3 \u2264 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(\u2113 d1\/\u2113<\/sup> + \u03c3) space suffice, where d is the number of distinct destinations and \u2113=\u230b1\/\u03c1\u230a and we show that \u03a9(1 over \u2113 d1\/\u2113<\/sup> + \u03c3) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d’ + \u03c3 where d’ is the maximum number of destinations on any root-leaf path.<\/p>\n<\/div>\n<\/div>\nPlain SINR is Enough!<\/a><\/h3>\n\n- Magnus M. Halldorsson<\/li>\n
- Tigran Tonoyan<\/li>\n<\/ul>\n\n\n
We develop randomized distributed algorithms for many of the most fundamental communication problems in the wireless SINR model, including (multi-message) broadcast, local broadcast, coloring, MIS, and aggregation. The complexity of the algorithms is optimal up to polylogarithmic preprocessing time. It shows — contrary to expectation — that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and GPS location. A key component of the algorithms is an efficient simulation of CONGEST algorithms on a constant-density SINR backbone.<\/p>\n<\/div>\n<\/div>\n
Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions<\/a><\/h3>\n\n- Ran Gelles<\/li>\n
- Yael Tauman Kalai<\/li>\n
- Govind Ramnarayan<\/li>\n<\/ul>\n\n\n
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate).<\/p>\n
In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel.<\/p>\n
We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most \u03b5 over m fraction of the total communication, where m is the number of links in the network and \u03b5 is a small constant. This scheme assumes an oblivious adversary which is independent of the parties’ inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to \u03b5 over m log m errors.<\/p>\n
While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.<\/p>\n<\/div>\n<\/div>\n
Multiparty Interactive Communication with Private Channels<\/a><\/h3>\n\n- Abhinav Aggarwal<\/li>\n
- Varsha Dani<\/li>\n
- Thomas P. Hayes<\/li>\n
- Jared Saia<\/li>\n<\/ul>\n\n\n
A group of n players wants to run a distributed protocol \u2118 over a network where communication occurs via private point-to-point channels. Can we efficiently simulate \u2118 in the presence of an adversary who knows \u2118 and is able to maliciously flip bits on the channels? We show that this is possible, even when L, the number of bits sent in \u2118, the average message size \u03b1 in \u2118, and T, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of \u2118, \u2118 such that 1) \u2118’ fails with probability at most \u03b4, for any \u03b4>0; and 2) \u2118’ sends O( L (1 + (1\/\u03b1) \u0142og (n L\/\u03b4)) + T) bits. We note that if \u03b1 is \u03a9 (log (n L\/\u03b4), then \u2118 sends only O(L+T) bits, and is therefore within a constant factor of optimal. Critically, our result requires that \u2118 runs correctly in an asynchronous network and our protocol \u2118 must run in a synchronous network.<\/p>\n<\/div>\n<\/div>\n
Coded State Machine — Scaling State Machine Execution under Byzantine Faults<\/a><\/h3>\n\n- Songze Li<\/li>\n
- Saeid Sahraei<\/li>\n
- Mingchao Yu<\/li>\n
- Salman Avestimehr<\/li>\n
- Sreeram Kannan<\/li>\n
- Pramod Viswanath<\/li>\n<\/ul>\n\n\n
We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.<\/p>\n<\/div>\n<\/div>\n
On Termination of a Flooding Process<\/a><\/h3>\n\n- Walter Hussak<\/li>\n
- Amitabh Trehan<\/li>\n<\/ul>\n\n\n
Flooding is a fundamental distributed algorithms technique. Consider the following flooding process, for simplicity, in a synchronous message passing network: A distinguished node begins the flooding process by sending the (same) message to all its neighbours in the first round. In subsequent rounds, every node receiving the message relays a copy of the message further to all those, and only those, nodes it did not receive the message from in the previous round. However, the nodes do not remember if they’ve taken part in the flooding before and therefore will repeat the process every time they get a message. In other words, they execute an amnesiac flooding process with memory only of the present round. The flooding process terminates in a particular round when no edge in the network carries the message in that, and, hence, subsequent, rounds. We call this process Amnesiac Flooding (AF).<\/p>\n
In this work, the main question we address is whether AF will terminate on an arbitrary network (graph) and in what time? We show that, indeed, AF terminates on any arbitrary graph. Further, AF terminates in at most D rounds in bipartite graphs and at most 2D + 1 rounds in non-bipartite graphs – in this brief announcement, we show this for the bipartite case only.<\/p>\n
We also show that in a natural asynchronous variant of AF, an adversary can always ensure non-termination.<\/p>\n<\/div>\n<\/div>\n
SESSION: Keynote Lecture 2<\/h2>\n\u00a0<\/div>\nTowards a Theory of Randomized Shared Memory Algorithms<\/a><\/h3>\n\n- Philipp Woelfel<\/li>\n<\/ul>\n\n\n
Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms.<\/p>\n
For many years, linearizability [6] has been the gold standard of distributed correctness conditions, and the corner stone of modular programming. In deterministic algorithms, implemented linearizable methods can be assumed to be atomic. But when processes can make random choices, the situation is not the same: Probability distributions of outcomes of algorithms using linearizable methods may be very different from those using equivalent atomic operations [4]. In general, modular algorithm design is much more difficult for randomized algorithms than for deterministic ones. The first part of the talk will present a correctness condition [2, 5] that is suitable for randomized algorithms in certain settings, and will explain why in other settings no such correctness condition exists [3] and what we can do about that.<\/p>\n
To this date, almost all randomized shared memory algorithms are Las Vegas, meaning they permit no error. Monte Carlo algorithms, which allow errors to occur with small probability, have been studied thoroughly for sequential systems. But in the shared memory world such algorithms have been neglected. The second part of this talk will discuss recent attempts to devise Monte Carlo algorithms for fundamental shared memory problems (e.g., [1]). It will also present some general techniques, that have proved useful in the design of concurrent randomized algorithms.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 4<\/h2>\n\u00a0<\/div>\nOptimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion<\/a><\/h3>\n\n- Zahra Aghazadeh<\/li>\n
- Damien Imbs<\/li>\n
- Michel Raynal<\/li>\n
- Gadi Taubenfeld<\/li>\n
- Philipp Woelfel<\/li>\n<\/ul>\n\n\n
The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B \u2260 A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y \u2260 X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: \u2200 \u2113: (1) < \u2113 \u2264 n: gcd(\u2113,m)=1). Symmetric means here that,process identities define a specific data type which allows a process to check only if two identities are equal or not.<\/p>\n
The present paper presents two optimal deadlock-free symmetric mutual exclusion algorithms for n-process systems where communication is through m registers. The first algorithm, which considers anonymous read\/write registers, works for any m which is \u2265 n and belongs to the set M(n). It follows that this condition on m is both necessary and sufficient for symmetric deadlock-free mutual exclusion in this anonymity context, and this algorithm is optimal with respect to m The second algorithm, which considers anonymous read\/modify\/write atomic registers, works for any m\u2208 M(n), which is shown to be necessary and sufficient for anonymous read\/modify\/write registers. It follows that, when m > 1, m \u2208 M(n) is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the registers read\/write or read\/modify\/write.<\/p>\n<\/div>\n<\/div>\n
Constant Amortized RMR Abortable Mutex for CC and DSM<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Siddhartha Jayanti<\/li>\n<\/ul>\n\n\n
The Abortable mutual exclusion problem, proposed by Scott and Scherer in response to the needs in real time systems and databases, is a variant of mutual exclusion that allows processes to abort from their attempt to acquire the lock. Worst-case constant remote memory reference (RMR) algorithms for mutual exclusion using hardware instructions such as Fetch&Add or Fetch&Store have long existed for both Cache Coherent (CC) and Distributed Shared Memory (DSM) multiprocessors, but no such algorithms are known for abortable mutual exclusion. Even relaxing the worst-case requirement to amortized, algorithms are only known for the CC model.<\/p>\n
In this paper, we improve this state-of-the-art by designing a deterministic algorithm that uses Fetch&Store (FAS) to achieve amortized O(1) RMR in both the CC and DSM models. Our algorithm supports Fast Abort (a process aborts within six steps of receiving the abort signal), and has the following additional desirable properties: it supports an arbitrary number of processes of arbitrary names, requires only O(1) space per process, and satisfies a novel fairness condition that we call “Airline FCFS”. Our algorithm is short and practical with fewer than a dozen lines of code.<\/p>\n<\/div>\n<\/div>\n
A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Both CC and DSM<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Siddhartha Jayanti<\/li>\n
- Anup Joshi<\/li>\n<\/ul>\n\n\n
In light of recent advances in non-volatile main memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(\u221a log n log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors.<\/p>\n
We answer this question affirmatively by designing an algorithm for a system with n processes, such that, it satisfies the same complexity bound as Golab and Hendler’s for both CC and DSM multiprocessors. Our algorithm has some additional advantages over Golab and Hendler’s: (i) its Exit section is wait-free, (ii) it uses only the Fetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each process to have a cache of only O(1) words, while their algorithm needs a cache of size that is a function of n.<\/p>\n<\/div>\n<\/div>\n
Randomized Concurrent Set Union and Generalized Wake-Up<\/a><\/h3>\n\n- Siddhartha Jayanti<\/li>\n
- Robert E. Tarjan<\/li>\n
- Enric Boix-Adser\u00e0<\/li>\n<\/ul>\n\n\n
We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (\u03b1(n, m\/(np)) + log(np\/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler.<\/p>\n
We use Jayanti’s Wake Up problem and our newly defined Generalized Wake Up problem to prove several lower bounds on concurrent set union. We show an \u03a9(log min {n,p}) expected work lower bound on the cost of any single operation on a set union algorithm. This shows that our single-operation upper bound is optimal across all algorithms when p = n\u03a9(1)<\/sup>. Furthermore, we identify a class of “symmetric algorithms” that captures the complexities of all the known algorithms for the disjoint set union problem, and prove an \u03a9(m\u2022(\u03b1(n, m(np)) + log(np\/m + 1))) expected total work lower bound on algorithms of this class, thereby showing that our algorithm has optimal total work complexity for this class. Finally, we prove that any randomized algorithm, symmetric or not, cannot breach an \u03a9(m \u2022(\u03b1(n, m\/n) + log log(np\/m + 1))) expected total work lower bound.<\/p>\n<\/div>\n<\/div>\nStrongly Linearizable Implementations of Snapshots and Other Types<\/a><\/h3>\n\n- Sean Ovens<\/li>\n
- Philipp Woelfel<\/li>\n<\/ul>\n
2019 Edsger W. Dijkstra Prize in Distributed Computing<\/a><\/h3>\n\n- Lorenzo Alvisi<\/li>\n
- Shlomi Dolev<\/li>\n
- Faith Ellen (chair)<\/li>\n
- Idit Keidar<\/li>\n
- Fabian Kuhn<\/li>\n
- Jukka Suomela<\/li>\n<\/ul>\n\n\n
The committee decided to award the 2019 Edsger W. Dijkstra Prize in Distributed Computing to Alessandro Panconesi and Aravind Srinivasan for their paper Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, SIAM Journal on Computing, volume 26, number 2, 1997, pages 350-368. A preliminary version of this paper appeared as Fast Randomized Algorithms for Distributed Edge Coloring, Proceedings of the Eleventh Annual ACM Symposium Principles of Distributed Computing (PODC), 1992, pages 251-262.<\/p>\n
The paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6\u0394 + O(log1+\u03b6<\/sup>n) colors and O(log n) rounds with high probability for any constant \u03b6>0, where n is the number of nodes and is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource allocation.<\/p>\nIn spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff-Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff-Hoeffding bounds to certain random variables they call \u03bb-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.<\/p>\n<\/div>\n<\/div>\n
2019 Principles of Distributed Computing Doctoral Dissertation Award<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Nancy A. Lynch<\/li>\n
- Boaz Patt-Shamir<\/li>\n
- Ulrich Schmid (chair)<\/li>\n<\/ul>\n\n\n
The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi for his dissertation Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation, written under the supervision of Prof. Sanjeev Khanna at the University of Pennsylvania.<\/p>\n
The thesis resolves a number of long-standing problems in the exciting and still relatively new area of sublinear computation. The area of sublinear computation focuses on design of algorithms that use sublinear space, time, or communication to solve global optimization problems on very large datasets. In addition to addressing a wide range of different problems, comprising graph optimization problems (matching, vertex cover, and connectivity), submodular optimization (set cover and maximum coverage), and resource-constrained optimization (combinatorial auctions and learning), these problems are studied in three different models of computation, namely, streaming algorithms, multiparty communication, and massively parallel computation (MPC). The thesis also reveals interesting relations between these different models, including generic algorithmic and analysis techniques that can be applied in all of them.<\/p>\n
For many fundamental optimization problems, the thesis gives asymptotically matching algorithmic and intractability results, completely resolving several long-standing problems. This is accomplished by using a broad spectrum of mathematical methods in very detailed and intricate proofs. In addition to a wide variety of classic techniques, ranging from graph theory, combinatorics, probability, linear algebra and calculus, it also makes heavy use of communication complexity and information theory, for example.<\/p>\n
Sepehr’s dissertation work has been published in a remarkably large number of top-conference papers. It received multiple best paper awards and multiple special issue invitations, as well as two invitations to the Highlights of Algorithms (HALG) conference. Due to its contributions to the field of distributed computing and all the merits mentioned above, the award committee unanimously selected this thesis as the winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award.<\/p>\n<\/div>\n<\/div>\n
SESSION: Keynote Lecture 1<\/h2>\n\u00a0<\/div>\nLocal Computation Algorithms<\/a><\/h3>\n\n- Ronitt Rubinfeld<\/li>\n<\/ul>\n\n\n
Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of “local computation algorithms” which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms.<\/p>\n
In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed — we will give special focus to finding maximal independent sets and sparse spanning graphs.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 1<\/h2>\n\u00a0<\/div>\nSymmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes<\/a><\/h3>\n\n- Jurek Czyzowicz<\/li>\n
- Leszek Gasieniec<\/li>\n
- Ryan Killick<\/li>\n
- Evangelos Kranakis<\/li>\n<\/ul>\n\n\n
We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and “measuring instruments” of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.<\/p>\n
We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.<\/p>\n<\/div>\n<\/div>\n
Composable Computation in Discrete Chemical Reaction Networks<\/a><\/h3>\n\n- Eric E. Severson<\/li>\n
- David Haley<\/li>\n
- David Doty<\/li>\n<\/ul>\n\n\n
We study the composability of discrete chemical reaction networks (CRNs) that stably compute (i.e., with probability 0 of error) integer-valued functions \u0192:Nd<\/sup>\u2192 N. We consider output-oblivious CRNs in which the output species is never a reactant (input) to any reaction. The class of output-oblivious CRNs is fundamental, appearing in earlier studies of CRN computation, because it is precisely the class of CRNs that can be composed by simply renaming the output of the upstream CRN to match the input of the downstream CRN.<\/p>\nOur main theorem precisely characterizes the functions f stably computable by output-oblivious CRNs with an initial leader. The key necessary condition is that for sufficiently large inputs, f is the minimum of a finite number of nondecreasing quilt-affine functions. (An affine function is linear with a constant offset; a quilt-affine function is linear with a periodic offset).<\/p>\n<\/div>\n<\/div>\n
How to Spread a Rumor: Call Your Neighbors or Take a Walk?<\/a><\/h3>\n\n- George Giakkoupis<\/li>\n
- Frederik Mallmann-Trenn<\/li>\n
- Hayk Saribekyan<\/li>\n<\/ul>\n\n\n
We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is disseminated by a collection of agents performing independent random walks. In the VISIT-EXCHANGE protocol, both nodes and agents store information, and each time an agent visits a node, the two exchange all the information they have. In the MEET-EXCHANGE protocol, only the agents store information, and exchange their information with each agent they meet.<\/p>\n
We consider the broadcast time of a single piece of information in an n-node graph for the above three protocols, assuming a linear number of agents that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols are significantly faster than PUSH-PULL, and graphs where the converse is true. We attribute the good performance of agent-based algorithms to their inherently fair bandwidth utilization, and conclude that, in certain settings, agent-based information dissemination, separately or in combination with PUSH-PULL, can significantly improve the broadcast time.<\/p>\n
The graphs considered above are highly non-regular. Our main technical result is that on any regular graph of at least logarithmic degree, PUSH-PULL and VISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novel coupling argument which relates the random choices of vertices in PUSH-PULL with the random walks in VISIT-EXCHANGE. Further, we show that the broadcast time of MEET-EXCHANGE is asymptotically at least as large as the other two’s on all regular graphs, and strictly larger on some regular graphs.<\/p>\n
As far as we know, this is the first systematic and thorough comparison of the running times of these very natural information dissemination protocols.<\/p>\n<\/div>\n<\/div>\n
Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols<\/a><\/h3>\n\n- David Doty<\/li>\n
- Mahsa Eftekhari<\/li>\n<\/ul>\n\n\n
We study uniform population protocols: networks of anonymous agents whose pairwise interactions are chosen at random, where each agent uses an identical transition algorithm that does not depend on the population size n. Many existing polylog(n) time protocols for leader election and majority computation are nonuniform: to operate correctly, they require all agents to be initialized with an approximate estimate of n (specifically, the value \u0142floor\u0142og n\\rfloor). Our first main result is a uniform protocol for calculating \u0142og(n) \\pm O(1) with high probability in O(\u0142og^2 n) time and O(\u0142og^4 n) states (O(\u0142og \u0142og n) bits of memory). The protocol is not terminating : it does not signal when the estimate is close to the true value of \u0142og n. If it could be made terminating with high probability, this would allow composition with protocols requiring a size estimate initially. We do show how our main protocol can be indirectly composed with others in a simple and elegant way, based on leaderless phase clocks, demonstrating that those protocols can in fact be made uniform. However, our second main result implies that the protocol cannot be made terminating, a consequence of a much stronger result: a uniform protocol for any task requiring more than constant time cannot be terminating even with probability bounded above 0, if infinitely many initial configurations are dense : any state present initially occupies \u00d8mega(n) agents. (In particular no leader is allowed.) Crucially, the result holds no matter the memory or time permitted.<\/p>\n<\/div>\n<\/div>\n
On Counting the Population Size<\/a><\/h3>\n\n- Petra Berenbrink<\/li>\n
- Dominik Kaaser<\/li>\n
- Tomasz Radzik<\/li>\n<\/ul>\n\n\n
We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using \u00d5 (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.<\/p>\n<\/div>\n<\/div>\n
Self-Stabilizing Leader Election<\/a><\/h3>\n\n- Hsueh-Ping Chen<\/li>\n
- Ho-Lin Chen<\/li>\n<\/ul>\n\n\n
In this paper, we study the self-stabilizing leader election (SSLE) problem in population protocols. We construct a non-deterministic population protocol that can solve SSLE on directed rings of all sizes. Our algorithm uses a constant number of states and can be converted to a deterministic population protocol on undirected rings using previous techniques [8]. Furthermore, we extend our algorithm to perform SSLE on directed and undirected tori of arbitrary sizes.<\/p>\n<\/div>\n<\/div>\n
Logarithmic Expected-Time Leader Election in Population Protocol Model<\/a><\/h3>\n\n- Yuichi Sudo<\/li>\n
- Fukuhito Ooshita<\/li>\n
- Taisuke Izumi<\/li>\n
- Hirotsugu Kakugawa<\/li>\n
- Toshimitsu Masuzawa<\/li>\n<\/ul>\n\n\n
In this paper, we present a leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m \u2265 = log2<\/sub> n and m=O(log n), this protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.<\/p>\n<\/div>\n<\/div>\nOn Site Fidelity and the Price of Ignorance in Swarm Robotic Central Place Foraging Algorithms<\/a><\/h3>\n\n- Abhinav Aggarwal<\/li>\n
- G. Matthew Fricke<\/li>\n
- Diksha Gupta<\/li>\n
- Melanie E. Moses<\/li>\n<\/ul>\n\n\n
A key factor limiting the performance of central place foraging algorithms is the awareness of the agent(s) about the location of food items around the nest. We study the ratio of how much time an ignorant agent takes relative to an omniscient forager for complete collection of food items in the arena. This effectively quantifies the penalty each algorithm pays for not knowing (or choosing to ignore information gained about) where the resources are located. We model the effect of depletion of food items from the arena on the foraging efficiency over time and analytically verify that returning to the location of the last food item found strongly helps in counteracting this effect. To the best of our knowledge, these results have only been empirically argued so far.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 2<\/h2>\n\u00a0<\/div>\nImproved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration<\/a><\/h3>\n\n- Yi-Jun Chang<\/li>\n
- Thatchaphol Saranurak<\/li>\n<\/ul>\n\n\n
An(\u03b5,\u03c6)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1<\/sub>\u222a\u2026\u222a Vx<\/sub> such that (1) each cluster Vi<\/sub> induces subgraph with conductance at least \u03c6, and (2) the number of inter-cluster edges is at most \u03b5|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.<\/p>\nSpecifically, we construct an (\u03b5,\u03c6)-expander decomposition with \u03c6=(\u03b5\/log n)2 O(k)<\/sup> in O(n2\/k<\/sup> \u22c5 poly (1\/\u03c6, log n))rounds for any \u03b5 \u2208(0,1) and positive integer k. For example, a (1\/no(1)<\/sup>, 1\/no(1)<\/sup>)-expander decomposition only requires O(no(1)<\/sup>) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1\/poly log n)-expander decomposition can be computed in O(n\u03b3<\/sup>) rounds, for any arbitrarily small constant \u03b3 > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1\/6,1\/poly log n)-expander decomposition using \u00d5 (n1-\u03b4<\/sup>) rounds for any \u03b4 > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most n\u03b4<\/sup>. Our algorithm does not have this caveat.<\/p>\nBy slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC’17], we obtain a triangle enumeration algorithm using \u00d5(n1\/3<\/sup>) rounds. This matches the lower bound by Izumi and LeGall [PODC’17] and Pandurangan, Robinson and Scquizzato [SPAA’18] of \u00d8(n1\/3<\/sup>) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.<\/p>\nThe key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.<\/p>\n<\/div>\n<\/div>\n
Fast Approximate Shortest Paths in the Congested Clique<\/a><\/h3>\n\n- Keren Censor-Hillel<\/li>\n
- Michal Dory<\/li>\n
- Janne H. Korhonen<\/li>\n
- Dean Leitersdorf<\/li>\n<\/ul>\n\n\n
We design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:<\/p>\n
\n- A (2+\u03b5)-approximation for all-pairs shortest paths problem in O(log2<\/sup>n \/ \u03b5) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model.<\/li>\n
- A (1+\u03b5)-approximation for multi-source shortest paths problem from O(\u221an) sources in O(log2<\/sup> n \/ \u03b5) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size.<\/li>\n<\/ul>\n
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in \u00d5 (n1\/6<\/sub>) rounds.<\/p>\n<\/div>\n<\/div>\nQuantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model<\/a><\/h3>\n\n- Taisuke Izumi<\/li>\n
- Fran{c c}ois Le Gall<\/li>\n<\/ul>\n\n\n
The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(\u0142og n) bits in synchronous rounds, the best known general algorithm for APSP uses \u00d5(n1\/3<\/sub>) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a \u00d5(n1\/4<\/sub>)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.<\/p>\nOur quantum algorithm is based on a relationship discovered by Vassilevska Williams and Williams (JACM 2018) between the APSP and the detection of negative triangles in a graph. The quantum part of our algorithm exploits the framework for quantum distributed search recently developed by Le Gall and Magniez (PODC 2018). Our main technical contribution is a method showing how to implement multiple quantum searches (one for each edge in the graph) in parallel without introducing congestions.<\/p>\n<\/div>\n<\/div>\n
Deterministic Distributed Dominating Set Approximation in the CONGEST Model<\/a><\/h3>\n\n- Janosch Deurer<\/li>\n
- Fabian Kuhn<\/li>\n
- Yannic Maus<\/li>\n<\/ul>\n\n\n
We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For \u03b5 1\/ poly log \u0394 we obtain two algorithms with approximation factor (1 + \u03b5)(1 + \u0142 n (\u0394 + 1)) and with runtimes 2O<\/sup>(\u221a log n log log n) and O(\u0394 poly log \u0394 + poly log \u0394 log* n), respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic O(log \u0394)-approximation algorithm for the minimum connected dominating set with time complexity 2O(\u221a log n log log n).<\/p>\n<\/div>\n<\/div>\nOptimal Distributed Covering Algorithms<\/a><\/h3>\n\n- Ran Ben Basat<\/li>\n
- Guy Even<\/li>\n
- Ken-ichi Kawarabayashi<\/li>\n
- Gregory Schwartzman<\/li>\n<\/ul>\n\n\n
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank \u0192. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by \u0192. The approximation factor of our algorithm is (\u0192 + \u03b5). Let \u0394 denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log \u0394\/log log \u0394) rounds, for constants \u03b5 \u2208 (0,1] and \u0192 \u2208 N+<\/sup>. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.<\/p>\nFor constant values of \u0192 and \u03b5, our algorithm improves over the (&3402; + \u03b5)-approximation algorithm of [16] whose running time is O(log \u0394 + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an \u0192-approximation for the problem in O(\u0192 log n) rounds, improving over the classical result of [13] that achieves a running time of O(\u0192 log 2<\/sup> n). Finally, for weighted vertex cover (\u0192=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [14].<\/p>\nWe also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (\u0192 + \u03b5)-approximate integral solution in O(1 + \u0192 \/log n)\u22c5 log \u0394 over log log \u0394+(\u0192 \u22c5 log M)1.01<\/sup>\u22c5 log \u03b5-1<\/sup> \u22c5(log \u0394)0.01<\/sup>)) rounds, where \u0192 bounds the number of variables in a constraint, \u0394 bounds the number of constraints a variable appears in, and M=max{1,1\/a min},, amin<\/sub>, where amin<\/sub> is the smallest normalized constraint coefficient. This significantly improves over the results of [16] for the integral case, which achieves the same guarantees in O(\u03b5-4<\/sup> \u22c5 \u01924<\/sup> \u22c5 log \u0192 \u22c5 log(M \u22c5 \u0394)) rounds.<\/p>\n<\/div>\n<\/div>\nSESSION: Session 3<\/h2>\n\u00a0<\/div>\nSecure Distributed Computing Made (Nearly) Optimal<\/a><\/h3>\n\n- Merav Parter<\/li>\n
- Eylon Yogev<\/li>\n<\/ul>\n\n\n
In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes.<\/p>\n
A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees : a collection of n trees T(u1<\/sub>), \u2026, T(un<\/sub>) such that each tree T(ui<\/sub>) spans the neighbors of ui<\/sub> without going through ui<\/sub>. Intuitively, each tree T(ui<\/sub>) allows all neighbors of ui<\/sub> to exchange a secret that is hidden from ui<\/sub>. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d,c)-private neighborhood trees each tree T(ui<\/sub>) has depth O(d) and each edge e \u2208 G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d=O(\u0394 \u2026 D) and c=\u00d5 (D) was presented therein. We make two key contributions:<\/p>\nUniversally Optimal Private Trees:<\/b> We show a combinatorial construction of nearly (universally) optimal (d,c)-private neighborhood trees with d + c=\u00d5 (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees.<\/p>\n
Optimal Secure Computation:<\/b> Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is \u00d5 (poly(\u0394)\u2026 OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely \u00d5 (OPT(G)) per round for a class of “simple” algorithms. This class includes many standard distributed algorithms such as Luby-MIS, the standard logarithmic-round algorithms for matching and \u0394 + 1-coloring, as well as the computation of aggregate functions.<\/p>\n<\/div>\n<\/div>\nWith Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing<\/a><\/h3>\n\n- Avery Miller<\/li>\n
- Boaz Patt-Shamir<\/li>\n
- Will Rosenbaum<\/li>\n<\/ul>\n\n\n
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 \u2264 \u03c1 \u2264 1 and burstiness \u03c3 \u2264 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(\u2113 d1\/\u2113<\/sup> + \u03c3) space suffice, where d is the number of distinct destinations and \u2113=\u230b1\/\u03c1\u230a and we show that \u03a9(1 over \u2113 d1\/\u2113<\/sup> + \u03c3) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d’ + \u03c3 where d’ is the maximum number of destinations on any root-leaf path.<\/p>\n<\/div>\n<\/div>\nPlain SINR is Enough!<\/a><\/h3>\n\n- Magnus M. Halldorsson<\/li>\n
- Tigran Tonoyan<\/li>\n<\/ul>\n\n\n
We develop randomized distributed algorithms for many of the most fundamental communication problems in the wireless SINR model, including (multi-message) broadcast, local broadcast, coloring, MIS, and aggregation. The complexity of the algorithms is optimal up to polylogarithmic preprocessing time. It shows — contrary to expectation — that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and GPS location. A key component of the algorithms is an efficient simulation of CONGEST algorithms on a constant-density SINR backbone.<\/p>\n<\/div>\n<\/div>\n
Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions<\/a><\/h3>\n\n- Ran Gelles<\/li>\n
- Yael Tauman Kalai<\/li>\n
- Govind Ramnarayan<\/li>\n<\/ul>\n\n\n
In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate).<\/p>\n
In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel.<\/p>\n
We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most \u03b5 over m fraction of the total communication, where m is the number of links in the network and \u03b5 is a small constant. This scheme assumes an oblivious adversary which is independent of the parties’ inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to \u03b5 over m log m errors.<\/p>\n
While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.<\/p>\n<\/div>\n<\/div>\n
Multiparty Interactive Communication with Private Channels<\/a><\/h3>\n\n- Abhinav Aggarwal<\/li>\n
- Varsha Dani<\/li>\n
- Thomas P. Hayes<\/li>\n
- Jared Saia<\/li>\n<\/ul>\n\n\n
A group of n players wants to run a distributed protocol \u2118 over a network where communication occurs via private point-to-point channels. Can we efficiently simulate \u2118 in the presence of an adversary who knows \u2118 and is able to maliciously flip bits on the channels? We show that this is possible, even when L, the number of bits sent in \u2118, the average message size \u03b1 in \u2118, and T, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of \u2118, \u2118 such that 1) \u2118’ fails with probability at most \u03b4, for any \u03b4>0; and 2) \u2118’ sends O( L (1 + (1\/\u03b1) \u0142og (n L\/\u03b4)) + T) bits. We note that if \u03b1 is \u03a9 (log (n L\/\u03b4), then \u2118 sends only O(L+T) bits, and is therefore within a constant factor of optimal. Critically, our result requires that \u2118 runs correctly in an asynchronous network and our protocol \u2118 must run in a synchronous network.<\/p>\n<\/div>\n<\/div>\n
Coded State Machine — Scaling State Machine Execution under Byzantine Faults<\/a><\/h3>\n\n- Songze Li<\/li>\n
- Saeid Sahraei<\/li>\n
- Mingchao Yu<\/li>\n
- Salman Avestimehr<\/li>\n
- Sreeram Kannan<\/li>\n
- Pramod Viswanath<\/li>\n<\/ul>\n\n\n
We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.<\/p>\n<\/div>\n<\/div>\n
On Termination of a Flooding Process<\/a><\/h3>\n\n- Walter Hussak<\/li>\n
- Amitabh Trehan<\/li>\n<\/ul>\n\n\n
Flooding is a fundamental distributed algorithms technique. Consider the following flooding process, for simplicity, in a synchronous message passing network: A distinguished node begins the flooding process by sending the (same) message to all its neighbours in the first round. In subsequent rounds, every node receiving the message relays a copy of the message further to all those, and only those, nodes it did not receive the message from in the previous round. However, the nodes do not remember if they’ve taken part in the flooding before and therefore will repeat the process every time they get a message. In other words, they execute an amnesiac flooding process with memory only of the present round. The flooding process terminates in a particular round when no edge in the network carries the message in that, and, hence, subsequent, rounds. We call this process Amnesiac Flooding (AF).<\/p>\n
In this work, the main question we address is whether AF will terminate on an arbitrary network (graph) and in what time? We show that, indeed, AF terminates on any arbitrary graph. Further, AF terminates in at most D rounds in bipartite graphs and at most 2D + 1 rounds in non-bipartite graphs – in this brief announcement, we show this for the bipartite case only.<\/p>\n
We also show that in a natural asynchronous variant of AF, an adversary can always ensure non-termination.<\/p>\n<\/div>\n<\/div>\n
SESSION: Keynote Lecture 2<\/h2>\n\u00a0<\/div>\nTowards a Theory of Randomized Shared Memory Algorithms<\/a><\/h3>\n\n- Philipp Woelfel<\/li>\n<\/ul>\n\n\n
Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms.<\/p>\n
For many years, linearizability [6] has been the gold standard of distributed correctness conditions, and the corner stone of modular programming. In deterministic algorithms, implemented linearizable methods can be assumed to be atomic. But when processes can make random choices, the situation is not the same: Probability distributions of outcomes of algorithms using linearizable methods may be very different from those using equivalent atomic operations [4]. In general, modular algorithm design is much more difficult for randomized algorithms than for deterministic ones. The first part of the talk will present a correctness condition [2, 5] that is suitable for randomized algorithms in certain settings, and will explain why in other settings no such correctness condition exists [3] and what we can do about that.<\/p>\n
To this date, almost all randomized shared memory algorithms are Las Vegas, meaning they permit no error. Monte Carlo algorithms, which allow errors to occur with small probability, have been studied thoroughly for sequential systems. But in the shared memory world such algorithms have been neglected. The second part of this talk will discuss recent attempts to devise Monte Carlo algorithms for fundamental shared memory problems (e.g., [1]). It will also present some general techniques, that have proved useful in the design of concurrent randomized algorithms.<\/p>\n<\/div>\n<\/div>\n
SESSION: Session 4<\/h2>\n\u00a0<\/div>\nOptimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion<\/a><\/h3>\n\n- Zahra Aghazadeh<\/li>\n
- Damien Imbs<\/li>\n
- Michel Raynal<\/li>\n
- Gadi Taubenfeld<\/li>\n
- Philipp Woelfel<\/li>\n<\/ul>\n\n\n
The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B \u2260 A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y \u2260 X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: \u2200 \u2113: (1) < \u2113 \u2264 n: gcd(\u2113,m)=1). Symmetric means here that,process identities define a specific data type which allows a process to check only if two identities are equal or not.<\/p>\n
The present paper presents two optimal deadlock-free symmetric mutual exclusion algorithms for n-process systems where communication is through m registers. The first algorithm, which considers anonymous read\/write registers, works for any m which is \u2265 n and belongs to the set M(n). It follows that this condition on m is both necessary and sufficient for symmetric deadlock-free mutual exclusion in this anonymity context, and this algorithm is optimal with respect to m The second algorithm, which considers anonymous read\/modify\/write atomic registers, works for any m\u2208 M(n), which is shown to be necessary and sufficient for anonymous read\/modify\/write registers. It follows that, when m > 1, m \u2208 M(n) is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the registers read\/write or read\/modify\/write.<\/p>\n<\/div>\n<\/div>\n
Constant Amortized RMR Abortable Mutex for CC and DSM<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Siddhartha Jayanti<\/li>\n<\/ul>\n\n\n
The Abortable mutual exclusion problem, proposed by Scott and Scherer in response to the needs in real time systems and databases, is a variant of mutual exclusion that allows processes to abort from their attempt to acquire the lock. Worst-case constant remote memory reference (RMR) algorithms for mutual exclusion using hardware instructions such as Fetch&Add or Fetch&Store have long existed for both Cache Coherent (CC) and Distributed Shared Memory (DSM) multiprocessors, but no such algorithms are known for abortable mutual exclusion. Even relaxing the worst-case requirement to amortized, algorithms are only known for the CC model.<\/p>\n
In this paper, we improve this state-of-the-art by designing a deterministic algorithm that uses Fetch&Store (FAS) to achieve amortized O(1) RMR in both the CC and DSM models. Our algorithm supports Fast Abort (a process aborts within six steps of receiving the abort signal), and has the following additional desirable properties: it supports an arbitrary number of processes of arbitrary names, requires only O(1) space per process, and satisfies a novel fairness condition that we call “Airline FCFS”. Our algorithm is short and practical with fewer than a dozen lines of code.<\/p>\n<\/div>\n<\/div>\n
A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Both CC and DSM<\/a><\/h3>\n\n- Prasad Jayanti<\/li>\n
- Siddhartha Jayanti<\/li>\n
- Anup Joshi<\/li>\n<\/ul>\n\n\n
In light of recent advances in non-volatile main memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(\u221a log n log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors.<\/p>\n
We answer this question affirmatively by designing an algorithm for a system with n processes, such that, it satisfies the same complexity bound as Golab and Hendler’s for both CC and DSM multiprocessors. Our algorithm has some additional advantages over Golab and Hendler’s: (i) its Exit section is wait-free, (ii) it uses only the Fetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each process to have a cache of only O(1) words, while their algorithm needs a cache of size that is a function of n.<\/p>\n<\/div>\n<\/div>\n
Randomized Concurrent Set Union and Generalized Wake-Up<\/a><\/h3>\n\n- Siddhartha Jayanti<\/li>\n
- Robert E. Tarjan<\/li>\n
- Enric Boix-Adser\u00e0<\/li>\n<\/ul>\n\n\n
We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (\u03b1(n, m\/(np)) + log(np\/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler.<\/p>\n
We use Jayanti’s Wake Up problem and our newly defined Generalized Wake Up problem to prove several lower bounds on concurrent set union. We show an \u03a9(log min {n,p}) expected work lower bound on the cost of any single operation on a set union algorithm. This shows that our single-operation upper bound is optimal across all algorithms when p = n\u03a9(1)<\/sup>. Furthermore, we identify a class of “symmetric algorithms” that captures the complexities of all the known algorithms for the disjoint set union problem, and prove an \u03a9(m\u2022(\u03b1(n, m(np)) + log(np\/m + 1))) expected total work lower bound on algorithms of this class, thereby showing that our algorithm has optimal total work complexity for this class. Finally, we prove that any randomized algorithm, symmetric or not, cannot breach an \u03a9(m \u2022(\u03b1(n, m\/n) + log log(np\/m + 1))) expected total work lower bound.<\/p>\n<\/div>\n<\/div>\nStrongly Linearizable Implementations of Snapshots and Other Types<\/a><\/h3>\n\n- Sean Ovens<\/li>\n
- Philipp Woelfel<\/li>\n<\/ul>\n
The committee decided to award the 2019 Edsger W. Dijkstra Prize in Distributed Computing to Alessandro Panconesi and Aravind Srinivasan for their paper Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, SIAM Journal on Computing, volume 26, number 2, 1997, pages 350-368. A preliminary version of this paper appeared as Fast Randomized Algorithms for Distributed Edge Coloring, Proceedings of the Eleventh Annual ACM Symposium Principles of Distributed Computing (PODC), 1992, pages 251-262.<\/p>\n
The paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6\u0394 + O(log1+\u03b6<\/sup>n) colors and O(log n) rounds with high probability for any constant \u03b6>0, where n is the number of nodes and is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource allocation.<\/p>\n In spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff-Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff-Hoeffding bounds to certain random variables they call \u03bb-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.<\/p>\n<\/div>\n<\/div>\n The winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award is Dr. Sepehr Assadi for his dissertation Combinatorial Optimization on Massive Datasets: Streaming, Distributed, and Massively Parallel Computation, written under the supervision of Prof. Sanjeev Khanna at the University of Pennsylvania.<\/p>\n The thesis resolves a number of long-standing problems in the exciting and still relatively new area of sublinear computation. The area of sublinear computation focuses on design of algorithms that use sublinear space, time, or communication to solve global optimization problems on very large datasets. In addition to addressing a wide range of different problems, comprising graph optimization problems (matching, vertex cover, and connectivity), submodular optimization (set cover and maximum coverage), and resource-constrained optimization (combinatorial auctions and learning), these problems are studied in three different models of computation, namely, streaming algorithms, multiparty communication, and massively parallel computation (MPC). The thesis also reveals interesting relations between these different models, including generic algorithmic and analysis techniques that can be applied in all of them.<\/p>\n For many fundamental optimization problems, the thesis gives asymptotically matching algorithmic and intractability results, completely resolving several long-standing problems. This is accomplished by using a broad spectrum of mathematical methods in very detailed and intricate proofs. In addition to a wide variety of classic techniques, ranging from graph theory, combinatorics, probability, linear algebra and calculus, it also makes heavy use of communication complexity and information theory, for example.<\/p>\n Sepehr’s dissertation work has been published in a remarkably large number of top-conference papers. It received multiple best paper awards and multiple special issue invitations, as well as two invitations to the Highlights of Algorithms (HALG) conference. Due to its contributions to the field of distributed computing and all the merits mentioned above, the award committee unanimously selected this thesis as the winner of the 2019 Principles of Distributed Computing Doctoral Dissertation Award.<\/p>\n<\/div>\n<\/div>\n Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of “local computation algorithms” which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms.<\/p>\n In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed — we will give special focus to finding maximal independent sets and sparse spanning graphs.<\/p>\n<\/div>\n<\/div>\n We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and “measuring instruments” of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent.<\/p>\n We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.<\/p>\n<\/div>\n<\/div>\n We study the composability of discrete chemical reaction networks (CRNs) that stably compute (i.e., with probability 0 of error) integer-valued functions \u0192:Nd<\/sup>\u2192 N. We consider output-oblivious CRNs in which the output species is never a reactant (input) to any reaction. The class of output-oblivious CRNs is fundamental, appearing in earlier studies of CRN computation, because it is precisely the class of CRNs that can be composed by simply renaming the output of the upstream CRN to match the input of the downstream CRN.<\/p>\n Our main theorem precisely characterizes the functions f stably computable by output-oblivious CRNs with an initial leader. The key necessary condition is that for sufficiently large inputs, f is the minimum of a finite number of nondecreasing quilt-affine functions. (An affine function is linear with a constant offset; a quilt-affine function is linear with a periodic offset).<\/p>\n<\/div>\n<\/div>\n We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is disseminated by a collection of agents performing independent random walks. In the VISIT-EXCHANGE protocol, both nodes and agents store information, and each time an agent visits a node, the two exchange all the information they have. In the MEET-EXCHANGE protocol, only the agents store information, and exchange their information with each agent they meet.<\/p>\n We consider the broadcast time of a single piece of information in an n-node graph for the above three protocols, assuming a linear number of agents that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols are significantly faster than PUSH-PULL, and graphs where the converse is true. We attribute the good performance of agent-based algorithms to their inherently fair bandwidth utilization, and conclude that, in certain settings, agent-based information dissemination, separately or in combination with PUSH-PULL, can significantly improve the broadcast time.<\/p>\n The graphs considered above are highly non-regular. Our main technical result is that on any regular graph of at least logarithmic degree, PUSH-PULL and VISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novel coupling argument which relates the random choices of vertices in PUSH-PULL with the random walks in VISIT-EXCHANGE. Further, we show that the broadcast time of MEET-EXCHANGE is asymptotically at least as large as the other two’s on all regular graphs, and strictly larger on some regular graphs.<\/p>\n As far as we know, this is the first systematic and thorough comparison of the running times of these very natural information dissemination protocols.<\/p>\n<\/div>\n<\/div>\n We study uniform population protocols: networks of anonymous agents whose pairwise interactions are chosen at random, where each agent uses an identical transition algorithm that does not depend on the population size n. Many existing polylog(n) time protocols for leader election and majority computation are nonuniform: to operate correctly, they require all agents to be initialized with an approximate estimate of n (specifically, the value \u0142floor\u0142og n\\rfloor). Our first main result is a uniform protocol for calculating \u0142og(n) \\pm O(1) with high probability in O(\u0142og^2 n) time and O(\u0142og^4 n) states (O(\u0142og \u0142og n) bits of memory). The protocol is not terminating : it does not signal when the estimate is close to the true value of \u0142og n. If it could be made terminating with high probability, this would allow composition with protocols requiring a size estimate initially. We do show how our main protocol can be indirectly composed with others in a simple and elegant way, based on leaderless phase clocks, demonstrating that those protocols can in fact be made uniform. However, our second main result implies that the protocol cannot be made terminating, a consequence of a much stronger result: a uniform protocol for any task requiring more than constant time cannot be terminating even with probability bounded above 0, if infinitely many initial configurations are dense : any state present initially occupies \u00d8mega(n) agents. (In particular no leader is allowed.) Crucially, the result holds no matter the memory or time permitted.<\/p>\n<\/div>\n<\/div>\n We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using \u00d5 (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.<\/p>\n<\/div>\n<\/div>\n In this paper, we study the self-stabilizing leader election (SSLE) problem in population protocols. We construct a non-deterministic population protocol that can solve SSLE on directed rings of all sizes. Our algorithm uses a constant number of states and can be converted to a deterministic population protocol on undirected rings using previous techniques [8]. Furthermore, we extend our algorithm to perform SSLE on directed and undirected tori of arbitrary sizes.<\/p>\n<\/div>\n<\/div>\n In this paper, we present a leader election protocol in the population protocol model that stabilizes within O(log n) parallel time in expectation with O(log n) states per agent, where n is the number of agents. Given a rough knowledge m of the population size n such that m \u2265 = log2<\/sub> n and m=O(log n), this protocol guarantees that exactly one leader is elected and the unique leader is kept forever thereafter.<\/p>\n<\/div>\n<\/div>\n A key factor limiting the performance of central place foraging algorithms is the awareness of the agent(s) about the location of food items around the nest. We study the ratio of how much time an ignorant agent takes relative to an omniscient forager for complete collection of food items in the arena. This effectively quantifies the penalty each algorithm pays for not knowing (or choosing to ignore information gained about) where the resources are located. We model the effect of depletion of food items from the arena on the foraging efficiency over time and analytically verify that returning to the location of the last food item found strongly helps in counteracting this effect. To the best of our knowledge, these results have only been empirically argued so far.<\/p>\n<\/div>\n<\/div>\n An(\u03b5,\u03c6)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1<\/sub>\u222a\u2026\u222a Vx<\/sub> such that (1) each cluster Vi<\/sub> induces subgraph with conductance at least \u03c6, and (2) the number of inter-cluster edges is at most \u03b5|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.<\/p>\n Specifically, we construct an (\u03b5,\u03c6)-expander decomposition with \u03c6=(\u03b5\/log n)2 O(k)<\/sup> in O(n2\/k<\/sup> \u22c5 poly (1\/\u03c6, log n))rounds for any \u03b5 \u2208(0,1) and positive integer k. For example, a (1\/no(1)<\/sup>, 1\/no(1)<\/sup>)-expander decomposition only requires O(no(1)<\/sup>) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1\/poly log n)-expander decomposition can be computed in O(n\u03b3<\/sup>) rounds, for any arbitrarily small constant \u03b3 > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1\/6,1\/poly log n)-expander decomposition using \u00d5 (n1-\u03b4<\/sup>) rounds for any \u03b4 > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most n\u03b4<\/sup>. Our algorithm does not have this caveat.<\/p>\n By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC’17], we obtain a triangle enumeration algorithm using \u00d5(n1\/3<\/sup>) rounds. This matches the lower bound by Izumi and LeGall [PODC’17] and Pandurangan, Robinson and Scquizzato [SPAA’18] of \u00d8(n1\/3<\/sup>) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.<\/p>\n The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.<\/p>\n<\/div>\n<\/div>\n We design fast deterministic algorithms for distance computation in the CONGESTED CLIQUE model. Our key contributions include:<\/p>\n Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in \u00d5 (n1\/6<\/sub>) rounds.<\/p>\n<\/div>\n<\/div>\n The All-Pairs Shortest Path problem (APSP) is one of the most central problems in distributed computation. In the CONGEST-CLIQUE model, in which n nodes communicate with each other over a fully connected network by exchanging messages of O(\u0142og n) bits in synchronous rounds, the best known general algorithm for APSP uses \u00d5(n1\/3<\/sub>) rounds. Breaking this barrier is a fundamental challenge in distributed graph algorithms. In this paper we investigate for the first time quantum distributed algorithms in the CONGEST-CLIQUE model, where nodes can exchange messages of O(log n) quantum bits, and show that this barrier can be broken: we construct a \u00d5(n1\/4<\/sub>)-round quantum distributed algorithm for the APSP over directed graphs with polynomial weights in the CONGEST-CLIQUE model. This speedup in the quantum setting contrasts with the case of the standard CONGEST model, for which Elkin et al. (PODC 2014) showed that quantum communication does not offer significant advantages over classical communication.<\/p>\n Our quantum algorithm is based on a relationship discovered by Vassilevska Williams and Williams (JACM 2018) between the APSP and the detection of negative triangles in a graph. The quantum part of our algorithm exploits the framework for quantum distributed search recently developed by Le Gall and Magniez (PODC 2018). Our main technical contribution is a method showing how to implement multiple quantum searches (one for each edge in the graph) in parallel without introducing congestions.<\/p>\n<\/div>\n<\/div>\n We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For \u03b5 1\/ poly log \u0394 we obtain two algorithms with approximation factor (1 + \u03b5)(1 + \u0142 n (\u0394 + 1)) and with runtimes 2O<\/sup>(\u221a log n log log n) and O(\u0394 poly log \u0394 + poly log \u0394 log* n), respectively. Further we show how dominating set approximations can be deterministically transformed into a connected dominating set in the CONGEST model while only increasing the approximation guarantee by a constant factor. This results in a deterministic O(log \u0394)-approximation algorithm for the minimum connected dominating set with time complexity 2O(\u221a log n log log n).<\/p>\n<\/div>\n<\/div>\n We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank \u0192. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by \u0192. The approximation factor of our algorithm is (\u0192 + \u03b5). Let \u0394 denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log \u0394\/log log \u0394) rounds, for constants \u03b5 \u2208 (0,1] and \u0192 \u2208 N+<\/sup>. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.<\/p>\n For constant values of \u0192 and \u03b5, our algorithm improves over the (&3402; + \u03b5)-approximation algorithm of [16] whose running time is O(log \u0394 + log W), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an \u0192-approximation for the problem in O(\u0192 log n) rounds, improving over the classical result of [13] that achieves a running time of O(\u0192 log 2<\/sup> n). Finally, for weighted vertex cover (\u0192=2) our algorithm achieves a deterministic running time of O(log n), matching the randomized previously best result of [14].<\/p>\n We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an (\u0192 + \u03b5)-approximate integral solution in O(1 + \u0192 \/log n)\u22c5 log \u0394 over log log \u0394+(\u0192 \u22c5 log M)1.01<\/sup>\u22c5 log \u03b5-1<\/sup> \u22c5(log \u0394)0.01<\/sup>)) rounds, where \u0192 bounds the number of variables in a constraint, \u0394 bounds the number of constraints a variable appears in, and M=max{1,1\/a min},, amin<\/sub>, where amin<\/sub> is the smallest normalized constraint coefficient. This significantly improves over the results of [16] for the integral case, which achieves the same guarantees in O(\u03b5-4<\/sup> \u22c5 \u01924<\/sup> \u22c5 log \u0192 \u22c5 log(M \u22c5 \u0394)) rounds.<\/p>\n<\/div>\n<\/div>\n In this paper, we study secure distributed algorithms that are nearly optimal, with respect to running time, for the given input graph G. Roughly speaking, an algorithm is secure if the nodes learn only their final output while gaining no information on the input (or output) of other nodes.<\/p>\n A graph theoretic framework for secure distributed computation was recently introduced by the authors (SODA 2019). This framework is quite general and it is based on a new combinatorial structure called private neighborhood trees : a collection of n trees T(u1<\/sub>), \u2026, T(un<\/sub>) such that each tree T(ui<\/sub>) spans the neighbors of ui<\/sub> without going through ui<\/sub>. Intuitively, each tree T(ui<\/sub>) allows all neighbors of ui<\/sub> to exchange a secret that is hidden from ui<\/sub>. The efficiency of the framework depends on two key parameters of these trees: their depth and the amount of overlap. In a (d,c)-private neighborhood trees each tree T(ui<\/sub>) has depth O(d) and each edge e \u2208 G appears in at most O(c) different trees. An existentially optimal construction of private neighborhood trees with d=O(\u0394 \u2026 D) and c=\u00d5 (D) was presented therein. We make two key contributions:<\/p>\n Universally Optimal Private Trees:<\/b> We show a combinatorial construction of nearly (universally) optimal (d,c)-private neighborhood trees with d + c=\u00d5 (OPT(G)) for any input graph G. Perhaps surprisingly, we show that OPT(G) is equal to the best depth possible for these trees even without the congestion constraint. We also present efficient distributed constructions of these private trees.<\/p>\n Optimal Secure Computation:<\/b> Using the optimal constructions above, we get a secure compiler for distributed algorithms where the overhead for each round is \u00d5 (poly(\u0394)\u2026 OPT(G)). As our second key contribution, we design an optimal compiler with an overhead of merely \u00d5 (OPT(G)) per round for a class of “simple” algorithms. This class includes many standard distributed algorithms such as Luby-MIS, the standard logarithmic-round algorithms for matching and \u0394 + 1-coloring, as well as the computation of aggregate functions.<\/p>\n<\/div>\n<\/div>\n We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 \u2264 \u03c1 \u2264 1 and burstiness \u03c3 \u2264 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(\u2113 d1\/\u2113<\/sup> + \u03c3) space suffice, where d is the number of distinct destinations and \u2113=\u230b1\/\u03c1\u230a and we show that \u03a9(1 over \u2113 d1\/\u2113<\/sup> + \u03c3) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d’ + \u03c3 where d’ is the maximum number of destinations on any root-leaf path.<\/p>\n<\/div>\n<\/div>\n We develop randomized distributed algorithms for many of the most fundamental communication problems in the wireless SINR model, including (multi-message) broadcast, local broadcast, coloring, MIS, and aggregation. The complexity of the algorithms is optimal up to polylogarithmic preprocessing time. It shows — contrary to expectation — that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and GPS location. A key component of the algorithms is an efficient simulation of CONGEST algorithms on a constant-density SINR backbone.<\/p>\n<\/div>\n<\/div>\n In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate).<\/p>\n In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel.<\/p>\n We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most \u03b5 over m fraction of the total communication, where m is the number of links in the network and \u03b5 is a small constant. This scheme assumes an oblivious adversary which is independent of the parties’ inputs and randomness. We can remove this assumption and resist a worst-case adversary at the price of being resilient to \u03b5 over m log m errors.<\/p>\n While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.<\/p>\n<\/div>\n<\/div>\n A group of n players wants to run a distributed protocol \u2118 over a network where communication occurs via private point-to-point channels. Can we efficiently simulate \u2118 in the presence of an adversary who knows \u2118 and is able to maliciously flip bits on the channels? We show that this is possible, even when L, the number of bits sent in \u2118, the average message size \u03b1 in \u2118, and T, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of \u2118, \u2118 such that 1) \u2118’ fails with probability at most \u03b4, for any \u03b4>0; and 2) \u2118’ sends O( L (1 + (1\/\u03b1) \u0142og (n L\/\u03b4)) + T) bits. We note that if \u03b1 is \u03a9 (log (n L\/\u03b4), then \u2118 sends only O(L+T) bits, and is therefore within a constant factor of optimal. Critically, our result requires that \u2118 runs correctly in an asynchronous network and our protocol \u2118 must run in a synchronous network.<\/p>\n<\/div>\n<\/div>\n We introduce Coded State Machine (CSM), an information-theoretic framework to securely and efficiently execute multiple state machines on Byzantine nodes. The standard method of solving this problem is using State Machine Replication, which achieves high security at the cost of low efficiency. CSM simultaneously achieves the optimal linear scaling in storage, throughput, and security with increasing network size. The storage is scaled via the design of Lagrange coded states and coded input commands that require the same storage size as their origins. The computational efficiency is scaled using a novel delegation algorithm, called INTERMIX, which is an information-theoretically verifiable matrix-vector multiplication algorithm of independent interest.<\/p>\n<\/div>\n<\/div>\n Flooding is a fundamental distributed algorithms technique. Consider the following flooding process, for simplicity, in a synchronous message passing network: A distinguished node begins the flooding process by sending the (same) message to all its neighbours in the first round. In subsequent rounds, every node receiving the message relays a copy of the message further to all those, and only those, nodes it did not receive the message from in the previous round. However, the nodes do not remember if they’ve taken part in the flooding before and therefore will repeat the process every time they get a message. In other words, they execute an amnesiac flooding process with memory only of the present round. The flooding process terminates in a particular round when no edge in the network carries the message in that, and, hence, subsequent, rounds. We call this process Amnesiac Flooding (AF).<\/p>\n In this work, the main question we address is whether AF will terminate on an arbitrary network (graph) and in what time? We show that, indeed, AF terminates on any arbitrary graph. Further, AF terminates in at most D rounds in bipartite graphs and at most 2D + 1 rounds in non-bipartite graphs – in this brief announcement, we show this for the bipartite case only.<\/p>\n We also show that in a natural asynchronous variant of AF, an adversary can always ensure non-termination.<\/p>\n<\/div>\n<\/div>\n Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging. This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms.<\/p>\n For many years, linearizability [6] has been the gold standard of distributed correctness conditions, and the corner stone of modular programming. In deterministic algorithms, implemented linearizable methods can be assumed to be atomic. But when processes can make random choices, the situation is not the same: Probability distributions of outcomes of algorithms using linearizable methods may be very different from those using equivalent atomic operations [4]. In general, modular algorithm design is much more difficult for randomized algorithms than for deterministic ones. The first part of the talk will present a correctness condition [2, 5] that is suitable for randomized algorithms in certain settings, and will explain why in other settings no such correctness condition exists [3] and what we can do about that.<\/p>\n To this date, almost all randomized shared memory algorithms are Las Vegas, meaning they permit no error. Monte Carlo algorithms, which allow errors to occur with small probability, have been studied thoroughly for sequential systems. But in the shared memory world such algorithms have been neglected. The second part of this talk will discuss recent attempts to devise Monte Carlo algorithms for fundamental shared memory problems (e.g., [1]). It will also present some general techniques, that have proved useful in the design of concurrent randomized algorithms.<\/p>\n<\/div>\n<\/div>\n The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B \u2260 A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y \u2260 X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: \u2200 \u2113: (1) < \u2113 \u2264 n: gcd(\u2113,m)=1). Symmetric means here that,process identities define a specific data type which allows a process to check only if two identities are equal or not.<\/p>\n The present paper presents two optimal deadlock-free symmetric mutual exclusion algorithms for n-process systems where communication is through m registers. The first algorithm, which considers anonymous read\/write registers, works for any m which is \u2265 n and belongs to the set M(n). It follows that this condition on m is both necessary and sufficient for symmetric deadlock-free mutual exclusion in this anonymity context, and this algorithm is optimal with respect to m The second algorithm, which considers anonymous read\/modify\/write atomic registers, works for any m\u2208 M(n), which is shown to be necessary and sufficient for anonymous read\/modify\/write registers. It follows that, when m > 1, m \u2208 M(n) is a tight characterization of the size of the anonymous shared memory needed to solve deadlock-free mutex, be the registers read\/write or read\/modify\/write.<\/p>\n<\/div>\n<\/div>\n The Abortable mutual exclusion problem, proposed by Scott and Scherer in response to the needs in real time systems and databases, is a variant of mutual exclusion that allows processes to abort from their attempt to acquire the lock. Worst-case constant remote memory reference (RMR) algorithms for mutual exclusion using hardware instructions such as Fetch&Add or Fetch&Store have long existed for both Cache Coherent (CC) and Distributed Shared Memory (DSM) multiprocessors, but no such algorithms are known for abortable mutual exclusion. Even relaxing the worst-case requirement to amortized, algorithms are only known for the CC model.<\/p>\n In this paper, we improve this state-of-the-art by designing a deterministic algorithm that uses Fetch&Store (FAS) to achieve amortized O(1) RMR in both the CC and DSM models. Our algorithm supports Fast Abort (a process aborts within six steps of receiving the abort signal), and has the following additional desirable properties: it supports an arbitrary number of processes of arbitrary names, requires only O(1) space per process, and satisfies a novel fairness condition that we call “Airline FCFS”. Our algorithm is short and practical with fewer than a dozen lines of code.<\/p>\n<\/div>\n<\/div>\n In light of recent advances in non-volatile main memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(\u221a log n log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors.<\/p>\n We answer this question affirmatively by designing an algorithm for a system with n processes, such that, it satisfies the same complexity bound as Golab and Hendler’s for both CC and DSM multiprocessors. Our algorithm has some additional advantages over Golab and Hendler’s: (i) its Exit section is wait-free, (ii) it uses only the Fetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each process to have a cache of only O(1) words, while their algorithm needs a cache of size that is a function of n.<\/p>\n<\/div>\n<\/div>\n We consider the disjoint set union problem in the asynchronous shared memory multiprocessor computation model. We design a randomized algorithm that performs at most O(log n) work per operation (with high probability), and performs at most O(m #8226; (\u03b1(n, m\/(np)) + log(np\/m + 1)) total work in expectation for a problem instance with m operations on n elements solved by p processes. Our algorithm is the first to have work bounds that grow sublinearly with p against an adversarial scheduler.<\/p>\n We use Jayanti’s Wake Up problem and our newly defined Generalized Wake Up problem to prove several lower bounds on concurrent set union. We show an \u03a9(log min {n,p}) expected work lower bound on the cost of any single operation on a set union algorithm. This shows that our single-operation upper bound is optimal across all algorithms when p = n\u03a9(1)<\/sup>. Furthermore, we identify a class of “symmetric algorithms” that captures the complexities of all the known algorithms for the disjoint set union problem, and prove an \u03a9(m\u2022(\u03b1(n, m(np)) + log(np\/m + 1))) expected total work lower bound on algorithms of this class, thereby showing that our algorithm has optimal total work complexity for this class. Finally, we prove that any randomized algorithm, symmetric or not, cannot breach an \u03a9(m \u2022(\u03b1(n, m\/n) + log log(np\/m + 1))) expected total work lower bound.<\/p>\n<\/div>\n<\/div>\n2019 Principles of Distributed Computing Doctoral Dissertation Award<\/a><\/h3>\n
\n
SESSION: Keynote Lecture 1<\/h2>\n
Local Computation Algorithms<\/a><\/h3>\n
\n
SESSION: Session 1<\/h2>\n
Symmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes<\/a><\/h3>\n
\n
Composable Computation in Discrete Chemical Reaction Networks<\/a><\/h3>\n
\n
How to Spread a Rumor: Call Your Neighbors or Take a Walk?<\/a><\/h3>\n
\n
Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols<\/a><\/h3>\n
\n
On Counting the Population Size<\/a><\/h3>\n
\n
Self-Stabilizing Leader Election<\/a><\/h3>\n
\n
Logarithmic Expected-Time Leader Election in Population Protocol Model<\/a><\/h3>\n
\n
On Site Fidelity and the Price of Ignorance in Swarm Robotic Central Place Foraging Algorithms<\/a><\/h3>\n
\n
SESSION: Session 2<\/h2>\n
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration<\/a><\/h3>\n
\n
Fast Approximate Shortest Paths in the Congested Clique<\/a><\/h3>\n
\n
\n
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model<\/a><\/h3>\n
\n
Deterministic Distributed Dominating Set Approximation in the CONGEST Model<\/a><\/h3>\n
\n
Optimal Distributed Covering Algorithms<\/a><\/h3>\n
\n
SESSION: Session 3<\/h2>\n
Secure Distributed Computing Made (Nearly) Optimal<\/a><\/h3>\n
\n
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing<\/a><\/h3>\n
\n
Plain SINR is Enough!<\/a><\/h3>\n
\n
Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions<\/a><\/h3>\n
\n
Multiparty Interactive Communication with Private Channels<\/a><\/h3>\n
\n
Coded State Machine — Scaling State Machine Execution under Byzantine Faults<\/a><\/h3>\n
\n
On Termination of a Flooding Process<\/a><\/h3>\n
\n
SESSION: Keynote Lecture 2<\/h2>\n
Towards a Theory of Randomized Shared Memory Algorithms<\/a><\/h3>\n
\n
SESSION: Session 4<\/h2>\n
Optimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion<\/a><\/h3>\n
\n
Constant Amortized RMR Abortable Mutex for CC and DSM<\/a><\/h3>\n
\n
A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Both CC and DSM<\/a><\/h3>\n
\n
Randomized Concurrent Set Union and Generalized Wake-Up<\/a><\/h3>\n
\n
Strongly Linearizable Implementations of Snapshots and Other Types<\/a><\/h3>\n
\n