OPODIS 2021 - Program

Abstract:A very common optimization technique in Machine Learning is Stochastic Gradient Descent (SGD). SGD can easily be distributed: several workers try to estimate the gradient of a loss function, and a central parameter server gathers these estimates. When all workers behave correctly, the more workers we have, the more accurate the gradient estimate is. We call this the Arbitrary Aggregation Accuracy (AAA) property. However, in practice, some workers may be Byzantine (i.e., have an arbitrary behavior). Interestingly, when a fixed fraction of workers is assumed to be Byzantine (e.g. 20%), no existing aggregation scheme has the AAA property. In this paper, we propose the first aggregation scheme that has this property despite a fixed fraction of Byzantine workers (less than 50%). We theoretically prove this property, and then illustrate it with simulations.

Abstract:This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that $n \geq 4f$ is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.

Abstract:This paper focuses on blockchain finality, which refers to the time when it becomes impossible to remove a block that has previously been appended to the blockchain. Blockchain finality can be deterministic or probabilistic, immediate or eventual. To favor availability against consistency in the face of partitions, most blockchains only offer probabilistic eventual finality: blocks may be revoked after being appended to the blockchain, yet with decreasing probability as they sink deeper into the chain. Other blockchains favor consistency by leveraging the immediate finality of Consensus -- a block appended is never revoked -- at the cost of additional synchronization. The quest for "good" deterministic finality properties for blockchains is still in its infancy, though. Our motivation is to provide a thorough study of several possible deterministic finality properties and explore their solvability. This is achieved by introducing the notion of bounded revocation, which informally says that the number of blocks that can be revoked from the current blockchain is bounded. Based on the requirements we impose on this revocation number, we provide reductions between different forms of eventual finality, Consensus and Eventual Consensus. From these reductions, we show some related impossibility results in presence of Byzantine processes, and provide non-trivial results. In particular, we provide an algorithm that solves a weak form of eventual finality in an asynchronous system in presence of an unbounded number of Byzantine processes. We also provide an algorithm that solves eventual finality with a bounded revocation number in an eventually synchronous environment in presence of less than half of Byzantine processes. The simplicity of the arguments should better guide blockchain designs and link them to clear formal properties of finality.

Abstract:Twins is an effective strategy for generating test scenarios with Byzantine nodes in order to find flaws in Byzantine Fault Tolerant (BFT) systems. Twins finds flaws in the design or implementation of BFT protocols that may cause correctness issues.The main idea of Twins is the following: running twin instances of a node that use correct, unmodified code and share the same network identity and credentials allows to emulate most interesting Byzantine behaviors. Because a twin executes normal, unmodified node code, building Twins only requires a thin wrapper over an existing distributed system designed for Byzantine tolerance. To emulate material, interesting scenarios with Byzantine nodes, it instantiates one or more twin copies of the node, giving the twins the same identities and network credentials as the original node. To the rest of the system, the node and all its twins appear indistinguishable from a single node behaving in a ''questionable'' manner. This approach generates many interesting Byzantine behaviors, including equivocation, double voting, and losing internal state, while forgoing uninteresting behavior scenarios that can be filtered at the transport layer, such as producing semantically invalid messages. Building on configurations with twin nodes, Twins systematically generates scenarios with Byzantine nodes via enumeration over protocol rounds and communication patterns among nodes. Despite this being inherently exponential, one new flaw and several known flaws were materialized by Twins in the arena of BFT consensus protocols. In all cases, protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems. In two of these cases, it took the community more than a decade to discover protocol flaws that Twins would have surfaced within minutes. Additionally, Twins has been incorporated into the continuous release testing process of a production setting (DiemBFT) in which it can execute 44M Twins-generated scenarios daily.

