Best Paper: Approximating Bipartite Minimum Vertex Cover in the CONGEST model, by Salwa Faour and Fabian Kuhn.
Best Student Paper: Fast Byzantine SGD, by Amine Boussetta, El-Mahdi El-Mhamdi, Rachid Guerraoui, Alexandre Maurer, and Sébastien Rouault.

All times are in Central European Time.

December 14
December 15
December 16
December 14
15:00 16:00
Keynote by Pascal Felber University of Neuchâtel Big Data Processing: Security and Scalability Challenges Abstract
16:15 17:15
Session 1 Dynamic & Radio Networks Chair: Faith Ellen
youtube Haimin Chen, Chaodong Zheng Broadcasting Competitively against Adaptive Adversary in Multi-channel Radio Networks +
Haimin Chen, Nanjing University
Chaodong Zheng, Nanjing University
Abstract: Broadcasting in wireless networks is vulnerable to adversarial jamming. To thwart such behavior, resource competitive analysis is proposed. In this framework, sending, listening, or jamming on one channel for one time slot costs one unit of energy. The adversary can employ arbitrary strategy to disrupt communication, but has a limited energy budget $T$. The honest nodes, on the other hand, aim to accomplish broadcast while spending only $o(T)$. Previous work has shown, in a $C$-channels network containing $n$ nodes, for large $T$ values, each node can receive the message in $\tilde{O}(T/C)$ time, while spending only $\tilde{O}(\sqrt{T/n})$ energy. However, these multi-channel algorithms only work for certain values of $n$ and $C$, and can only tolerate an oblivious adversary.

In this work, we provide new upper and lower bounds for broadcasting in multi-channel radio networks, from the perspective of resource competitiveness. Our algorithms work for arbitrary $n,C$ values, require minimal prior knowledge, and can tolerate a powerful adaptive adversary. More specifically, in our algorithms, for large $T$ values, each node’s runtime is $O(T/C)$, and each node’s energy cost is $\tilde{O}(\sqrt{T/n})$. We also complement algorithmic results with lower bounds, proving both the time complexity and the energy complexity of our algorithms are optimal or near-optimal (within a poly-log factor). Our technical contributions lie in using “epidemic broadcast” to achieve time efficiency and resource competitiveness, and employing coupling techniques in the analysis to handle the adaptivity of the adversary. At the lower bound side, we first derive a new energy complexity lower bound for 1-to-1 communication in the multi-channel setting, and then apply simulation and reduction arguments to obtain the desired result.

youtube Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh Dynamic Byzantine Reliable Broadcast +
Rachid Guerraoui, School of Computer and Communication Sciences, EPFL
Jovan Komatovic, École polytechnique fédérale de Lausanne
Petr Kuznetsov, Telecom ParisTech
Yvonne-Anne Pignolet, DFINITY
Dragos-Adrian Seredinschi, Informal Systems – Lausanne
Andrei Tonkikh, National Research University Higher School of Economics
Abstract: Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: \emph{(i)} we can implement it deterministically in a completely asynchronous environment, unlike stronger primitives like consensus and total-order broadcast, and yet \emph{(ii)} reliable broadcast is powerful enough to implement important applications like payment systems.

The problem we tackle in this paper is that of \emph{dynamic} reliable broadcast, i.e., enabling processes to join or leave the system. This property is desirable for long-lived applications (aiming to be highly available), yet has been precluded in previous asynchronous reliable broadcast protocols. We study this property in a general adversarial (i.e., Byzantine) environment.

We introduce the first specification of a dynamic Byzantine reliable broadcast (\name) primitive that is amenable to an asynchronous implementation. We then present an algorithm implementing this specification in an asynchronous network. Our \name algorithm ensures that if any correct process in the system broadcasts a message, then every correct process delivers that message unless it leaves the system. Moreover, if a correct process delivers a message, then every correct process that has not expressed its will to leave the system delivers that message. We assume that more than $2/3$ of processes in the system are correct at all times, which is tight in our context.

We also show that if only one process in the system can fail—and it can fail only by crashing—then it is impossible to implement a stronger primitive, ensuring that if any correct process in the system broadcasts (resp., delivers) a message, then every correct process in the system delivers that message—including those that leave.

