- Fast Two-Robot Disk Evacuation with Wireless Communication
Ioannis Lamprou, Russell Martin and Sven Schewe
- Deterministic Leader Election Algorithm in O(D + log n) Time with Messages of Size O(1)
Arnaud Casteigts, Yves Métivier, John-Michael Robson and Akka Zemmari
- Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel and Seri Khoury
- Fast Distributed Algorithms for Testing Graph Properties
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman and Yadu Vasudev
- Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems
Francois Le Gall
- Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
Christian Scheideler, Alexander Setzer and Thim Strothmann
- Asynchronous Embedded Pattern Formation without Orientation
Serafino Cicerone, Gabriele Di Stefano and Alfredo Navarra
- Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
Dan Hefetz, Fabian Kuhn, Yannic Maus and Angelika Steger
- Optimal Consistent Network Updates in Polynomial Time
Pavol Cerny, Nate Foster, Nilesh Jagnik and Jedidiah McClurg
- Distributed Construction of Purely Additive Spanners
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz and Amir Yehudayoff
- Optimal Fair Computation
Rachid Guerraoui and Jingjing Wang
- Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
Bernhard Haeupler, Taisuke Izumi and Goran Zuzic
- Anonymity-Preserving Failure Detectors
Zohir Bouzid and Corentin Travers
- Certified Universal Gathering in R2 for Oblivious Mobile Robots
Pierre Courtieu, Lionel Rieg, Sebastien Tixeuil and Xavier Urbain
- Non-Local Probes Do Not Help with Many Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina and Jukka Suomela
- Are Byzantine Failures Really Different From Crash Failures?
Damien Imbs, Michel Raynal and Julien Stainer
- Sublinear-Space Distance Labeling using Hubs
Pawel Gawrychowski, Adrian Kosowski and Przemyslaw Uznanski
- Online Balanced Repartitioning
Chen Avin, Andreas Loukas, Maciej Pacut and Stefan Schmid
- Lower bound on the step complexity of obstruction-free consensus
Hagit Attiya, Ohad Ben-Baruch and Danny Hendler
- Opacity vs TMS2: Expectations and Reality
Sandeep Hans, Ahmed Hassan, Roberto Palmieri, Sebastiano Peluso and Binoy Ravindran
- On Composition and Implementation of Sequential Consistency
Matthieu Perrin, Matoula Petrolia, Achour Mostéfaoui and Claude Jard
- k-Abortable Objects: Progress under High Contention
Naama Ben-David, David Yu Cheng Chan, Vassos Hadzilacos and Sam Toueg
- Linearizability of Persistent Memory Objects under a Full-System-Crash Failure Model
Joseph Izraelevitz, Hammurabi Mendes and Michael Scott
- Buffer Size for Routing Limited-Rate Adversarial Traffic
Avery Miller and Boaz Patt-Shamir
- Distributed Testing of Excluded Subgraphs
Pierre Fraigniaud, Ivan Rapaport, Ville Salo and Ioan Todinca
- How to Discreetly Spread a Rumor in a Crowd
Mohsen Ghaffari and Calvin Newport
- Depth of a random binary search tree with concurrent insertions
James Aspnes and Eric Ruppert
- Priority Mutual Exclusion: Specification and Algorithm
Chien-Chung Huang and Prasad Jayanti
- Information Spreading in Dynamic Networks under Oblivious Adversaries
John Augustine, Chen Avin, Mehraneh Liaee, Gopal Pandurangan and Rajmohan Rajaraman
- Non-Bayesian Learning in the Presence of Byzantine Agents
Lili Su and Nitin Vaidya
- Asynchronous Computability Theorems for t-Resilient Systems
Vikram Saraph, Maurice Herlihy and Eli Gafni
- Upper Bounds for Boundless Tagging with Bounded Objects
Zahra Aghazadeh and Philipp Woelfel
- Brief Announcements: Local Distributed Verification
Alkida Balliu, Gianlorenzo D’Angelo, Pierre Fraigniaud and Dennis Olivetti
- Brief Announcements: Optimal Implementations of Large Single-Writer Registers
Yuanhao Wei and Tian Ze Chen
- Brief Announcements: Deterministic MST Sparsification in the Congested Clique
Janne H. Korhonen
- Brief Announcement: Symmetricity in 3D-space — Characterizing Formable Patterns by Synchronous Mobile Robots
Yukiko Yamauchi, Taichi Uehara and Masafumi Yamashita
- Brief Announcements: Mending the Big-Data Missing Information
Hadassa Daltrophe, Shlomi Dolev and Zvi Lotker
- Brief Announcements: Set-Consensus Collections are Decidable
Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni and Petr Kuznetsov
- Brief Announcements: A Log*-Time Local Approximation Scheme for Bounded Genus Graphs
Saeed Akhoondian Amiri and Stefan Schmid
- Brief Announcements: On the Space Complexity of Conflict Detector Objects
Claire Capdevielle, Colette Johnen and Alessia Milani
- Brief Announcements: Public vs. Private Randomness for Multi-Player Simultaneous Communication
Orr Fischer, Rotem Oshman and Uri Zwick
- Brief Announcements: Beeping a Maximal Independent Set Fast
Stephan Holzer and Nancy Lynch
Accepted Papers with abstracts
- Fast Two-Robot Disk Evacuation with Wireless Communication
Ioannis Lamprou, Russell Martin and Sven Schewe
Abstract:
In the fast evacuation problem, we study the path planning problem for two robots who want to minimize the worst-case evacuation time on the unit disk. The robots are initially placed at the center of the disk. In order to evacuate, they need to reach an unknown point, the exit, on the boundary of the disk. Once one of the robots finds the exit, it will instantaneously notify the other agent, who will make a beeline to it. The problem has been studied for robots with the same speed~\cite{s1}. We study a more general case where one robot has speed $1$ and the other has speed $s \geq 1$. We provide optimal evacuation strategies in the case that $s \geq c_{2.75} \approx 2.75$ by showing matching upper and lower bounds on the worst-case evacuation time. For $1\leq s < c_{2.75}$, we show (non-matching) upper and lower bounds on the evacuation time with a ratio less than $1.22$. Moreover, we demonstrate that a generalization of the two-robot search strategy from~\cite{s1} is outperformed by our proposed strategies for any $s \geq c_{1.71} \approx 1.71$.
- Deterministic Leader Election Algorithm in O(D + log n) Time with Messages of Size O(1)
Arnaud Casteigts, Yves Métivier, John-Michael Robson and Akka Zemmari
Abstract:
This paper presents a distributed algorithm, called STT, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $O(\log n)$, where $n$ is the number of processors. It elects a leader in $O(D + \log n)$ rounds, where $D$ is the diameter of the network, with messages of size $O(1)$. Thus it has a bit complexity of $O(D + \log n)$. This substantially improves upon the best known algorithm whose bit complexity is $O(D \log n)$. In fact, using the lower bound by Kutten et al. [KPPRT15] and a result of Dinitz and Solomon [DS07], we show that the bit complexity of STT is optimal (up to a constant factor), which is a step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as $n$ or $D$.
- Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel and Seri Khoury
Abstract:
We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model.
Specifically, we show an $\widetilde{\Omega}(n)$ lower bound for computing the diameter in sparse networks, which was previously known only for dense networks [Frishknecht et al., SODA 2012]. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define.
Moreover, our technique allows us to show $\widetilde{\Omega}(n)$ lower bounds for computing $(\frac{3}{2}-\varepsilon)$-approximations of the diameter or the radius, and for computing a $(\frac{5}{3}-\varepsilon)$-approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors [Frishknecht et al., SODA 2012], and for eccentricities the improvement is both in the lower bound and in the approximation factor [Holzer and Wattenhofer, PODC 2012].
Interestingly, our technique also allows showing an almost-linear lower bound for the verification of $(\alpha,\beta)$-spanners, for $\alpha < \beta+1$.
- Fast Distributed Algorithms for Testing Graph Properties
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman and Yadu Vasudev
Abstract:
We initiate a thorough study of \emph{distributed property testing} — producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called \emph{dense} graph testing model we emulate sequential tests for nearly all graph properties having $1$-sided tests, while in the \emph{general} and \emph{sparse} models we obtain faster tests for triangle-freeness, cycle-freeness and bipartiteness, respectively. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness, which holds even in the stronger LOCAL model.
In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that may be of independent interest.
- Further Algebraic Algorithms in the Congested Clique Model and Applications to Graph-Theoretic Problems
Francois Le Gall
Abstract:
Censor-Hillel et al.~[PODC’15] recently showed how to efficiently implement centralized algebraic algorithms for matrix multiplication in the congested clique model, a model of distributed computing that has received increasing attention in the past few years. This paper develops further algebraic techniques for designing algorithms in this model. We present deterministic and randomized algorithms, in the congested clique model, for efficiently computing multiple independent instances of matrix products, computing the determinant, the rank and the inverse of a matrix, and solving systems of linear equations. As applications of these techniques, we obtain more efficient algorithms for the computation, again in the congested clique model, of the all-pairs shortest paths and the diameter in directed and undirected graphs with small weights, improving over Censor-Hillel et al.’s work. We also obtain algorithms for several other graph-theoretic problems such as computing the number of edges in a maximum matching and the Gallai-Edmonds decomposition of a simple graph, and computing a minimum vertex cover of a bipartite graph.
- Towards a Universal Approach for Monotonic Searchability in Self-Stabilizing Overlay Networks
Christian Scheideler, Alexander Setzer and Thim Strothmann
Abstract:
For overlay networks the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have already been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network. We investigate overlay networks that are not only self-stabilizing but that also ensure that monotonic searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. Monotonic searchability was recently introduced in OPODIS 2015, in which the authors provide a solution for a simple line topology. We present the first universal approach to maintain monotonic searchability that is applicable to a wide range of topologies. As the base for our approach, we introduce a set of primitives for manipulating overlay networks that allows us to maintain searchability and show how existing protocols can be transformed to use theses primitives. We complement this result with a generic search protocol that together with the use of our primitives guarantees monotonic searchability. As an additional feature, searching existing nodes with the generic search protocol is as fast as searching a node with any other fixed routing protocol once the topology has stabilized.
- Asynchronous Embedded Pattern Formation without Orientation
Serafino Cicerone, Gabriele Di Stefano and Alfredo Navarra
Abstract:
We consider the Embedded Pattern Formation (EPF) problem introduced in [Fujinaga et al., SIAM J. on Comput., 44(3), 2015]. Given a set F of distinct points in the Euclidean plane (called here fixed-points) and a set R of robots such that |R| = |F|, the problem asks for a distributed algorithm that moves robots so as to occupy all points in F. Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of the robots’ positions and the fixed-points (Look) according to its own coordinate system, decides whether to move toward some direction (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are anonymous and execute the same algorithm. Initially, each robot occupies a distinct position. In the mentioned paper, the problem has been investigated by empowering robots with chirality, that is robot share a common left-right orientation. The obtained solution has been used as a sub-procedure to solve the general Pattern Formation problem, without fixed-points but still with chirality. Here we investigate the other branch, that is, we are interested in solving epf without chirality. We fully characterize when the EPF problem can be accomplished and we design a deterministic distributed algorithm that solves the problem for all configurations but those identified as unsolvable. Our approach is also characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness.
- Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
Dan Hefetz, Fabian Kuhn, Yannic Maus and Angelika Steger
Abstract:
We show an $\Omega(\Delta^{\frac{1}{3}-\frac{\eta}{3}})$ lower bound on the runtime for any deterministic distributed $O(\Delta^{1+\eta})$-graph coloring algorithm in a weak version of the LOCAL-model.
In particular, given a network graph \mbox{$G=(V,E)$}, in the weak LOCAL-model nodes communicate in synchronous rounds and they can use unbounded local computation. We assume that the nodes have no identifiers, but that instead, the computation starts with an initial valid vertex coloring. A node can \textbf{broadcast} a \textbf{single} message of \textbf{unbounded} size to its neighbors and receives the \textbf{set of messages} sent to it by its neighbors. That is, if two neighbors of a node $v\in V$ send the same message to $v$, $v$ will receive this message only a single time; without any further knowledge, $v$ cannot know whether a received message was sent by only one or more than one neighbor.
Neighborhood graphs have been essential in the proof of lower bounds for distributed coloring algorithms, e.g., [Linial 1992; Kuhn, Wattenhofer 2006]. Our proof analyzes the recursive structure of the neighborhood graph of the respective model to devise an $\Omega(\Delta^{\frac{1}{3}-\frac{\eta}{3}})$ lower bound on the runtime for any distributed $O(\Delta^{1+\eta})$-graph coloring algorithm.
Furthermore, we hope that the proof technique improves the understanding of neighborhood graphs in general and that it will help towards finding a lower (runtime) bound for distributed graph coloring in the standard LOCAL-model. Our proof technique works for one-round algorithms in the standard LOCAL-model and provides a simpler and more intuitive proof for an existing $\Omega(\Delta^2)$ lower bound proven in [Kuhn 2009].
- Optimal Consistent Network Updates in Polynomial Time
Pavol Cerny, Nate Foster, Nilesh Jagnik and Jedidiah McClurg
Abstract:
Software-defined networking (SDN) allows operators to control the behavior of a network by programatically managing the forwarding rules installed on switches. However, as is common in distributed systems, it can be difficult for them to ensure that certain consistency properties are preserved during periods of reconfiguration. Per-packet consistency, a widely accepted notion of consistency, requires every packet to be forwarded using the new configuration or the old configuration, but not a mixture of the two. If switches can be updated in some (partial) order which guarantees that per-packet consistency is preserved, we call this order a consistent order update. In particular, switches that are incomparable in this order can be updated in parallel. We call a consistent order update optimal if it allows maximal parallelism. This paper presents a polynomial-time algorithm for finding an optimal consistent order update. This contrasts with other recent results in the literature, which show that for other classes of properties (e.g., loop-freedom and waypoint enforcement), the optimal update problem is NP-complete.
- Distributed Construction of Purely Additive Spanners
Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz and Amir Yehudayoff
Abstract:
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts.
We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.
- Optimal Fair Computation
Rachid Guerraoui and Jingjing Wang
Abstract:
A computation scheme among n parties is fair if no party obtains the computation result unless all other n-1 parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party.
We prove, for the first time, a tight lower bound on the message complexity of optimistic fair computation for n parties among which n-1 can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.
- Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
Bernhard Haeupler, Taisuke Izumi and Goran Zuzic
Abstract:
We show that many distributed network optimization problems can be solved much more efficiently in structured and topologically simple networks. It is known that solving essentially any global network optimization problem in a general network requires $\Omega(\sqrt{n})$ rounds in the CONGEST model, even if the network diameter is small, e.g., logarithmic. Many networks of interest, however, have more structure which allows for significantly more efficient algorithms. Recently Ghaffari, Haeupler, Taisuke and Zuzic [SODA’16,PODC’16] introduced low-congestion shortcuts as a suitable abstraction to capture this phenomenon. In particular, they showed that graphs with diameter $D$ embeddable in a genus $g$ surface have $\tilde{O}(gD)$ shortcuts and that these shortcuts lead to $\tilde{O}(g D)$ round algorithms for MST, min-cut and other problems.
We generalize these results by showing that $k$-well-separated networks and networks with bounded pathwidth or treewidth $k$ allow for good $O(k D \log n)$ low-congestion shortcuts leading to near optimal $O(k D \polylog(n))$ distributed optimization algorithms. We also improve the dependence on the genus $g$ from $\tilde{O}(gD)$ to $\tilde{O}(\sqrt{g}D)$. Lastly, we prove lower bounds which show that the dependence on $k$ and $g$ in our shortcuts is optimal. Overall, this significantly refines and extends the understanding of how the complexity of distributed optimization problems depends on the network topology.
- Anonymity-Preserving Failure Detectors
Zohir Bouzid and Corentin Travers
Abstract:
The paper investigates the consensus problem in anonymous, failures prone and asynchronous shared memory systems. It introduces a new class of failure detectors, called anonymity-preserving failures detectors suited to anonymous systems. As its name indicates, a failure detector in this class cannot be relied upon to break anonymity. For example, the anonymous perfect detector AP , which gives at each process an estimation of the number of processes that have failed belongs to this class.
The paper then determines the weakest failure detector among this class for consensus. This failure detector, called C, may be seen as a loose failures counter: (1) after a failure occurs, the counter is eventually incremented, and (2) when at least two processes do not fail, it eventually stabilizes. Finally, the paper also introduces failure detector C_k , a simple generalization of C and shows that it can be used to solve k-set-agreement, a generalization of consensus in which up to k distinct values may be decided.
- Certified Universal Gathering in R2 for Oblivious Mobile Robots
Pierre Courtieu, Lionel Rieg, Sebastien Tixeuil and Xavier Urbain
Abstract:
We present a unified formal framework for expressing mobile robots models, protocols, and proofs, and devise a protocol design/proof methodology dedicated to mobile robots that takes advantage of this formal framework. As a case study, we present the first formally certified protocol for oblivious mobile robots evolving in a two-dimensional Euclidean space. In more details, we provide a new algorithm for the problem of universal gathering mobile oblivious robots (that is, starting from any initial configuration that is not bivalent, using any number of robots, the robots reach in a finite number of steps the same position, not known beforehand) without relying on a common orientation nor chirality. We give very strong guaranties on the correctness of our algorithm by proving formally that it is correct, using the Coq proof assistant.
This result demonstrates both the effectiveness of the approach to obtain new algorithms that use as few assumptions as necessary, and its manageability since the amount of developed code remains human readable.
- Non-Local Probes Do Not Help with Many Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina and Jukka Suomela
Abstract:
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.
- Are Byzantine Failures Really Different From Crash Failures?
Damien Imbs, Michel Raynal and Julien Stainer
Abstract:
The BG-simulation is a powerful reduction algorithm designed for asynchronous read/write crash-prone systems. It allows a set of $(t+1)$ asynchronous sequential processes to wait-free simulate (i.e., despite the crash of up to $t$ of them) an arbitrary number $n$ of processes under the assumption that at most $t$ of them may crash. The BG simulation shows that, in read/write systems, the crucial parameter is not the number $n$ of processes, but the upper bound $t$ on the number of process crashes.
The paper extends the concept of BG simulation to asynchronous message-passing systems prone to Byzantine failures. Byzantine failures are the most general type of failure: a faulty process can exhibit any arbitrary behavior. Because of this, they are also the most difficult to analyze and to handle algorithmically. The main contribution of the paper is a signature-free reduction of Byzantine failures to crash failures. Assuming $t<\min(n’,n/3)$, the paper presents an algorithm that simulates a system of $n’$ processes where up to $t$ may crash, on top of a basic system of $n$ processes where up to $t$ may be Byzantine. While topological techniques have been used to relate the computability of Byzantine failure-prone systems to that of crash failure-prone ones, this simulation is the first, to our knowledge, that establishes this relation directly, in an algorithmic way.
In addition to extending the basic BG simulation to message-passing systems and failures more severe than process crashes, being modular and direct, this simulation provides us with a deeper insight in the nature and understanding of crash an Byzantine failures in the context of asynchronous message-passing systems. Moreover, it also allows crash-tolerant algorithms, designed for asynchronous read/write systems, to be executed on top of asynchronous message-passing systems prone to Byzantine failures.
- Sublinear-Space Distance Labeling using Hubs
Pawel Gawrychowski, Adrian Kosowski and Przemyslaw Uznanski
Abstract:
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node $u$ stores its distance to all nodes from an appropriately chosen set of hubs $S(u) \subseteq V$. For a queried pair of nodes $(u,v)$, the length of a shortest $u-v$-path passing through a hub node from $S(u)\cap S(v)$ is then used as an upper bound on the distance between $u$ and $v$.
We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most $n$ nodes and average degree $\Delta$, the tradeoff between label bit size $L$ and query decoding time $T$ for our approach is given by $L = O(n \log \log_\Delta T / \log_\Delta T)$, for any $T \leq n$. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant $\Delta$, we can achieve any $T=\omega(1)$ while maintaining $L=o(n)$), and it also provides an improvement in terms of label size with respect to previous slower approaches.
By using similar techniques, we then present a $2$-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve the same label size-time tradeoff $L = O(n \log^2 \log T / \log T)$, for any $T \leq n$. To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any $T=\omega(1)$ is sufficient). We believe all of our techniques are of independent value and provide a desirable simplification of previous approaches.
- Online Balanced Repartitioning
Chen Avin, Andreas Loukas, Maciej Pacut and Stefan Schmid
Abstract:
This paper initiates the study of the fundamental balanced graph partitioning problem in the online setting. The input to the, so-called, online Balanced RePartitioning (BRP) problem is an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time. The objective is to dynamically partition the nodes into L clusters, each of size k, at a minimum cost. Every communication request needs to be served: if the communicating nodes are located in the same cluster, the request is served locally, at cost 0; if the nodes are located in dierent clusters, the request is served remotely using inter-cluster communication, at cost 1. The partitioning can be updated dynamically (i.e., repartitioned), by migrating nodes between clusters at cost per node migration. The goal is to devise online algorithms which nd a good trade-o between the communication and the migration cost while maintaining partitions which minimize the number of inter-cluster communications. BRP features interesting connections to other well-known online problems. In particular, we show that scenarios with L = 2 generalize online paging, and scenarios with k = 2 constitute a novel online version of maximum matching. We consider settings both with and without cluster-size augmentation. Somewhat surprisingly (and unlike online paging), we prove that any deterministic online algorithm has a competitive ratio of at least k, even with augmentation. Our main technical contribution is an O(k log k)-competitive deterministic algorithm for the setting with (constant) augmentation. For the case of matching (k = 2), we present a constant competitive algorithm that does not rely on augmentation. We believe that our model finds interesting applications, e.g., in the context of datacenters, where virtual machines need to be dynamically embedded on a set of servers: A server can only host a small number of virtual machines, and machine migrations are possible, but costly.
- Lower bound on the step complexity of obstruction-free consensus
Hagit Attiya, Ohad Ben-Baruch and Danny Hendler
Abstract:
Obstruction-free consensus, ensuring that a process running solo will eventually terminate, is at the core of practical ways to solve consensus, e.g., by using randomization or failure detectors. An obstruction-free consensus algorithm may not terminate in many executions, but it must terminate whenever a process runs solo. Such an algorithm can be evaluated by its solo step complexity, which bounds the worst case number of steps taken by a process running alone, from any configuration, until it decides.
This paper presents a lower bound of Omega(log n) on the solo step complexity of obstruction-free binary anonymous consensus. The proof constructs a sequence of executions in which more and more distinct variables are about to be written to, and then uses the backtracking covering technique to obtain a single execution in which many variables are accessed.
- Opacity vs TMS2: Expectations and Reality
Sandeep Hans, Ahmed Hassan, Roberto Palmieri, Sebastiano Peluso and Binoy Ravindran
Abstract:
Most of the popular Transactional Memory (TM) algorithms are known to be safe because they satisfy opacity, the well-known correctness criterion for TM algorithms. Recently, it has been shown that they are even more conservative, and that they satisfy TMS2, a strictly stronger property than opacity. This paper investigates the theoretical and practical implications of relaxing those algorithms in order to allow histories that are not TMS2. In particular, we present four impossibility results on TM implementations that are not TMS2 and are either opaque or strict serializable, and one practical TM implementation that extends TL2, a high-performance state-of-the-art TM algorithm, to allow non-TMS2 histories. By matching our theoretical findings with the results of our performance evaluation, we conclude that designing and implementing TM algorithms that are not TMS2, but safe, has inherent costs that limit any possible performance gain.
- On Composition and Implementation of Sequential Consistency
Matthieu Perrin, Matoula Petrolia, Achour Mostéfaoui and Claude Jard
Abstract:
Linearizability and sequential consistency are two valuable abstractions for shared objects. They both require that all operations invoked on an object appear as if they were executed sequentially by a unique process. Unlike linearizability, sequential consistency is not composable: using two sequentially consistent objects in a single program does not ensure that the execution of the program is sequentially consistent. For this reason, linearizability has received much more attention than sequential consistency so far.
However, sequential consistency is weaker than linearizability, leaving room for implementation improvements that are not possible for linearizability. Indeed, it has been proved that, to implement a linearizable shared memory in synchronous message-passing systems, it is necessary to wait for a time proportional to the latency of the network for both read and write operations, while waiting during read operations or during write operations is sufficient for sequential consistency.
This paper extends this result to crash-prone asynchronous systems. We propose a distributed algorithm that builds a sequentially consistent shared memory abstraction on top of an asynchronous message passing system where less than half of the processes can experience crash failures. This abstraction consists of an array of single-writer/multi-reader (one register per process) provided with a snapshot operation. We prove that, it is only necessary to wait when a read/snapshot is immediately preceded by a write on the same process.
We also show that sequential consistency is composable in some cases commonly encountered. The first example concerns objects that would be linearizable if they were implemented on top of a linearizable memory; we prove that they become sequentially consistent if they are implemented on top of a sequential memory while remaining composable. The second case concerns round-based algorithms, where each object is only accessed within one round.
- k-Abortable Objects: Progress under High Contention
Naama Ben-David, David Yu Cheng Chan, Vassos Hadzilacos and Sam Toueg
Abstract:
One of the challenges in the design of concurrent data structures is choosing the best liveness property to implement: there is often a tradeoff between the strength of the progress guarantees one wants and the efficiency and simplicity of the algorithm. Wait-freedom guarantees that all processes in the system make progress, but wait-free implementations are often complicated and inefficient. Lock-freedom permits simpler and more efficient algorithms, but it only guarantees that a single process makes progress; a guarantee that might be too weak in some situations. A parametrized liveness property that spans the range between wait-freedom and lock-freedom, called k-lock-freedom [5], guarantees that at least k processes make progress. With k-lock-freedom, however, under continuous high contention a process may get stuck forever, i.e., it may apply an operation to an object and never return. In this paper, we propose objects that can easily implement k-lock-free objects, and always return control. Specifically, we define k-abortable objects, the first kind of abortable objects [2, 6] that guarantee some degree of progress even under high contention. The definition is simple and natural: intuitively, an operation on a k-abortable object can abort only if k operations from distinct processes succeed during the execution of the aborted operation. We first show that wait-free k-abortable objects can easily implement k-lock-free objects. We then give an efficient universal construction for wait-free k-abortable objects shared by n processes that takes only O(k) steps per operation. For k = o(log n), this beats the well-known lower bound of O(log n) steps per operation for universal constructions of wait-free objects [10]. Thus, in general, wait-free k-abortable objects are more efficient than their wait-free non-abortable counterparts when k = o(log n). Since every wait-free k-abortable object can implement its k-lock-free counterpart, our universal construction also provides a universal construction for k-lock-free objects. Prior to the present paper, for k > 1, there was no implementation of any k-lock-free object that was not also wait free. Finally, we give a O(log k)-steps lower bound for universal constructions of k-abortable objects shared by n = k processes.
- Linearizability of Persistent Memory Objects under a Full-System-Crash Failure Model
Joseph Izraelevitz, Hammurabi Mendes and Michael Scott
Abstract:
It is expected that nonvolatile, byte-addressable memory (NVM) will soon be commonplace. However, registers and caches are expected to remain transient. In the event of a power failure, NVM content will be preserved, but data stored in the cache and processor will be lost. Since main memory is customarily seen through the filter of current cache contents, data must be carefully managed in NVM to ensure consistency in the wake of a crash.
This paper provides a theoretical and practical framework for correct data structures on a machine with both transient and persistent state. In contrast to certain prior work, but in keeping with “real world” systems, we assume a full-system failure model, in which all transient state (of all processes) is lost on a crash. We introduce the notion of durable linearizability to govern the safety of concurrent objects under this failure model and a corresponding relaxed, buffered variant which ensures that the persistent state in the event of a crash is consistent but not necessarily up to date.
At the implementation level, we present a new memory persistency model, explicit epoch persistency, that builds upon and generalizes prior work. Our model captures both hardware buffering and fully relaxed consistency, and subsumes both existing and proposed instruction set architectures. Using the persistency model, we present an automated transform to convert any linearizable, nonblocking concurrent object into one that is also durably linearizable. We also present a design pattern, analogous to linearization points, for the construction of other, more optimized objects. Finally, we discuss generic optimizations that may improve performance while preserving both safety and liveness.
- Buffer Size for Routing Limited-Rate Adversarial Traffic
Avery Miller and Boaz Patt-Shamir
Abstract:
We consider the slight variation of the adversarial queuing theory model, in which an adversary injects packets with routes into the network subject to the following constraint: For any link $e$, the total number of packets injected in any time window $[t,t’)$ and whose route contains $e$, is at most $\rho(t’-t)+\sigma$, where $\rho$ and $\sigma$ are non-negative parameters. Informally, $\rho$ bounds the long-term rate of injections and $\sigma$ bounds the “burstiness” of injection: $\sigma=0$ means that the injection is as smooth as it can be.
It is known that greedy scheduling of the packets (under which a link is not idle if there is any packet ready to be sent over it) may result in $\Omega(n)$ buffer size even on an $n$-line network and very smooth injections ($\sigma=0$). In this paper we propose a simple non-greedy scheduling policy and show that, in a tree where all packets are destined at the root, no buffer needs to be larger than $\sigma+2\rho$ to ensure that no overflows occur, which is optimal in our model. The rule of our algorithm is to \emph{forward a packet only if its next buffer is completely empty}. The policy is centralized: in a single step, a long “train” of packets may progress together. We show that in some sense central coordination is required, by presenting an injection pattern with $\sigma=0$ for the $n$-node line that results in $\Omega(n)$ packets in a buffer if local control is used, even for the more sophisticated “downhill” algorithm, which forwards a packet only if its next buffer is less occupied than its current one.
- Distributed Testing of Excluded Subgraphs
Pierre Fraigniaud, Ivan Rapaport, Ville Salo and Ioan Todinca
Abstract:
We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangles. Hence, in particular, testing whether a graph is K4-free, and testing whether a graph is C4-free can be done in a constant number of rounds (where Kk denotes the k-node clique, and Ck denotes the k-node cycle). On the other hand, we show that testing Kk-freeness and Ck-freeness for k > 4 appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node subgraph H. We prove that both DFS and BFS testers fail to test Kk-freeness and Ck-freeness in a constant number of rounds for k > 4.
- How to Discreetly Spread a Rumor in a Crowd
Mohsen Ghaffari and Calvin Newport
Abstract:
In this paper, we study PUSH-PULL style rumor spreading algorithms in the {\em mobile telephone model}, a variant of the classical {\em telephone model} in which each node can participate in at most one connection per round; i.e., you can no longer have multiple nodes pull information from the same source in a single round. Our model also includes two new parameterized generalizations: (1) the network topology can undergo a bounded rate of change (for a parametrized rate that spans from no changes to changes in every round); and (2) in each round, each node can advertise a bounded amount of information to all of its neighbors before connection decisions are made (for a parameterized number of bits that spans from no advertisement to large advertisements). We prove that in the mobile telephone model with no advertisements and no topology changes, PUSH-PULL style algorithms perform poorly with respect to a graph’s vertex expansion and graph conductance as compared to the known tight results in the classical telephone model. We then prove, however, that if nodes are allowed to advertise a single bit in each round, a natural variation of PUSH-PULL terminates in time that matches (within logarithmic factors) this strategy’s performance in the classical telephone model—even in the presence of frequent topology changes. We also analyze how the performance of this algorithm degrades as the rate of change increases toward the maximum possible amount. We argue that our model matches well the properties of emerging peer-to-peer communication standards for mobile devices, and that our efficient PUSH-PULL variation that leverages small advertisements and adapts well to topology changes is a good choice for rumor spreading in this increasingly important setting.
- Depth of a random binary search tree with concurrent insertions
James Aspnes and Eric Ruppert
Abstract:
Shuffle a deck of n cards numbered 1 through n. Deal out the first c cards into a hand, and then repeat the processes of choosing one of the cards from the hand, inserting it into a binary search tree, and then replacing it with the next card from deck (or no card, if the deck is empty). When the player finally runs out of cards, how deep can the search tree be?
This problem is motivated by concurrent insertions by c processes into a randomized binary search tree, where the order of insertions is controlled by an adversary that can delay individual processes. We show that an adversary that uses any strategy based on comparing keys cannot obtain an expected average depth greater than O(c + log n). However, the adversary can obtain an expected tree height of O(c log n), using a simple strategy of always playing the largest available card.
- Priority Mutual Exclusion: Specification and Algorithm
Chien-Chung Huang and Prasad Jayanti
Abstract:
Mutual exclusion is a fundamental problem in distributed computing. In one well known variant of this problem, which we call {\em priority mutual exclusion}, processes have priorities and the requirement is that, whenever the critical section becomes vacant, the next occupant should be the process that has the highest priority among the waiting processes. Instead of first capturing this vague, but intuitively appealing requirement by a rigorously specified condition, earlier research rushed into proposing algorithms. Consequently, as we explain in the paper, none of the existing algorithms meet the reasonable expectations we would have of an algorithm that claims to respect process priorities. This paper fixes this situation by rigorously specifying the priority mutual exclusion problem and designing an efficient algorithm for it. Our algorithm supports an arbitrary number of processes and, when configured to support $m$ priority levels ($m$ can be any natural number), the algorithm has $O(m)$ RMR complexity on both DSM and CC machines. It is noteworthy that the algorithm’s RMR complexity is independent of the number of processes.
- Information Spreading in Dynamic Networks under Oblivious Adversaries
John Augustine, Chen Avin, Mehraneh Liaee, Gopal Pandurangan and Rajmohan Rajaraman
Abstract:
We study the problem of all-to-all information exchange, also known as gossip, in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network remains connected at all times. In the gossip problem, there are $n$ tokens arbitrarily distributed among the $n$ network nodes, and the goal is to disseminate all the $n$ tokens to every node in the network. Our focus is on token-forwarding algorithms for gossip, which do not manipulate tokens in any way other than storing, copying, and forwarding them. Gossip can be completed in linear time in any static network, but an important and basic open question for dynamic networks is the existence of a distributed protocol that can do significantly better than an easily achievable bound of $O(n^2)$ rounds.
In previous work, it has been shown that under adaptive adversaries —those that have full knowledge and control of the topology in every round and also have knowledge of the distributed protocol including its random choices— every token forwarding algorithm requires $\Omega(n^2/log n)$ rounds to complete. In this paper, we study oblivious adversaries, which are similar to adaptive adversaries with a crucial difference— they are oblivious to the random choices made by the protocol. We consider RandDiff, a natural distributed algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. Previous work has shown that starting from a distribution in which each node has a random constant fraction of the tokens, RandDiff completes in O(n polylog(n)) rounds. In contrast, we show that a polynomial slowdown is inevitable under more general distributions: we present an $\tilde{\Omega}(n^{3/2}) lower bound for RandDiff under an oblivious adversary. We also present an $\tilde{\Omega}(n^{4/3}) lower bound for a class of randomized distributed algorithms— symmetric knowledge-based algorithms— in which nodes make token transmission decisions based entirely on the sets of tokens they possess over time. On the positive side, we present a centralized algorithm that completes gossip in $\tilde{O}(n^{3/2}) rounds with high probability, under any oblivious adversary.
Our results are a step towards understanding the true complexity of information spreading in dynamic networks under oblivious adversaries.
- Non-Bayesian Learning in the Presence of Byzantine Agents
Lili Su and Nitin Vaidya
Abstract:
This paper addresses the problem of non-Bayesian learning over multi-agent networks, where agents repeatedly collect partially informative observations about an unknown state of the world, and try to collaboratively learn the true state. This problem finds its application in the opinion formation process in social networks. We focus on the impact of the adversarial agents on the performance of consensus-based non-Bayesian learning. In particular, we consider the scenario where an unknown subset of agents suffer Byzantine faults — agents suffering Byzantine faults may behave arbitrarily. Our goal is to design an algorithm that enables the non-faulty agents collaboratively learn the true state through local information exchange.
The existing non-Bayesian learning algorithms are not robust to Byzantine agents, since the malicious messages sent by the Byzantine agents are indiscriminatingly utilized in the local belief updates. On the other hand, the incorporation of Byzantine consensus is non-trivial, since the effective communication networks are dependent on the all the random local observations, making it non-trivial to adapt analysis of previous algorithms to our setting.
We propose an update rule wherein each agent updates its local beliefs as (up to normalization) the product of (1) the likelihood of the cumulative private signals and (2) the weighted geometric average of the beliefs of its incoming neighbors and itself (using Byzantine consensus). Under mild assumptions on the underlying network structure and the global identifiability of the network, we show that all the non-faulty agents asymptotically agree on the true state almost surely. Our proposed algorithm may be of independent interest for the failure-free setting as well, where every agent is reliable and collaborative.
- Asynchronous Computability Theorems for t-Resilient Systems
Vikram Saraph, Maurice Herlihy and Eli Gafni
Abstract:
A task is a coordination problem where processes start with private inputs, communicate with one another, and then halt with private outputs. A protocol that solves a task is t- resilient if it tolerates halting failures by t or fewer processes. The t-resilient asynchronous computability theorem stated here characterizes the tasks that have t-resilient protocols in a shared-memory model. This result generalizes the prior (wait-free) asynchronous computability theorem of Herlihy and Shavit to a broader class of failure models, and requires introducing several novel concepts.
- Upper Bounds for Boundless Tagging with Bounded Objects
Zahra Aghazadeh and Philipp Woelfel
Abstract:
A fundamental technique used in the design of shared memory algorithms is tagging, where registers or other shared objects get augmented with additional values, called tags. Under the assumption that shared objects can store arbitrary large values, distinct tags can easily be obtained by incrementing unbounded sequence numbers. However, often it is desirable, in theory and practice, to rely only on bounded objects. Naturally, this requires bounding tags as well. Often, bounded timestamp systems are used, but they have high time complexity and require base objects of size \Omega(n) bits for systems with n processes (Israeli and Li 1987, Dolev and Shavit 1997). In cases, where no ordering relation between tags is needed, ad-hoc solutions for bounding tags have been used (see e.g. Jayanti and Petrovic, 2003) in order to reduce the time and object size complexity, but these techniques have not been studied systematically.
In this paper we fill this gap by providing a framework for tagging, and proving upper bounds for the complexity of this problem. We define new types that allow processes to generate tags infinitely often, write and read them to a number of objects, use them safely, and release them when they are not needed any more. We present asymptotically optimally time efficient implementations of those types from objects of bounded size. In particular, contrary to bounded timestamps, which require objects of size \Omega(n) (Israeli and Li 1987) and whose maintenance operations have generally at least linear step complexity in known implementations (see e.g. Dwork and Waarts, 1992), our tags need only objects of logarithmic size, and all important operations can be performed in constant step complexity.
In addition to the straightforward applications that use tags directly, our implementations can also be used for memory reclamation in a number of algorithms, such as those based on single compare-and-swap universal or read-copy-update (see e.g. Alistarh, Censor-Hillel and Shavit, 2014). In several use cases, this allows search methods to be executed wait-free and in constant step complexity, where other memory reclamation techniques, such as Hazard Pointers (Michael 2004) inherently yield lock-freedom for those methods.
- Brief Announcements: Local Distributed Verification
Alkida Balliu, Gianlorenzo D’Angelo, Pierre Fraigniaud and Dennis Olivetti
Abstract:
In the framework of distributed network computing, it is known that, for every network predicate, each network configuration that satisfies this predicate can be proved using distributed certificates which can be verified locally. However, this requires to leak information about the identities of the nodes in the certificates, which might not be applicable in a context in which privacy is desirable. Unfortunately, it is known that if one insists on certificates independent of the node identities, then not all network predicates can be proved using distributed certificates that can be verified locally. In this paper, we prove that, for every network predicate, there is a distributed protocol satisfying the following two properties: (1) for every network configuration that is legal w.r.t. the predicate, and for any attempt by an adversary to prove the illegality of that configuration using distributed certificates, there is a locally verifiable proof that the adversary is wrong, also using distributed certificates; (2) for every network configuration that is illegal w.r.t. the predicate, there is a proof of that illegality, using distributed certificates, such that no matter the way an adversary assigns its own set of distributed certificates in an attempt to prove the legality of the configuration, the actual illegality of the configuration will be locally detected. In both cases, the certificates are independent of the identities of the nodes. These results are achieved by investigating the so-called local hierarchy.
- Brief Announcements: Optimal Implementations of Large Single-Writer Registers
Yuanhao Wei and Tian Ze Chen
Abstract:
We present two algorithms for simulating an $\ell$-bit single-writer register from $k$-bit single-writer registers, for any $k \geq 1$. Our first algorithm has optimal step complexity $\Theta(\ell/k)$ for both $\proc{Read}$ and $\proc{Write}$, which is optimal. It uses $\Theta(4^{\ell-k})$ registers. If $\ell \leq \lceil (\log_2{} n)/2\rceil$, where $n$ is the number of readers, this is $O(n/4^k)$. An interesting feature of the algorithm is that $\proc{Read}$ operations do not write to shared variables. Our second algorithm has $\Theta(\ell/k + (\log{}n)/k)$ step complexity for both $\proc{Read}$ and $\proc{Write}$, but uses only $\Theta(n \ell/k + n(\log{}n)/k)$ registers. For $\ell > \lceil ( \log_2{} n)/2\rceil$, this algorithm has optimal step complexity and uses $\Theta(n \ell/k)$ registers. Combining both algorithms gives an implementation with optimal step complexity using $\Theta(n \ell/k)$ space for any $1 \leq k < \ell$.
- Brief Announcements: Deterministic MST Sparsification in the Congested Clique
Janne H. Korhonen
Abstract:
We give a simple deterministic constant-round algorithm in the congested clique model for reducing the number of edges in a graph to $n^{1+\varepsilon}$ while preserving the minimum spanning forest, where $\varepsilon > 0$ is any constant. This implies that in the congested clique model, it is sufficient to improve MST and other connectivity algorithms on graphs with slightly superlinear number of edges to obtain a general improvement. As a byproduct, we also obtain a simple alternative proof showing that MST can be computed deterministically in $O(\log \log n)$ rounds.
- Brief Announcement: Symmetricity in 3D-space — Characterizing Formable Patterns by Synchronous Mobile Robots
Yukiko Yamauchi, Taichi Uehara and Masafumi Yamashita
Abstract:
We investigate the pattern formation problem that requires a swarm of autonomous mobile robots to form a given target pattern in the three-dimensional Euclidean space (3D-space). The robots are anonymous and synchronously execute a common algorithm. Hence the set of target patterns that the robots can form depends on the symmetry among the robots, more specifically, the rotational symmetry of their initial configuration (i.e., the positions of the robots). We define the symmetricity $\varrho(P)$ of configuration $P$ in 3D-space as the set of rotation groups each of which acts on $P$ and whose rotation axes do not contain any robot. This definition means that $\varrho(P)$ may consist of proper subgroups of the rotational symmetry of $P$, and we show that the robots can reduce their rotational symmetry to an element of $\varrho(P)$ by a deterministic distributed algorithm. Then we show that synchronous robots in 3D-space can form a target pattern $F$ from an initial configuration $P$ if and only if $\varrho(P) \subseteq \varrho(F)$. We give a pattern formation algorithm for solvable instances that does not need any local memory at each robot.
- Brief Announcements: Mending the Big-Data Missing Information
Hadassa Daltrophe, Shlomi Dolev and Zvi Lotker
Abstract:
Consider a high-dimensional data set, in which for every data-point there is incomplete information. Each object in the data set represents a real entity, which is described by a point in high-dimensional space. We model the lack of information for a given object as an affine subspace in $\mathbb{R}^d$ whose dimension $k$ is the number of missing features.
Our goal in this study is to find clusters of objects where the main problem is to cope with partial information and high dimension. Assuming the data set is separable, namely, its emergence from clusters that can be modeled as a set of disjoint ball in $\mathbb{R}^d$, we develop a simple data clustering algorithm. Our suggested algorithm use the affine subspaces minimum distance and calculates pair-wise projection of the data achieving poly-logarithmic time complexity. We use probabilistic considerations to prove the algorithm’s correctness. These probabilistic results are of independent interest, and can serve to better understand the geometry of high dimensional objects.
- Brief Announcements: Set-Consensus Collections are Decidable
Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni and Petr Kuznetsov
Abstract:
A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model of computation is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for a restricted class of models and tasks. We show that the question of whether a collection $C$ of \emph{$(j,\ell)$-set consensus} tasks, for various $\ell$ (the number of processes that can invoke the task) and $j$ (the number of distinct outputs the task returns), can be used by $n$ processes to solve wait-free $k$-set consensus is decidable. Moreover, we provide a simple $O(n^2)$ decision algorithm, based on a dynamic programming solution to the Knapsack problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participants, achieves the best level of agreement that is possible to achieve using $C$. Overall, this gives us a complete characterization of a model equipped with a collection of set-consensus tasks through its \emph{set-consensus power}. Therefore, the question of determining the relative power of models defined by set-consensus collections is decidable and, moreover, has an efficient solution. We conjecture that any “reasonable” shared-memory model can be charaterized by its set-consensus power.
- Brief Announcements: A Log*-Time Local Approximation Scheme for Bounded Genus Graphs
Saeed Akhoondian Amiri and Stefan Schmid
Abstract:
This paper shows that the results by Czygrinow et al. (DISC 2008) and Amiri et al. (PODC 2016) can be combined to obtain a O(log* n)-time local and deterministic approximation scheme for Minimum Dominating Sets on bounded genus graphs.
- Brief Announcements: On the Space Complexity of Conflict Detector Objects
Claire Capdevielle, Colette Johnen and Alessia Milani
Abstract:
A conflict detector is a one-shot shared-memory object introduced by Aspnes and Ellen in \cite{AE14}. It supports a single operation, $check(v)$, with input $v$ from a set of values and returns $true$ (to indicate a conflict) or $false$ (to indicate no conflicts). A conflict detector has the following two properties: i) in any execution that contains a $check(v)$ operation and a $check(v’)$ operation with $v\neq v’$, at least one of these two operations returns true; ii) in any execution in which all check operations have the same input value, they all return false.
The conflict detector was introduced to prove tight bounds on the individual step complexity of wait-free adopt-commit objects implemented using multi-writer registers. Adopt-commit objects can be used to implement round-based protocols for set-agreement and consensus \cite{G98}. Aspnes and Ellen show that we can implement an adopt-commit object using a conflict detector plus a constant number of registers and vice versa. They also show that the individual step complexity of adopt-commit objects and conflict detectors differ by a small additive constant. Being a simpler object we can easier obtain bounds on adopt-commit objects reasoning on conflict detectors.
In this paper we study the space and solo-write complexity of conflict detectors (and then of adopt-commit objects), answering a question left open in the conclusion of \cite{AE14}. The \emph{solo-write complexity} is the maximal number of writes performed in a solo execution of a single $check$ operation, taken over all possible input values. We prove a $\Theta(\min(\sqrt{n},\log{m}/\log{\log{m}}))$ bound on the space and solo-write complexity of a wait-free conflict-detector implemented using multi-writer registers for $n$ anonymous processes and where $m$ is the size of the input values set. Processes are anonymous meaning that they have no identifiers and thus they execute the same program.
- Brief Announcements: Public vs. Private Randomness for Multi-Player Simultaneous Communication
Orr Fischer, Rotem Oshman and Uri Zwick
Abstract:
In simultaneous number-in-hand multi-party communication protocols, we have k players, who each receive a private input, and wish to compute a joint function of their inputs. The players simultaneously send a single message to a referee, who then outputs the value of the function. The cost of the protocol is the total number of bits sent to the referee.
For two players, it is known that giving the players a public (shared) random string is much more useful than private randomness: public-coin protocols can be unboundedly better than deterministic protocols, while private-coin protocols can only give a quadratic improvement on deterministic protocols.
We extend the two-player gap to multiple players, and show that the private-coin communication complexity of a k-player function f is Omega(\sqrt(D(f)) for any k. Perhaps surprisingly, this bound is tight: although one might expect the gap between private-coin and deterministic protocols to scale linearly with k (or nearly so), we show that the All-Equality function, where each player receives n bits of input and the players must determine if their inputs are all the same, can be solved by a private-coin protocol with O(\sqrt(nk)+k) bits, up to polylogarithmic factors. Since All-Equality has deterministic complexity Theta(nk), this shows that sometimes the gap scales only as the square root of the number of players.
- Brief Announcements: Beeping a Maximal Independent Set Fast
Stephan Holzer and Nancy Lynch
Abstract:
We show how to adapt a recent algorithm for computing a Maximal Independent Set by Ghaffari that is stated in the LOCAL model to work in the significantly weaker beeping model of wireless communication, while keeping the same asymptotic runtime. This improves previous work on computing a Maximal Independent in the beeping model.