Abstract:Given an undirected, anonymous, port-labeled graph of $n$ memory-less nodes, $m$ edges, and degree $\Delta$, we consider the problem of dispersing $k\leq n$ robots (or tokens) positioned initially arbitrarily on one or more nodes of the graph to exactly $k$ different nodes of the graph, one on each node. The objective is to simultaneously minimize time to achieve dispersion and memory requirement at each robot. If all $k$ robots are positioned initially on a single node, depth first search (DFS) traversal solves this problem in $O(\min\{m,k\Delta\})$ time with $\Theta(\log(k+\Delta))$ bits at each robot. However, if robots are positioned initially on multiple nodes, the best previously known algorithm solves this problem in $O(\min\{m,k\Delta\}\cdot \log \ell)$ time storing $\Theta(\log(k+\Delta))$ bits at each robot, where $\ell\leq k/2$ is the number of multiplicity nodes in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in $O(\min\{m,k\Delta\})$ time with $\Theta(\log(k+\Delta))$ bits at each robot, improving the time bound of the best previously known algorithm by $O(\log \ell)$ and matching asymptotically the single-source DFS traversal bounds. This is the first algorithm for dispersion that is optimal in both time and memory in arbitrary anonymous graphs of constant degree, $\Delta=O(1)$. Furthermore, the result holds in both synchronous and asynchronous settings.

Abstract:We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other, but are endowed with visibility sensors that allow them to see the positions of the other robots. Most of the investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robots unless it is their current node. As a consequence, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

Abstract:Arbitrary Pattern Formation is a fundamental problem in autonomous mobile robot systems. The problem asks to design a distributed algorithm that moves a team of autonomous, anonymous and identical mobile robots to form any arbitrary pattern $F$ given as input. In this paper, we study the problem for robots whose movements can be inaccurate. Our movement model assumes errors in both direction and extent of the intended movement. Forming the given pattern exactly is not possible in this setting. So we require that the robots must form a configuration which is close to the given pattern $F$. We call this the Approximate Arbitrary Pattern Formation problem. With no agreement in coordinate system, the problem is unsolvable, even by fully synchronous robots, if the initial configuration 1) has rotational symmetry and there is no robot at the center of rotation or 2) has reflectional symmetry and there is no robot on the reflection axis. From all other initial configurations, we solve the problem by 1) oblivious, silent and semi-synchronous robots and 2) oblivious, asynchronous robots that can communicate using externally visible lights.

Abstract:Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20] introduced the HYBRID model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with any neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the HYBRID model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with n nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size O(log n) bits in only O(log n) rounds.

Abstract:We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size $n$ of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. Our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, as well as safe, i.e., never update the label assigned to any single agent. We first present a silent and safe labeling protocol that draws labels from the range $[1,2n].$ Both, the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., $O(n \log n)$ w.h.p. and $O(n)$, respectively. Next, we present a generalization of the protocol, where the range of assigned labels is $[1,(1+\varepsilon ) n]$. The generalized protocol requires $O(n \log n / \varepsilon )$ interactions in order to complete the assignment of distinct labels from $[1,(1+\varepsilon ) n]$ to the $n$ agents, w.h.p. It is also silent and safe, and uses $(2+\varepsilon)n+O(n^c)$ states, for any positive $c<1.$ On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is $\ge \frac{n^2}{r+1}$, when the labels range is $1,\dots, n+r<2n.$ Furthermore, we provide a silent and safe protocol which uses only $n+5\sqrt n +O(n^c)$ states, for any $c<1,$ and draws labels from the range $1,\dots,n.$ The expected number of interactions required by the protocol is $O(n^3).$ On the other hand, we show that any silent protocol that produces a valid labeling and is safe with probability $>1-\frac 1n$, uses $\ge n+\sqrt {\frac {n-1} 2} -1$ states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing $n+t<2n$ states the expected number of interactions required to achieve a valid labeling is $\ge \frac{n^2}{t+1}$.

Abstract:In this paper, we focus on graph class identification problems in the population protocol model. A graph class identification problem aims to decide whether a given communication graph is in the desired class (e.g. whether the given communication graph is a ring graph). Angluin et al. proposed graph class identification protocols with directed graphs and designated initial states under global fairness [Angluin et al., DCOSS2005]. We consider graph class identification problems for undirected graphs on various assumptions such as initial states of agents, fairness of the execution, and initial knowledge of agents. In particular, we focus on lines, rings, $k$-regular graphs, stars, trees, and bipartite graphs. With designated initial states, we propose graph class identification protocols for $k$-regular graphs, and trees under global fairness, and propose a graph class identification protocol for stars under weak fairness. Moreover, we show that, even if agents know the number of agents $n$, there is no graph class identification protocol for lines, rings, $k$-regular graphs, trees, or bipartite graphs under weak fairness. On the other hand, with arbitrary initial states, we show that there is no graph class identification protocol for lines, rings, $k$-regular graphs, stars, trees, or bipartite graphs.