youtube Shantanu Das, Nikos Giachoudis, Flaminia L. Luccio, Euripides Markou Broadcasting with mobile agents in dynamic networks +
Shantanu Das, Aix-Marseille University
Nikos Giachoudis, University of Thessaly
Flaminia L. Luccio, Universita Ca' Foscari Venezia
Euripides Markou, University of Thessaly
Abstract: We study the standard communication problem of broadcast for mobile agents moving in a network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. In this model, broadcast is a communication primitive for information transfer from one agent, the source, to all other agents. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modelled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of other agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine how many agents are necessary and sufficient to solve the broadcast problem in dynamic networks. While two agents plus the source are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs at least $n-2$ agents plus the source are necessary and sufficient. We show lower bounds on the number of agents and provide some algorithms for solving broadcast using the minimum number of agents, for various topologies. These results show how the connectivity of the graph affects the communication capability of a team of mobile agents under the mobile adversarial model.
youtube Chen-Da Liu-Zhang, Varun Maram, Ueli Maurer On Broadcast in Generalized Network and Adversarial Models +
Chen-Da Liu-Zhang, ETH Zurich
Varun Maram, ETH Zurich
Ueli Maurer, ETH Zurich
Abstract: Broadcast is a primitive which allows a specific party to distribute a message consistently among $n$ parties, even if up to $t$ parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [JACM'80] shows that broadcast is achievable if and only if $t < n/3$. There are two generalizations suggested for the broadcast problem -- with respect to the adversarial model and the communication model. Fitzi and Maurer [DISC'98] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of $n$ parties. On the other hand, Considine et al. [JC'05] extend the standard model of bilateral channels with the existence of $b$-minicast channels that allow to locally broadcast among any subset of $b$ parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to $t$ corrupted parties is possible if and only if $t < \frac{b-1}{b+1}n$. These generalizations are unified in the work by Raykov [ICALP'15], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of $b$-minicasts.

This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed by Jaffe et al. [PODC'12], Raykov [ICALP'15]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of $b$-minicasts that are necessary and that suffice towards constructing broadcast in general $b$-minicast networks.

youtube Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, Stefan Schmid Maximally Resilient Replacement Paths for a Family of Product Graphs +
Mahmoud Parham, University of Vienna
Klaus-Tycho Foerster, University of Vienna
Petar Kosic, University of Vienna
Stefan Schmid, University of Vienna
Abstract: Modern communication networks support fast path restoration mechanisms which allow to reroute traffic in case of (possibly multiple) link failures, in a completely decentralized manner and without requiring global route reconvergence. However, devising resilient path restoration algorithms is challenging as these algorithms need to be inherently local. Furthermore, the resulting failover paths often have to fulfill additional requirements related to the policy and function implemented by the network, such as the traversal of certain waypoints (e.g., a firewall).

This paper presents local algorithms which ensure a maximally resilient path restoration for a large family of product graphs, including the widely used tori and generalized hypercube topologies. Our algorithms provably ensure that even under multiple link failures, traffic is rerouted to the other endpoint of every failed link whenever possible (i.e. detouring failed links), enforcing waypoints and hence accounting for the network policy. The algorithms are particularly well-suited for emerging segment routing networks based on label stacks.

youtube Alexandre Maurer Self-stabilizing Byzantine-resilient communication in dynamic networks +
Alexandre Maurer, UM6P
Abstract: We consider the problem of communicating reliably in a dynamic network in the presence of up to k Byzantine failures. It was shown that this problem can be solved if and only if the dynamic graph satisfies a certain condition, that we call "RDC condition". In this paper, we present the first self-stabilizing algorithm for reliable communication in this setting - that is: in addition to permanent Byzantine failures, there can also be an arbitrary number of transient failures. We prove the correctness of this algorithm, provided that the RDC condition is "always eventually satisfied".
17:30 18:20
Business Meeting
December 15
15:00 16:00
Keynote by Jukka Suomela Aalto University Can we automate our own work — or show that it is hard? Abstract
16:15 17:15
Session 2 Blockchain and BFT Chair: João Leitão
youtube Xiong Zheng, Vijay K. Garg Byzantine Lattice Agreement in Asynchronous Message Systems +
Xiong Zheng, University of Texas at Austin
Vijay K. Garg, University of Texas at Austin
Abstract: We study the Byzantine lattice agreement (BLA) problem in asynchronous distributed message passing systems. In the BLA problem, each process proposes a value from a join semi-lattice and needs to output a value also in the lattice such that all output values of correct processes lie on a chain despite the presence of Byzantine processes. We present an algorithm for this problem with round complexity of $O(\log f)$ which tolerates $f < \frac{n}{5}$ Byzantine failures in the asynchronous setting without digital signatures, where $n$ is the number of processes. This is the first algorithm which has logarithmic round complexity for this problem in asynchronous setting. Before our work, Di Luna et al give an algorithm for this problem which takes $O(f)$ rounds and tolerates $f < \frac{n}{3}$ Byzantine failures. We also show how this algorithm can be modified to work in the authenticated setting (i.e., with digital signatures) to tolerate $f < \frac{n}{3}$ Byzantine failures.
youtube Isaac Sheff, Xinwen Wang, Robbert van Renesse, Andrew C. Myers Heterogeneous Paxos +
Isaac Sheff, The Max Planck Institute for Software Systems
Xinwen Wang, Cornell University
Robbert van Renesse, Cornell University
Andrew C. Myers, Cornell University
Abstract: In distributed systems, a group of *learners* achieve *consensus* when, by observing the output of some *acceptors*, they all arrive at the same value. Consensus is crucial for ordering transactions in failure-tolerant systems. Traditional consensus algorithms are homogeneous in three ways: * all learners are treated equally, * all acceptors are treated equally, and * all failures are treated equally.