Abstract:Let $G$ be a graph on $n$ nodes. In the stochastic population protocol model, a collection of $n$ indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other's states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when $G$ is a \emph{clique}. Specifically, in the clique, these tasks can be solved \emph{fast}, i.e., in $n \operatorname{polylog} n$ pairwise interactions, with high probability, using at most $\operatorname{polylog} n$ states per node. In this work, we consider the more general setting where $G$ is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance $\varphi$, both leader election and exact majority can be solved in $\varphi^{-2} \cdot n \operatorname{polylog} n$ pairwise interactions, with high probability, using at most $\varphi^{-2} \cdot \operatorname{polylog} n$ states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting.

Abstract:Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph: – On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique. – On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard. – On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.

Abstract:Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter and there are relatively few spanner edges between clusters. In this paper, we provide a clustering algorithm that, given $k\geq 2$, can be used to compute a spanner of stretch $2k-1$ and expected size $O(n^{1+1/k})$ in $k$ rounds in the CONGEST model. This improves upon the state of the art (by Elkin, and Neiman [TALG'19]) by making the bounds on both running time and stretch independent of the random choices of the algorithm, whereas they only hold with high probability in previous results. We show how our improvements in the cluster-based spanner constructions directly transfer to applications in constructing synchronizers. Furthermore, for keeping the \emph{total} number of inter-cluster edges small in low diameter decompositions, our clustering algorithm provides the following guarantees. Given $\beta\in (0,1]$, we compute a low diameter decomposition with diameter bound $O\left(\frac{\log n}{\beta}\right)$ such that each edge $e\in E$ is an inter-cluster edge with probability at most $\beta\cdot w(e)$ in $O\left(\frac{\log n}{\beta}\right)$ rounds in the CONGEST model. Again, this improves upon the state of the art (by Miller, Peng, and Xu [SPAA'13]) by making the bounds on both running time and diameter independent of the random choices of the algorithm, whereas they only hold with high probability in previous results.

Abstract:We provide \CONGEST model algorithms for approximating the minimum weighted vertex cover and the maximum weighted matching problem. For bipartite graphs, we show that a $(1+\eps)$-approximate weighted vertex cover can be computed deterministically in $\poly\big(\frac{\log n}{\eps}\big)$ rounds. This generalizes a corresponding result for the unweighted vertex cover problem shown in [Faour, Kuhn; OPODIS '20]. Moreover, we show that in general weighted graph families that are closed under taking subgraphs and in which we can compute an independent set of weight at least $\lambda\cdot w(V)$ (where $w(V)$ denotes the total weight of all nodes) in polylogarithmic time in the \CONGEST model, one can compute a $(2-2\lambda +\eps)$-approximate weighted vertex cover in $\poly\big(\frac{\log n}{\eps}\big)$ rounds in the \CONGEST model. Our result in particular implies that in graphs of arboricity $a$, one can compute a $(2-1/a+\eps)$-approximate weighted vertex cover problem in $\poly\big(\frac{\log n}{\eps}\big)$ rounds in the \CONGEST model. For maximum weighted matchings, we show that a $(1-\eps)$-approximate solution can be computed deterministically in time $2^{O(1/\eps)}\cdot \poly\log n$ in the \CONGEST model. We also provide a randomized algorithm that with arbitrarily good constant probability succeeds in computing a $(1-\eps)$-approximate weighted matching in time $2^{O(1/\eps)}\cdot \poly\log(\Delta W)\cdot \log^* n$, where $W$ denotes the ratio between the largest and the smallest edge weight. Our algorithm generalizes results of [Lotker, Patt-Shamir, Pettie; SPAA '08] and [Bar-Yehuda, Hillel, Ghaffari, Schwartzman; PODC '17], who gave $2^{O(1/\eps)}\cdot \log n$ and $2^{O(1/\eps)}\cdot \frac{\log\Delta}{\log\log\Delta}$-round randomized approximations for the unweighted matching problem. Finally, we show that even in the \LOCAL model and in bipartite graphs of degree $\leq 3$, if $\eps<\eps_0$ for some constant $\eps_0>0$, then computing a $(1+\eps)$-approximation for the unweighted minimum vertex cover problem requires $\Omega\big(\frac{\log n}{\eps}\big)$ rounds. This generalizes a result of [G\"o\"os, Suomela; DISC '12], who showed that computing a $(1+\eps_0)$-approximation in such graphs requires $\Omega(\log n)$ rounds.

Abstract:We prove new bounds on the distributed fractional coloring problem in the \LOCAL model. A fractional $c$-coloring of a graph $G=(V,E)$ is a fractional covering of the nodes of $G$ with independent sets such that each independent set $I$ of $G$ is assigned a fractional value $\lambda_I\in[0,1]$. The total value of all independent sets of $G$ is at most $c$, and for each node $v\in V$, the total value of all independent sets containing $v$ is at least $1$. Equivalently, fractional $c$-colorings can also be understood as multicolorings as follows. For some natural numbers $p$ and $q$ such that $p/q\leq c$, each node $v$ is assigned a set of at least $q$ colors from $\set{1,\dots,p}$ such that adjacent nodes are assigned disjoint sets of colors. The minimum $c$ for which a fractional $c$-coloring of a graph $G$ exists is called the fractional chromatic number $\chi_f(G)$ of $G$. Recently, [Bousquet, Esperet, and Pirot; SIROCCO '21] showed that for any constant $\eps>0$, a fractional $(\Delta+\eps)$-coloring can be computed in $\Delta^{O(\Delta)} + O(\Delta\cdot\log^* n)$ rounds. We show that such a coloring can be computed in only $O(\sqrt{\Delta}\poly \log\Delta + \log^* n)$ rounds. We further show that in $O\big(\frac{\log n}{\eps}\big)$ rounds, it is possible to compute a fractional $(1+\eps)\chi_f(G)$-coloring, even if the fractional chromatic number $\chi_f(G)$ is not known. That is, the fractional coloring problem can be approximated arbitrarily well by an efficient algorithm in the \LOCAL model. For the standard coloring problem, it is only known that an $O\big(\frac{\log n}{\log\log n}\big)$-approximation can be computed in polylogarithmic time in the \LOCAL model. We also show that our distributed fractional coloring approximation algorithm is best possible. We show that in trees, which have fractional chromatic number $2$, computing a fractional $(2+\eps)$-coloring requires at least $\Omega\big(\frac{\log n}{\eps}\big)$ rounds. We finally study fractional colorings of regular grids. In [Bousquet, Esperet, and Pirot; SIROCCO '21], it is shown that in regular grids of bounded dimension, a fractional $(2+\eps)$-coloring can be computed in time $O(\log^* n)$. We show that such a coloring can even be computed in $O(1)$ rounds in the \LOCAL model.

Abstract:One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs. More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring alpha and a target coloring beta, and we want to find a schedule of colorings to reach beta starting from alpha. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication is needed to produce a schedule, and what is the length of this schedule? In the case of interval and chordal graphs, we prove that, if we have less than 2 omega colors, omega being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Delta)log*n) rounds of communication, and for chordal graphs, we need O(omega^2 Delta^2 log n) rounds to get one. Our techniques also improve classic coloring algorithms. Namely, we get omega+1-colorings of interval graphs in O(omega log*n)$ rounds and of chordal graphs in O(omega log n) rounds, which improves on previous known algorithms that use \omega+2 colors for the same running times.

Abstract:We study asynchronous rumor spreading algorithm in dynamic and static graphs. In the asynchronous rumor spreading, for a given underlying graph, each node is equipped with an exponential time clock of rate $1$. When a node's clock ticks, the node calls a random neighbor in order to exchange a rumor, if at least one of them knows it. Assuming a single node knows a rumor, we present a differential equation-based technique to obtain an upper bound for the \emph{spread time} of the algorithm in general dynamic graphs, which is the first time when all nodes get informed with high probability. In particular, we derive an upper bound for the spread time of the algorithm in a discrete version of a geometric mobile network, introduced by Clementi et al. \cite{CMPS11}. In this model, a set of $n$ agents independently performs random walks on a $\sqrt{n}\times \sqrt{n}$ plan and every two agents are able to communicate if they are at Euclidean distance at most $R$, where $f(n)\sqrt{\log n}\le R\le \sqrt{n}$ and $f(n)$ is a slowly growing function in $n$. Here, we show that the algorithm spreads a rumor through the network in $O(\log n+\sqrt{n}/R)$ time, with high probability. Although we only show an upper bound the spread time of the algorithm in a $2$ dimensional space, the framework can be also applied for geometric mobile networks defined over higher dimensional space and other random dynamic evolving networks such as stationary edge-Markovian model. Besides these synchronous and discrete dynamic models, we also consider the spreading time in dynamical Erd\H{o}s-R\'enyi graphs.