These assumptions, however, are unsuitable for cross-domain applications, including blockchains, where not all acceptors are equally trustworthy, and not all learners have the same assumptions and priorities. We present the first consensus algorithm to be heterogeneous in all three respects. Learners set their own mixed failure tolerances over differently trusted sets of acceptors. We express these assumptions in a novel Learner Graph, and demonstrate sufficient conditions for consensus.

We present Heterogeneous Paxos: an extension of Byzantine Paxos. Heterogeneous Paxos achieves consensus for any viable Learner Graph in best-case three message sends, which is optimal. We present a proof-of-concept implementation, and demonstrate how tailoring for heterogeneous scenarios can save resources and latency.

youtube Martin Hirt, Ard Kastrati, Chen-Da Liu-Zhang Multi-Threshold Asynchronous Reliable Broadcast and Consensus +
Martin Hirt, ETH Zurich
Ard Kastrati, ETH Zurich
Chen-Da Liu-Zhang, ETH Zurich
Abstract: Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties $f$ is bounded by a single given threshold $t$. If $f > t$, these protocols are completely deemed insecure. We consider the relaxed notion of \emph{multi-threshold} reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as $f \le t_v$, $f \le t_c$ and $f \le t_t$ respectively. For consensus, we consider both variants of $(1-\epsilon)$-consensus and \emph{almost-surely terminating} consensus, where termination is guaranteed with probability $(1-\epsilon)$ and $1$, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures:

-Multi-threshold reliable broadcast is possible if and only if $\max{t_c,t_v} + 2t_t < n$. -Multi-threshold almost-surely consensus is possible if $\max{t_c, t_v} + 2t_t < n$, $2t_v + t_t < n$ and $t_t < n/3$. Assuming a global coin, it is possible if and only if $\max{t_c, t_v} + 2t_t < n$ and $2t_v + t_t < n$. -Multi-threshold $(1-\epsilon)$-consensus is possible if and only if $\max{t_c, t_v} + 2t_t < n$ and $2t_v + t_t < n$.

youtube Qinzi Zhang, Lewis Tseng Echo-CGC: A Communication-Efficient Byzantine-tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network +
Qinzi Zhang, Boston College
Lewis Tseng, Boston College
Abstract: In the past few years, many Byzantine-tolerant distributed machine learning (DML) algorithms have been proposed in the point-to-point communication model. In this paper, we focus on a popular DML framework -- the parameter server computation paradigm and iterative learning algorithms that proceed in rounds, e.g., \cite{vaidya-2f-redundancy, Rachid_genuine_BML,Su_BGD}. One limitation of prior algorithms in this domain is the \textit{high communication complexity}. All the Byzantine-tolerant DML algorithms that we are aware of need to send $n$ $d$-dimensional vectors from worker nodes to the parameter server in each round, where $n$ is the number of workers and $d$ is the number of dimensions of the feature space (which may be in the order of millions). In wireless network, power consumption is proportional to the number of bits transmitted. Consequently, it is extremely difficult, if not impossible, to deploy these algorithms in power-limited wireless devices. %This is because communication of large gradients (or vectors) requires high power consumption. Motivated by this observation, we aim to reduce the \textit{communication complexity} of Byzantine-tolerant DML algorithms in the \textit{single-hop radio network} \cite{Broadcast_SPAA10,Broadcast_Nitin_PODC05,Broadcast_Koo_PODC04}.

Inspired by the CGC filter developed by Gupta and Vaidya, PODC 2020 \cite{vaidya-2f-redundancy}, we propose a gradient descent-based algorithm, Echo-CGC. Our main novelty is a mechanism to utilize the \textit{broadcast properties} of the radio network to avoid transmitting the raw gradients (full $d$-dimensional vectors). In the radio network, each worker can overhear previous gradients that were transmitted to the parameter server. Roughly speaking, in Echo-CGC, %each worker will compute its local stochastic gradient, and if it if a worker agrees'' with a combination of prior gradients, it will broadcast the echo message'' instead of the its raw local gradient. The echo message contains a vector of coefficients (of size at most $n$) and the ratio of the magnitude between two gradients (a float). In comparison, the traditional approaches need to send $n$ local gradients in each round, where each gradient is typically a vector in a ultra-high dimensional space ($d \gg n$). %Each worker $i$ computes the angle between the received gradients in the current round and its own gradient (on the local cost function). If there exists a linear combination of previous gradients broadcast by other workers whose angle is less than a certain bound $\alpha$, then worker $i$ broadcasts the ``echo'' message, which contains a vector of coefficients (of size at most $n$) and the ratio of the magnitude between two gradients (a float). Compared to the traditional approach that sends the entire raw gradient – which is typically a vector in a ultra-high dimensional space – the echo message contains only a few bytes \qinzi{Is this still true with the Span method?} \lewis{No, we can say it’s in the order of $n$ and will be beneficial when $n « d$}; hence, Echo-CGC effectively reduces the communication complexity. The improvement on communication complexity of our algorithm depends on multiple factors, including number of nodes, number of faulty workers in an execution, and the cost function. We numerically analyze the improvement, and show that with a large number of nodes, Echo-CGC reduces 80% of the communication under suitable assumptions.

youtube Amine Boussetta, El-Mahdi El-Mhamdi, Rachid Guerraoui, Alexandre Maurer, Sébastien Rouault Fast Byzantine SGD (Best Student Paper Award) +
Amine Boussetta, UM6P
El-Mahdi El-Mhamdi, EPFL
Rachid Guerraoui, EPFL
Alexandre Maurer, UM6P
Sébastien Rouault, EPFL
Abstract: Modern machine learning architectures distinguish servers and workers. Typically, a $d$-dimensional model is hosted by a server and trained by $n$ workers, using a distributed \textit{stochastic gradient descent} (SGD) optimization scheme. At each SGD step, the goal is to estimate the gradient of a cost function. The simplest way to do this is to \emph{average} the gradients estimated by the workers. However, averaging is not resilient to even one single Byzantine failure of a worker. Many alternative \emph{gradient aggregation rules} (GARs) have recently been proposed to tolerate a maximum number $f$ of Byzantine workers. These GARs differ according to (1) the complexity of their computation time, (2) the maximal number of Byzantine workers despite which convergence can still be ensured (breakdown point), and (3) their accuracy, which can be captured by (3.1) their angular error, namely the angle with the true gradient, as well as (3.2) their ability to aggregate full gradients. In particular, many are not full gradients for they operate on each dimension separately, which results in a coordinate-wise blended gradient, leading to low accuracy in practical situations where the number ($s$) of workers that are actually Byzantine in an execution is small ($s<We propose \textsc{Aksel}, a new scalable median-based GAR with an optimal time complexity ($\mathcal{O}(n)$),
an optimal breakdown point ($n > 2f$) and the lowest upper bound on the \textit{expected angular error} ($\mathcal{O}(1)$) among \textit{full gradient} approaches. We also study the \textit{actual angular error} of \textsc{Aksel} when the gradient distribution is normal and show that it only grows in $\mathcal{O}(\log{n})$, which is the first logarithmic upper bound ever proven assuming an optimal breakdown point. We also report on an empirical evaluation of \textsc{Aksel} on various classification tasks, which we compare to alternative GARs against state-of-the-art attacks. \textsc{Aksel} is the only GAR reaching top accuracy when there is actually none or few Byzantine workers while maintaining a good defense even under the extreme case ($s=f$). For simplicity of presentation, we consider a scheme with a single server. However, as we explain in the paper, \textsc{Aksel} can also easily be adapted to multi-server architectures.

youtube Ignacio Amores-Sesar, Christian Cachin, Jovana Mićić Security Analysis of Ripple Consensus +
Ignacio Amores-Sesar, University of Bern
Christian Cachin, University of Bern
Jovana Mićić, University of Bern
Abstract: The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has the third-largest cryptocurrency market capitalization. The Ripple consensus protocol powers thi s network and is generally considered to a Byzantine fault-tolerant agreement protocol, which can reach consensus in the presence of faulty or malicious nodes. In contrast to traditional Byzantine agreement protocols, there is no global knowledge of all participating nodes in Ripple consensus; instead, each node declares a list of other nodes that it trusts and from which it considers votes. Previous work has brought up concerns about the liveness and safety of the consensus protocol under the general assumptions stated earlier, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper makes two contributions. It first provides a detailed, abstract description of the protocol, which has been derived from the source code. Second, the paper points out that the abstract protocol may violate safety and liveness in several simple executions under relatively benign network assumptions.
17:30 18:30
Session 3 Consensus Potpourri Chair: Rotem Oshman
youtube Alexander Spiegelman, Arik Rinberg, Dahlia Malkhi ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication +
Alexander Spiegelman, Novi
Arik Rinberg, Technion
Dahlia Malkhi, Novi
Abstract: With the emergence of attack-prone cross-organization systems, providing asynchronous state machine replication (SMR) solutions is no longer a theoretical concern. This paper presents \emph{ACE}, a framework for the design of such fault tolerant systems. Leveraging a known paradigm for randomized consensus solutions, ACE wraps existing practical solutions and real-life systems, boosting their liveness under adversarial conditions and, at the same time, promoting load balancing and fairness. Boosting is achieved without modifying the overall design or the engineering of these solutions.

ACE is aimed at boosting the prevailing approach for practical fault tolerance. This approach, often named \emph{partial synchrony}, is based on a leader-based paradigm: a good leader makes progress and a bad leader does no harm. The partial synchrony approach focuses on safety and forgoes liveness under targeted and dynamic attacks. Specifically, an attacker might block specific leaders, e.g., through a denial of service, to prevent progress. ACE provides boosting by running \emph{waves} of parallel leaders and selecting a \emph{winning} leader only retroactively, achieving boosting at a linear communication cost increase.

ACE is agnostic to the fault model, inheriting it s failure model from the wrapped solution assumptions. As our evaluation shows, an asynchronous Byzantine fault tolerance (BFT) replication system built with ACE around an existing partially synchronous BFT protocol demonstrates reasonable slow-down compared with the base BFT protocol during faultless synchronous scenarios, yet exhibits significant speedup while the system is under attack.

youtube Gilad Stern, Ittai Abraham Information Theoretic HotStuff +
Gilad Stern, Hebrew University
Ittai Abraham, VMWare Research
Abstract: This work presents Information Theoretic HotStuff (IT-HS), a new optimally resilient protocol for solving Byzantine Agreement in partial synchrony with information theoretic security guarantees. In particular, IT-HS does not depend on any PKI or common setup assumptions and is resilient to computationally unbounded adversaries. IT-HS is based on the Primary-Backup view-based paradigm. In IT-HS, in each view, each party sends only a constant number of words to every other party. This yields an $O(n^2)$ word and message complexity in each view. In addition, IT-HS requires just $O(1)$ persistent local storage and $O(n)$ transient local storage. Finally, like all Primary-Backup view-based protocols in partial synchrony, after the system becomes synchronous, all nonfaulty parties decide on a value in the first view a nonfaulty leader is chosen. Moreover, like PBFT and HotStuff, IT-HS is optimistically responsive: with a nonfaulty leader, parties decide as quickly as the network allows them to do so, without regard for the known upper bound on network delay. Our work improves in multiple dimensions upon the information theoretic version of PBFT presented by Miguel Castro, and can be seen as an information theoretic variant of the HotStuff paradigm.
youtube Yackolley Amoussou-Guenou, Bruno Biais, Maria Potop-Butucaru, Sara Tucci-Piergiovanni Rational Behaviors in Committee-Based Blockchains +
Yackolley Amoussou-Guenou, CEA List, LIP6 - Sorbonne Université
Bruno Biais, HEC Paris
Maria Potop-Butucaru, LIP6, Sorbonne Université
Sara Tucci-Piergiovanni, CEA List
Abstract: We study the rational behaviors of participants in committee-based blockchains. Committee-based blockchains rely on specific blockchain consensus that must be guaranteed in presence of rational participants. We consider a simplified blockchain consensus algorithm based on existing or proposed committee-based blockchains that encapsulates the main actions of the participants: \emph{voting} for a block, and \emph{checking its validity}. Knowing that those actions have costs, and achieving the consensus gives rewards to committee members, we study using game theory how strategic participants behave while trying to maximize their gains. We consider different reward schemes, and found that in each setting, there exist equilibria where blockchain consensus is guaranteed; in some settings however, there can be coordination failures hindering consensus. Moreover, we study equilibria with trembling participants, which is a novelty in the context of committee-based blockchains. Trembling participants are rational that can do unintended actions with a low probability. We found that in presence of trembling participants, there exist equilibria where blockchain consensus is guaranteed; however, when only voters are rewarded, there also exist equilibria where validity can be violated.
youtube Hagit Attiya, Armando Castañeda, Sergio Rajsbaum Locally Solvable Tasks and the Limitations of Valency Arguments +
Hagit Attiya, Technion
Armando Castañeda, Instituto de Matemáticas UNAM, México
Sergio Rajsbaum, Instituto de Matemáticas UNAM, México
Abstract: An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is *local* in nature, as at each stage, one configuration of an hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to *consensus*, leading one to wonder why it has not been used in impossibility results of the two other well-known tasks: *set agreement* and *renaming*. This paper provide an explanation why the proof strategies for showing the impossibility of these tasks have a global nature. We show that *a protocol can always solve such tasks locally*, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming.
youtube Talley Amir, James Aspnes, John Lazarsfeld Approximate Majority With Catalytic Inputs +
Talley Amir, Yale University
James Aspnes, Yale University
John Lazarsfeld, Yale University
Abstract: Third-state dynamics (Angluin et al. 2008; Perron et al. 2009) is a well-known process for quickly and robustly computing approximate majority through interactions between randomly-chosen pairs of agents. In this paper, we consider this process in a new model with persistent-state catalytic inputs, as well as in the presence of transient leak faults.

Based on models considered in recent protocols for populations with persistent-state agents (Dudek et al. 2017; Alistarh et al. 2017; Alistarh et al. 2020), we formalize a Catalytic Input (CI) model comprised of $n$ input agents and $m$ worker agents. For $m = \Theta(n)$, we show that computing the PARITY of the input population with high probability requires at least $\Omega(n^2)$ total interactions, demonstrating a strong separation between the CI and standard population models. On the other hand, we show that the third-state dynamics can be naturally adapted to this new model to solve approximate majority in $O(n \log n)$ total steps with high probability when the input margin is $\Omega(\sqrt{n \log n})$, which preserves the time and space efficiency of the process in the original model.

Moreover we show the robustness of third-state dynamics protocols to the transient leak faults considered by (Alistarh et al. 2017; Alistarh et al 2020). In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each time step with probability $\beta \leq O\left(\frac{\sqrt{n \log n}}{n}\right)$. The resilience of these dynamics to adversarial leaks exhibits a subtle connection to previous results involving Byzantine agents.

youtube Hagit Attiya, Sweta Kumari, Noa Schiller Optimal Resilience in Systems that Mix Shared Memory and Message Passing +
Hagit Attiya, Technion
Sweta Kumari, Technion
Noa Schiller, Technion
Abstract: We investigate the minimal number of failures that can *partition* a system where processes communicate both through shared memory and by message passing. We prove that this number precisely captures the resilience that can be achieved by algorithms that implement a variety of shared objects, like registers, and solve common tasks, like randomized consensus, approximate agreement and renaming. This has implications for the m&m-model of Aguilera et al., and for the hybrid, cluster-based model of Imbs and Raynal.
December 16
15:00 16:00
Keynote by Idit Keidar Technion Byzantine Agreement and SMR with Sub-Quadratic Message Complexity Abstract
16:15 17:15
Session 4 Graph algorithms and population protocols Chair: Jara UItto
youtube Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, Gregory Schwartzman Fast Deterministic Algorithms for Highly-Dynamic Networks +
Keren Censor-Hillel, Technion-Israel Institute of Technology
Neta Dafni, Technion-Israel Institute of Technology
Victor I. Kolobov, Technion-Israel Institute of Technology
Ami Paz, University of Vienna
Gregory Schwartzman, Japan Advanced Institute of Science and Technology
Abstract: This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which \emph{arbitrarily many} edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an $O(1)$ amortized time complexity, (2) using only $O(\log{n})$-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks.

The tasks for which we deduce such an algorithm are maximal matching, $(degree+1)$-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.

youtube Salwa Faour, Fabian Kuhn Approximating Bipartite Minimum Vertex Cover in the CONGEST model (Best Paper Award) +
Salwa Faour, University of Freiburg, Germany
Fabian Kuhn, University of Freiburg, Germany
Abstract: We give efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model. From K\H{o}nig's theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. We first show that together with an existing $O(n\log n)$-round algorithm for computing a maximum matching, the constructive proof of K\H{o}nig's theorem directly leads to a deterministic $O(n\log n)$-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an \emph{approximate} maximum matching into an \emph{approximate} minimum vertex cover. Given a $(1-\delta)$-approximate matching for some $\delta>1$, we show that a $(1+O(\delta))$-approximate vertex cover can be computed in time $O\big(D+\poly\big(\frac{\log n}{\delta}\big)\big)$, where $D$ is the diameter of the graph. When combining with known graph clustering techniques, for any $\eps\in(0,1]$, this leads to a $\poly\big(\frac{\log n}{\eps}\big)$-time deterministic and also to a slightly faster and simpler randomized $O\big(\frac{\log n}{\eps^3}\big)$-round CONGEST algorithm for computing a $(1+\eps)$-approximate vertex cover in bipartite graphs. For constant $\eps$, the randomized time complexity matches the $\Omega(\log n)$ lower bound for computing a $(1+\eps)$-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires $\tilde{\Omega}(n^2)$ rounds in the CONGEST model and where it is not even known how to compute any $(2-\eps)$-approximation in time $o(n^2)$.
youtube Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, Virginia Vassilevska Williams Distributed Distance Approximation +
Bertie Ancona, MIT
Keren Censor-Hillel, Technion
Mina Dalirrooyfard, MIT
Yuval Efron, Technion
Virginia Vassilevska Williams, MIT
Abstract: Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants.

Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems.

Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhury and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.

youtube Michael Feldmann, Kristian Hinnenthal, Christian Scheideler Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs +
Michael Feldmann, Paderborn University
Kristian Hinnenthal, Paderborn University
Christian Scheideler, Paderborn University
Abstract: We consider the problem of computing shortest paths in hybrid networks, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a local and a global mode. Specifically, the local edges model a fixed communication network in which $O(1)$ messages of size $O(\log n)$ can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most $O(\log n)$ messages over global edges, which restricts the nodes to use these edges only very sparsely.

We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in sparse graphs. Specifically, we present exact $O(\log n)$ time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and $3$-approximations for graphs that have at most $n + O(n^{1/3})$ edges and arboricity $O(\log n)$. For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model. Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest.

youtube Leonid Barenboim, Harel Levin Secured Distributed Algorithms without Hardness Assumptions +
Leonid Barenboim, Department of Mathematics and Computer Science, The Open University of Israel
Harel Levin, Department of Physics, Nuclear Research Center-Negev, Israel; Department of Mathematics and Computer Science, The Open University of Israel
Abstract: We study algorithms in the distributed message-passing model that produce secured output, for an input graph $G$. Specifically, each vertex computes its part in the output, the entire output is correct, but each vertex cannot discover the output of other vertices, with a certain probability. This is motivated by high-performance processors that are embedded nowadays in a large variety of devices. Furthermore, sensor networks were established to monitor physical areas for scientific research, smart-cities control, and other purposes. In such situations, it no longer makes sense, and in many cases it is not feasible, to leave the whole processing task to a single computer or even a group of central computers. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms for many classic problems, the discussion about the security of distributed algorithms was somewhat neglected. Nevertheless, many protocols and algorithms were devised in the research area of secure multi-party computation problem (MPC or SMC). However, the notions and terminology of these protocols are quite different than in classic distributed algorithms. As a consequence, the focus in those protocols was to work for every function $f$ at the expense of increasing the round complexity, or the necessity of several computational assumptions. In this work, we present a novel approach, which rather than turning existing algorithms into secure ones, identifies and develops those algorithms that are inherently secure (which means they do not require any further constructions). This approach yields efficient secure algorithms for various locality problems, such as coloring, network decomposition, forest decomposition, and a variety of additional labeling problems. Remarkably, our approach does not require any hardness assumption, but only a private randomness generator in each vertex. This is in contrast to previously known techniques in this setting that are based on public-key encryption schemes.
youtube Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue, Sebastien Tixeuil Uniform Bipartition in Population Protocol Model with Arbitrary Communication Graphs +
Hiroto Yasumi, Nara Institute of Science and Technology
Fukuhito Ooshita, Nara Institute of Science and Technology
Michiko Inoue, Nara Institute of Science and Technology
Sebastien Tixeuil, Sorbonne Universite
Abstract: In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of \emph{arbitrary} communication graphs. As a result, we clarify the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.
17:30 18:10
Session 5 Concurrent data structures Chair: Paolo Romano
youtube Armando Castaneda, Sergio Rajsbaum, Michel Raynal Relaxed Queues and Stacks from Read/Write Operations +
Armando Castaneda, Instituto de Matematicas, UNAM
Sergio Rajsbaum, Instituto de Matematicas, UNAM
Michel Raynal, IRISA, ISTIC Université de Rennes
Abstract: Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizabilty are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.
youtube Dempsey Wade, Edward Talmage Fast and Space-Efficient Queues via Relaxation +
Dempsey Wade, Bucknell University
Edward Talmage, Bucknell University
Abstract: Efficient message-passing implementations of shared data types are a vital component of practical distributed systems, enabling them to work on shared data in predictable ways, but there is a long history of results showing that many of the most useful types of access to shared data are necessarily slow. A variety of approaches attempt to circumvent these bounds, notably weakening consistency guarantees and relaxing the sequential specification of the provided data type. These trade behavioral guarantees for performance. We focus on relaxing the sequential specification of a first-in, first-out queue type, which has been shown to allow faster linearizable implementations than are possible for unrelaxed queues.

The algorithms which showed these improvements in operation time tracked a complete execution history, storing complete object state at all n processes in the system, leading to n copies of every stored data element. In this paper, we consider the question of reducing the space complexity of linearizable implementations of shared data types, which provide intuitive behavior through strong consistency guarantees. We improve the existing algorithm for a relaxed queue, showing that it is possible to store only one copy of each element in a shared queue, while still having a low amortized time cost. This is one of several important steps towards making these data types practical in real world systems.

youtube Daniel Katzan, Adam Morrison Recoverable, Abortable, and Adaptive Mutual Exclusion with Sublogarithmic RMR Complexity +
Daniel Katzan, Tel Aviv University
Adam Morrison, Tel Aviv University
Abstract: We present the first recoverable mutual exclusion (RME) algorithm that is simultaneously abortable, adaptive to point contention, and with sublogarithmic RMR complexity. Our algorithm has $O(\min(K,\log_W N))$ RMR passage complexity and $O(F + \min(K,\log_W N))$ RMR super-passage complexity, where $K$ is the number of concurrent executing processes (point contention), $W$ is the size (in bits) of registers, and $F$ is the number of crashes in a super-passage. Under the standard assumption that $W=\Theta(\log N)$, these bounds translate to worst-case $O(\frac{\log N}{\log \log N})$ passage complexity and $O(F + \frac{\log N}{\log \log N})$ super-passage complexity.

Our key building blocks are:

  • A $D$-process abortable RME algorithm, for $D \leq W$, with $O(1)$ passage complexity and $O(1+F)$ super-passage complexity. We obtain this algorithm by using the Fetch-And-Add (FAA) primitive, unlike prior work on RME that uses Fetch-And-Store (FAS/SWAP).
  • A generic transformation that transforms any abortable RME algorithm with passage complexity of $B < W$, into an abortable RME lock with passage complexity of $O(\min(K,B))$.
youtube Soukaina Firmli, Vasileios Trigonakis, Jean-Pierre Lozi, Iraklis Psaroudakis, Alexander Weld, Dalila Chiadmi, Sungpack Hong, Hassan Chafi CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure +
Soukaina Firmli, Mohammed V University in Rabat, Ecole Mohammadia d'Ingénieurs, SIP Research Team
Vasileios Trigonakis, Oracle Labs
Jean-Pierre Lozi, Oracle Labs
Iraklis Psaroudakis, Oracle Labs
Alexander Weld, Oracle Labs
Dalila Chiadmi, Mohammed V University in Rabat, Ecole Mohammadia d'Ingénieurs, SIP Research Team
Sungpack Hong, Oracle Labs
Hassan Chafi, Oracle Labs
Abstract: The graph model enables a broad range of analysis, thus graph processing is an invaluable tool in data analytics. At the heart of every graph-processing system lies a concurrent graph data structure storing the graph. Such a data structure needs to be highly efficient for both graph algorithms and queries. Due to the continuous evolution, the sparsity, and the scale-free nature of real-world graphs, graph-processing systems face the challenge of providing an appropriate graph data structure that enables both fast analytic workloads and low-memory graph mutations. Existing graph structures offer a hard trade-off between read-only performance, update friendliness, and memory consumption upon updates. In this paper, we introduce CSR++, a new graph data structure that removes these trade-offs and enables both fast read-only analytics and quick and memory-friendly mutations. CSR++ combines ideas from CSR, the fastest read-only data structure, and adjacency lists to achieve the best of both worlds. We compare CSR++ to CSR, adjacency lists from the Boost Graph Library, and LLAMA, a state-of-the-art update-friendly graph structure. In our evaluation, which is based on popular graph-processing algorithms executed over real-world graphs, we show that CSR++ remains close to CSR in read-only concurrent performance (within 10% on average), while significantly outperforming CSR (by an order of magnitude) and LLAMA (by almost 2x) with frequent updates.
18:10 18:30
Session 6 Formal methods Chair: Shir Landau
youtube Ritam Ganguly, Anik Momtaz, Borzoo Bonakdarpour Monitoring Distributed Systems under Partial Synchrony +
Ritam Ganguly, Michigan State University
Anik Momtaz, Michigan State University
Borzoo Bonakdarpour, Michigan State University
Abstract: In this paper, we study the problem of runtime verification of distributed applications that do not share a global clock with respect to specifications in the linear temporal logics (LTL). Our proposed method distinguishes from the existing work in three novel ways. First, we make a practical assumption that the distributed system under scrutiny is augmented with a clock synchronization algorithm that guarantees bounded clock skew among all processes. Second, we do not make any assumption about the structure of predicates that form LTL formulas. This relaxation allows us to monitor a wide range of applications that was not possible before. Subsequently, we propose a distributed monitoring algorithm by employing SMT solving techniques. Third, given the fact that distributed applications nowadays run on massive cloud services, we extend our solution to a parallel monitoring algorithm to utilize the available computing infrastructure. We report on rigorous synthetic as well as real-world case studies and demonstrate that scalable online monitoring of distributed applications is within our reach.
youtube Mahboubeh Samadi, Fatemeh Ghassemi, Ramtin Khosravi Decentralized Runtime Enforcement of Message Sequences in Message-Based Systems +
Mahboubeh Samadi,
Fatemeh Ghassemi,
Ramtin Khosravi,
Abstract: In the new generation of message-based systems such as network-based smart systems, distributed components collaborate via asynchronous message passing. In some cases, particular ordering among the messages may lead to violation of the desired properties such as data confidentiality. Due to the absence of a global clock and usage of off-the-self components, there is no control over the order of messages at design time. To make such systems safe, we propose a choreography-based runtime enforcement algorithm that given an automata-based specification of unwanted message sequences, prevents certain messages to be sent, and assures that the unwanted sequences are not formed. Our algorithm is fully decentralized in the sense that each component is equipped with a monitor, as opposed to having a centralized monitor. As there is no global clock in message-based systems, monitors may prevent the sequence formation conservatively if the sequence consists of concurrent messages. We aim to minimize conservative prevention in our algorithm when the message sequence has not been formed. The efficiency and scalability of our algorithm are evaluated in terms of the communication overhead and the blocking duration through simulation.