Abstract: In distributed verification, our goal is to verify that the network configuration satisfies some desired property, using pre-computed information stored at each network node. This is formally modeled as a \emph{proof labeling scheme}: a prover assigns to each node a \emph{certificate}, and then the nodes exchange their certificates with their neighbors and decide whether to accept or reject the configuration. Subsequent work has shown that in some cases, allowing more rounds of communication---so nodes can communicate further across the network---can yield shorter certificates, trading off the \emph{space} required to store the certificate against the \emph{time} required for verification. In this work we investigate the application of \emph{erasure codes} in time-space tradeoffs for distributed verification. We show that erasure codes yield a simple and explicit scheme for the \emph{uniform} case, where all nodes receive the same certificate: if every node is guaranteed to have at least $b(t)$ nodes in its $t$-neighborhood, then we can save a factor of $b(t-1)$ in the certificate size by using $t$ rounds of communication (previously only a non-explicit construction with slightly worse parameters was known). Next, using our uniform construction, we show that in any graph family that has a balanced edge separator of size $s(n)$ (where $n$ is the size of the graph), we can save a factor of $\tilde{O}(s(n)/t)$ in the certificate size by using $t$ rounds of communication. In particular, this yields a nearly-optimal time-space tradeoff for graphs with constant treewidth and constant degree. Finally, we show that in any graph family that excludes some fixed minor, we can save a factor of $\tilde{O}(\sqrt{t}/\Delta)$ in the certificate size, where $\Delta$ is the maximum degree of the graph.

Abstract:Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph belongs to a given graph class. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds using a new proof technique.

Abstract:Multi-party random number generation is a key building-block in many practical protocols. While straightforward to solve when all parties are trusted to behave correctly, the problem becomes much more difficult in the presence of faults. In this context, this paper presents \textsf{RandSolomon}, a protocol that allows a network of $N$ processes to produce an unpredictable common random number among the non-faulty of them. We provide optimal resilience for partially-synchronous systems where $\lfloor \frac{N-1}{3} \rfloor$ of the participants might behave arbitrarily and, contrary to many solutions, we do not require at any point faulty-processes to be responsive.

Abstract:Given a boolean predicate Pi on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for Pi is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying Pi. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size n of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using node registers on O(log log n) bits in any n-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use $\Omega(\log \log n)$-bit registers in some n-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms.

Abstract:An accountable distributed system provides means to detect deviations of system components from their expected behavior. It is natural to complement fault detection with a reconfiguration mechanism, so that the system could heal itself, by replacing malfunctioning parts with new ones. In this paper, we describe a framework that can be used to implement a large class of accountable and reconfigurable replicated services. We build atop the fundamental lattice agreement abstraction lying at the core of storage systems and cryptocurrencies. Our asynchronous implementation of accountable lattice agreement ensures that every violation of consistency is followed by an undeniable evidence of misbehavior of a faulty replica. The system can then be seamlessly reconfigured by evicting faulty replicas, adding new ones and merging inconsistent states. We believe that this paper opens a direction towards asynchronous "self-healing" systems that combine accountability and reconfiguration.

Abstract:Distributed replication systems based on the replicated state machine model have become ubiquitous as the foundation of modern database systems. To ensure availability in the presence of faults, these systems must be able to dynamically replace failed nodes with healthy ones via dynamic reconfiguration. MongoDB is a document oriented database with a distributed replication mechanism derived from the Raft protocol. In this paper, we present MongoRaftReconfig, a novel dynamic reconfiguration protocol for the MongoDB replication system. MongoRaftReconfig utilizes a logless approach to managing configuration state and decouples the processing of configuration changes from the main database operation log. The protocol’s design was influenced by engineering constraints faced when attempting to redesign an unsafe, legacy reconfiguration mechanism that existed previously in MongoDB. We provide a safety proof of MongoRaftReconfig, along with a formal specification in TLA+. To our knowledge, this is the first published safety proof and formal specification of a reconfiguration protocol for a Raft-based system. We also present results from model checking its safety properties on finite protocol instances. Finally, we discuss the conceptual novelties of MongoRaftReconfig, how it can be understood as an optimized and generalized version of the single server reconfiguration algorithm of Raft, and present an experimental evaluation of how its optimizations can provide performance benefits for reconfigurations.

Abstract:This paper explores the good-case latency of synchronous Byzantine Fault Tolerant (BFT) consensus protocols in the rotating leader setting. We first present a lower bound that relates the latency of a broadcast when the sender is honest and the latency of switching to the next sender. We then present a matching upper bound with a latency of $2\Delta$ ($\Delta$ is the pessimistic synchronous delay) with an optimistically responsive change to the next sender. The results imply that both our lower and upper bounds are tight. We implement and evaluate our protocol and show that our protocol obtains similar latency compared to state-of-the-art stable-leader protocol Sync~HotStuff while allowing optimistically responsive leader rotation.

Abstract:Strong linearizability is a correctness condition conceived to address the inadequacies of linearzability when using implemented objects in randomized algorithms (STOC 2011). Due to its newfound nature, not many strongly linearizable implementations of data structures are known. In particular, very little is known about what can be achieved in terms of strong linearizability with strong primitives that are available in modern systems, such as the compare-and-swap (CAS) operation. This paper kick-starts the research into filling this gap. We show that Harris's linked list (DISC 2001) and Michael and Scott's queue (PODC 1996), two well-known lock-free, linearizable data structures, are not strongly linearizable. In addition, we give modifications to these data structures to make them strongly linearizable while maintaining lock-freedom. The algorithms we describe are the first instances of non-trivial, strongly linearizable data structures of their type not derived by a universal construction.

Abstract:The emergence of systems with non-volatile main memory (NVRAM) increases the need for persistent concurrent objects. Of specific interest are recoverable implementations that, in addition to being robust to crash-failures, are also *detectable*. Detectability ensures that upon recovery, it is possible to infer whether the failed operation took effect or not and, in the former case, obtain its response. This work presents two recoverable detectable fetch&add (FAA) algorithms that are self-implementations, i.e, use only a single fetch&add base object. The algorithms target two different models for recovery: the global-crash model and the individual-crash model. In both algorithms, operations are wait-free when there are no crashes, but the recovery code may block if there are repeated failures. We also prove that in the individual-crash model, there is no lock-free implementation of recoverable and detectable FAA using only read, write and fetch&add primitives.

Abstract:Transactional data structure libraries (TDSL) combine the ease-of-programming of transactions with the high performance and scalability of custom-tailored concurrent data structures. They can be very efficient thanks to their ability to exploit data structure semantics in order to reduce overhead, aborts, and wasted work compared to general-purpose software transactional memory. However, TDSLs were not previously used for complex use-cases involving long transactions and a variety of data structures. In this paper, we boost the performance and usability of a TDSL, towards allowing it to support complex applications. A key idea is \textit{nesting}. Nested transactions create checkpoints within a longer transaction, so as to limit the scope of abort, without changing the semantics of the original transaction. We build a Java TDSL with built-in support for nested transactions over a number of data structures. We conduct a case study of a complex network intrusion detection system that invests a significant amount of work to process each packet. Our study shows that our library outperforms publicly available STMs twofold without nesting, and by up to 16x when nesting is used.

Abstract:Today's applications, in particular, the analytics tasks based on graph algorithms in domains such as blockchains, social networks, biological networks, and several others, demand real-time data updates at high speed. The real-time updates are efficiently ingested if the data structure naturally supports dynamic addition and removal of both edges and vertices. These dynamic updates are best facilitated by concurrency in the underlying data structure. Unfortunately, the current dynamic graph frameworks broadly refurbish the static processing models using approaches such as versioning and incremental computation. Consequently, they carry their original design traits such as high memory footprint and batch processing that do not honor the real-time changes. At the same time, multi-core processors--a natural setting for concurrent data structures--are now commonplace, and the analytics tasks are moving closer to data sources over lightweight devices. Thus, exploring a fresh design approach for real-time graph analytics is significant. This paper reports a novel concurrent graph data structure that provides breadth-first search, single-source shortest-path, and betweenness centrality with concurrent dynamic updates of both edges and vertices. We evaluate the proposed data structure theoretically--by an amortized analysis--and experimentally via a C++ implementation. The experimental results show that (a) our algorithm outperforms the current state-of-the-art by a throughput speed-up of up to three orders of magnitude in several cases, and (b) it offers up to 80x lighter memory-footprint compared to existing counterpart. The experiments include several counterparts: Stinger, Ligra and GraphOne. We prove that the presented concurrent algorithms are non-blocking and linearizable.