Blockchains promise to make online services more fault tolerant because they are replicated on a distributed system of nodes. Their nodes typically run different implementations of the same protocol across different geo-distributed regions, making the protocol supposedly tolerant to various failures including isolated crashes, transient failures, network partitions or attacks. Unfortunately, their fault tolerance has never been compared.

In recent years, opportunistic traders have extracted hundreds of millions of dollars from blockchains by reordering financial transactions. The problem stems from the fact that blockchains implement a state machine replication that orders transactions in any consistent order, regardless of the order in which these transactions were received. Existing attempts at enforcing the order perceived by honest participants suffer from cyclic dependencies or message delays. In this paper, we propose the Asynchronous Ordered Atomic Broadcast (AOAB) protocol. It does not suffer from cyclic dependencies or message delays because (i) it assigns an absolute timestamp to transactions, and (ii) it tolerates unbounded message delays. Besides being the first protocol to solve this problem, AOAB is communication-optimal and resilience-optimal. In particular, AOAB makes use of threshold signatures and information dissemination to reach a communication complexity of$\mathcal{O}(n\ell+\lambda n^{2})$, where$n$is the number of processes,$\ell$is the input (transaction) size and$\lambda$is the security parameter. This is optimal when$\ell\geq\lambda n$,

In general, consensus cannot be solved if an adversary controls a third of the system. Yet, blockchain participants typically reach consensus “eventually” despite an adversary controlling a minority of the system. Exceeding this$\frac{1}{3}$cap is made possible by tolerating transient disagreements, where distinct participants select distinct blocks for the same index, before eventually agreeing on the same block. Until now, no blockchain could tolerate an attacker controlling a majority of the system. In this paper, we present Zero-Loss Blockchain ZLB, the first blockchain that tolerates an adversary controlling more than half of the system. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably faulty replicas. Interestingly, ZLB does not need a known bound on the delay of messages but progressively reduces the portion of alive but corrupt replicas below$\frac{1}{3}$, and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff that cannot tolerate$n/3$faults and is almost as fast as the scalable Redbelly Blockchain.

Abstract The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most $$f < n / 3$$ f < n / 3 failures, any solution to Byzantine consensus exchanges $$\Omega \big (n^2\big )$$ Ω ( n 2 ) words, where a word contains a constant number of values and signatures. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony where the network alternates between (1) asynchronous periods, with unbounded message delays, and (2) synchronous periods, with $$\delta $$ δ -bounded message delays. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad , a partially synchronous Byzantine consensus protocol with $$O\big (n^2\big )$$ O ( n 2 ) worst-case communication complexity. In addition, SQuad is optimally-resilient (tolerating up to $$f < n / 3$$ f < n / 3 failures) and achieves $$O(f \cdot \delta )$$ O ( f · δ ) worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization , the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync , a view synchronization protocol with $$O\big (n^2\big )$$ O ( n 2 ) communication complexity and $$O(f \cdot \delta )$$ O ( f · δ ) latency complexity, which we utilize in order to obtain SQuad .

Traditional blockchain systems offer a secure way of tracking the ownership of digital assets as long as the attacker does not control a large portion of the overall computational or mining power. They typically require participants to generate a proof-of-work before proposing a block at a given index of the chain. To choose one block among the candidate blocks at the same index, Nakamoto’s consensus, Ghost , and the original Ethereum’s consensus select, respectively, the longest branch, the heaviest subtree and the branch with the most difficult crypto-puzzles. This allows an attacker who can generate proofs-of-work faster than others to double spend by overwriting any given branch. In this article, we present a double spending attack, called the Balance attack, that simply needs to delay some messages. This result sheds new lights on an important, often implicit, assumption of the blockchain, synchrony , under which the transmission delay of any message should be within a known upper bound. We show that the attack succeeds with high probability on the protocols of the two largest blockchain systems in market capitalization, Bitcoin and Ethereum. To quantify the impact of our attack, we replicated the blockchain network run by 50 financial institutions and achieved double spending in less than 20 minutes. Finally, we demonstrate the success of the attack empirically by modifying the geth software and hijacking BGP in a controlled distributed system whose distribution of mining power is set to the distribution observed on the Ethereum main blockchain.

Blockchain governance is paramount to lead securely a large group of users towards the same decisions without disputes about the legitimacy of a blockchain instance over another. As of today, there is no efficient way of protecting this governance against an oligarchy. This paper aims to offer a new dimension to the security of blockchains by proposing a solution known as proportional governance reconfiguration. This solution mitigates the formation of an oligarchy by (1) electing governors proportionally using a proportional multi-winner election protocol (2) reconfiguring the governance automatically and periodically. The proportional governance reconfiguration relies on a Solidity based implementation making it compatible and usable in many smart contract supported blockchains. We prove our solution solves the proportional governance problem and we evaluate our solution on two smart contract supporting blockchains Ethereum-PoA and Smart Redbelly Blockchain. Our results indicate that our proportional governance can elect 200 governors within 6–12 minutes when 1000 voters from 5 continents vote for 500 candidates.

The problem of Byzantine consensus has been key to designing secure distributed systems. However, it is particularly difficult, mainly due to the presence of Byzantine processes that act arbitrarily and the unknown message delays in general networks. Although it is well known that both safety and liveness are at risk as soon as$n/3$Byzantine processes fail, very few works attempted to characterize precisely the faults that produce safety violations from the faults that produce termination violations. In this paper, we present a new lower bound on the solvability of the consensus problem by distinguishing deceitful faults violating safety and benign faults violating termination from the more general Byzantine faults, in what we call the Byzantine-deceitful-benign fault model. We show that one cannot solve consensus if$n\leq 3t+d+2q$with$t$Byzantine processes,$d$deceitful processes, and$q$benign processes. In addition, we show that this bound is tight by presenting the Basilic class of consensus protocols that solve consensus when$n > 3t+d+2q$. These protocols differ in the number of processes from which they wait to receive messages before progressing. Each of these protocols is thus better suited for some applications depending on the predominance of benign or deceitful faults.

With the recent advent of blockchains, we have witnessed a plethora of blockchain proposals. These proposals range from using work to using time, storage or stake in order to select blocks to be appended to the chain. As a drawback it makes it difficult for the application developer to choose the right blockchain to support their applications. In particular, the scalability and performance one can obtain from a specific blockchain is typically unknown. The claimed results are often obtained in isolation by the developers of the blockchain themselves. The experimental conditions corresponding to these results are generally missing and the lack of details make these results irreproducible.

Decentralization promises to remedy the drawbacks of the web by executing decentralized applications (DApps) on blockchains. Unfortunately, modern blockchains cannot support realistic web application workloads mainly due to congestion.We introduce the Smart Redbelly Blockchain (SRBB), a provably correct permissionless blockchain that reduces congestion by (1) avoiding redundant propagation and validations of transactions with Transaction Validation and Propagation Reduction (TVPR) and (2) mitigating the propagation of invalid transactions within blocks by Byzantine nodes with a dedicated Reward-Penalty Mechanism (RPM). Our comparison of SRBB against Algorand, Avalanche, Diem, Ethereum, Quorum, and Solana, using the DIABLO benchmark suite, indicates that SRBB outperforms all these blockchains under real application workloads. Moreover, SRBB is the only blockchain to successfully execute real workloads of NASDAQ and Uber on a DApp without losing transactions. To demonstrate that TVPR and RPM are the causes of the improved performance, we compare SRBB with its naive baseline, which does not contain TVPR and RPM. Our results show that TVPR increases the throughput by 55× and divides the latency by 3.5, while RPM increases the throughput by 7% under flooding attacks. Finally, TVPR helps reduce transaction losses in the normal scenario while RPM goes further and mitigates transaction losses under flooding attacks.

Reordering blockchain transactions to manipulate markets profited hackers by hundreds of millions of dollars. Because they rely on State Machine Replication (SMR), blockchains order transactions without preventing hackers from influencing the chosen order. Some order-fair consensus protocols, like Pompē [33], order transactions before agreeing on this order. They are insufficient because a hacker can leverage the lack of triangle inequality among network latencies to observe pending transactions before issuing their own. Other DAG-based protocols, like Fino [24], use commit-reveal to obfuscate transactions, but cannot prevent reordering by a Byzantine leader.In this paper, we present Lyra, a protocol that solves this problem. The key idea is the combination of a commit-reveal protocol to obfuscate transaction payloads, and a leaderless ordered consensus protocol that predicts the order of transactions. Lyra has optimal good-case latency, prevents reordering attacks, and is scalable. Finally, it outperforms the latency of Pompē by up to 2 times and its throughput by up to 7 times on a 100-node network over 3 continents.

Abstract In this paper, we consider the problem of cross-chain payment whereby customers of different escrows—implemented by a bank or a blockchain smart contract—successfully transfer digital assets without trusting each other. Prior to this work, cross-chain payment problems did not require this success, or any form of progress. We introduce a new specification formalism called Asynchronous Networks of Timed Automata to formalise such protocols. We present the first cross-chain payment protocol that ensures termination in a bounded amount of time and works correctly in the presence of clock drift. We then demonstrate that it is impossible to solve this problem without assuming synchrony, in the sense that each message is guaranteed to arrive within a known amount of time. Yet, we solve an eventually terminating weaker variant of this problem, where success is conditional on the patience of the participants, without assuming synchrony, and in the presence of Byzantine failures. We also discuss the relation with the recently defined cross-chain deals.

In a non-synchronous system with n processes, no t0-resilient (deterministic or probabilistic) Byzantine consensus protocol can prevent a disagreement among correct processes if the number of faulty processes is ≥n−2t0. Therefore, the community defined the accountable Byzantine consensus problem: the problem of (i) solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed t0), and (ii) allowing correct processes to obtain proofs of culpability of n−2t0 faulty processes whenever a disagreement occurs. This paper presents ABC, a simple yet efficient transformation of any non-synchronous t0-resilient (deterministic or probabilistic) Byzantine consensus protocol into its accountable counterpart. In the common case (up to t0 faults), ABC introduces an additive overhead of two communication rounds and O(n2) exchanged bits. Whenever they disagree, correct processes detect culprits by exchanging O(n3) messages, which we prove optimal. Lastly, ABC is not limited to Byzantine consensus: ABC provides accountability for other essential distributed problems (e.g., reliable and consistent broadcast).

We present SAZyzz, a leader-based Byzantine Fault Tolerant consensus protocol for partially synchronous networks. SAZyzz exhibits a better performance/scalability compared to the state-of-the-art leader-based BFT consensus protocols. It is built on top of AZyzzyva and has adopted a tree-based communication model which enables it to enhance the scalability of AZyzzyva. Additionally, SAZyzz reduces the communication complexity toO(logN) in two paths of the protocol. However, the tree-based topology has been argued that has a shortcoming when used in designing BFT consensus protocols. This refers to the strong assumption that all the internal nodes of the tree are honest, which leads to a trade-off between tolerating Byzantine faults and better performance and scalability. This paper shows that, with the current technological infrastructures available for industrial systems, such as Trusted Execution Environment (TEE) and Public Key Infrastructure (PKI), this assumption is realistic. SAZyzz comprises of fast-path and backup-path, each of which has two modes:simple modeandscalable mode. To demonstrate the efficiency and feasibility of SAZyzz's adoption for blockchain systems, we designed and implemented the ZyConChain blockchain system based on SAZyzz. The evaluation results show that SAZyzz can significantly improve the performance/scalability of blockchain systems.

It is impossible to solve the Byzantine consensus problem in an open network of n participants if only 2n/3 or less of them are correct. As blockchains need to solve consensus, one might think that blockchains need more than 2n/3 correct participants. But it is yet unknown whether consensus can be solved when less than 2n/3 participants are correct and k participants are rational players, which misbehave if they can gain the loot. Trading correct participants for rational players may not seem helpful to solve consensus since rational players can misbehave whereas correct participants, by definition, cannot.

A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. A distributed protocol solves a decision task if it enables processes to produce admissible output values despite arbitrary (Byzantine) failures. Unfortunately, it has been known for decades that many decision tasks cannot be solved if the system is overly corrupted, i.e., safety of distributed protocols solving such tasks can be violated in unlucky scenarios.By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect some faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity.In this paper, we propose a generic transformation, called τscr, of any non-synchronous distributed protocol solving a decision task into its accountable version. Our τscrtransformation is built upon the well-studied simulation of crash failures on top of Byzantine failures and increases the communication complexity by a quadratic multiplicative factor in the worst case.

It is known that the agreement property of the Byzantine consensus problem among$n$processes can be violated in a non-synchronous system if the number of faulty processes exceeds$t_{0}$= ┌$n$/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed$t_{0}$) and allowing correct processes to obtain proof of culpability of (at least)$t_{0}+ 1$faulty processes whenever correct processes disagree. We present four complementary contributions: 1) We introduce ABC: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. ABC introduces an overhead of only two all-to-all communication rounds and$O(n^{2})$additional bits in executions with up to$t_{0}$faults (i.e., in the common case). 2) We define the accountability complexity, a complex-ity metric representing the number of accountability-specific messages that correct processes must send. Fur-thermore, we prove a tight lower bound. In particular, we show that any accountable Byzantine consensus protocol incurs cubic accountability complexity. Moreover, we illustrate that the bound is tight by applying the ABC transformation to any Byzantine consensus protocol. 3) We demonstrate that, when applied to an optimal Byzan-tine consensus protocol, ABC constructs an accountable Byzantine consensus protocol that is (1) optimal with respect to the communication complexity in solving consensus whenever consensus is solvable, and (2) op-timal with respect to the accountability complexity in obtaining accountability whenever disagreement occurs. 4) We generalize ABC to other distributed computing prob-lems besides the classic consensus problem. We charac-terize a class of agreement tasks, including reliable and consistent broadcast [5], that ABC renders accountable.

Today, the market capitalization of the seminal blockchain, Bitcoin, is about $803B which incentivizes malicious participants to find problematic executions that would allow them to steal financial assets. As the blockchain requires a distributed set of machines to agree on a unique block of transactions to be appended to the chain, attackers naturally try to exploit consensus vulnerabilities to double spend. As a result, formally verifying that a blockchain consensus protocol is safe and live is key to mitigate financial losses. Recent progress in mechanical proofs represent the first steps towards verifying blockchain consensus. The parameterized model checking of threshold automata (TAs) has recently proved instrumental in verifying fully asynchronous parts of consensus algorithms, like broadcast algorithms [4]. The aforementioned reduction technique cannot apply to partial synchrony: moving the message reception step to a later point in the execution might violate an assumed message delay.

Blockchain has recently attracted the attention of the industry due, in part, to its ability to automate asset transfers. It requires distributed participants to reach a consensus on a block despite the presence of malicious (a.k.a. Byzantine) participants. Malicious participants exploit regularly weaknesses of these blockchain consensus algorithms, with sometimes devastating consequences. In fact, these weaknesses are quite common and are well illustrated by the flaws in various blockchain consensus algorithms [Pierre Tholoniat and Vincent Gramoli, 2019]. Paradoxically, until now, no blockchain consensus has been holistically verified. In this paper, we remedy this paradox by model checking for the first time a blockchain consensus used in industry. We propose a holistic approach to verify the consensus algorithm of the Red Belly Blockchain [Tyler Crain et al., 2021], for any number n of processes and any number f < n/3 of Byzantine processes. We decompose directly the algorithm pseudocode in two parts - an inner broadcast algorithm and an outer decision algorithm - each modelled as a threshold automaton [Igor Konnov et al., 2017], and we formalize their expected properties in linear-time temporal logic. We then automatically check the inner broadcasting algorithm, under a carefully identified fairness assumption. For the verification of the outer algorithm, we simplify the model of the inner algorithm by relying on its proven properties. Doing so, we formally verify, for any parameter, not only the safety properties of the Red Belly Blockchain consensus but also its liveness in less than 70 seconds.

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.

Classical synchronous consensus algorithms are leaderless: processes exchange their proposals, retain the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are more robust in that they only require eventual synchrony, but are however typically leader-based. Intuitively, this is a weakness for a slow leader can delay any decision. This paper asks whether, under eventual synchrony, it is possible to deterministically solve consensus without a leader. The fact that the weakest failure detector to solve consensus is one that also eventually elects a leader seems to indicate that the answer to the question is negative. We prove in this paper that the answer is actually positive. We first give a precise definition of the very notion of a leaderless algorithm. Then we present three indulgent leaderless consensus algorithms, each we believe interesting in its own right: (i) for shared memory, (ii) for message passing with omission failures and (iii) for message passing with Byzantine failures (with and without authentication).

In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm. If among$n$users$t < n/3$are malicious then it ensures consensus; otherwise (if$t\geq n/3)$, it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchain applications as it allows them to totally order blocks in a chain whenever possible, hence avoiding forks and double spending and, otherwise, to punish (e.g., via slashing) at least$n/3$malicious users when a fork occurs. This problem is more difficult than perhaps it first appears. One could try identifying malicious senders by extending classic Byzantine consensus algorithms to piggyback signed messages. We show however that to achieve accountability the resulting algorithms would then need to exchange$\Omega(\kappa^{2}\cdot n^{5})$bits, where$\kappa$is the security parameter of the signature scheme. By contrast, Polygraph has communication complexity$O(\kappa\cdot n^{4})$. Finally, we implement Polygraph in a blockchain and compare it to the Red Belly Blockchain to show that it commits more than 10,000 Bitcoin-like transactions per second when deployed on 80 geodistributed machines.

Blockchain has found applications to track ownership of digital assets. Yet, several blockchains were shown vulnerable to network attacks. It is thus crucial for companies to adopt secure blockchains before moving them to production. In this paper, we present Red Belly Blockchain (RBBC), the first secure blockchain whose throughput scales to hundreds of geodistributed consensus participants. To this end, we drastically revisited Byzantine Fault Tolerant (BFT) blockchains through three contributions: (i) defining the Set Byzantine Con-sensus problem of agreeing on a superblock of all proposed blocks instead of a single block; (ii) adopting a fair leaderless design to offer censorship-resistance guaranteeing the commit of correctly requested transactions; (iii) introducing sharded verification to limit the number of signature verifications without hampering security. We evaluate RBBC on up to 1000 VMs of 3 different types, spread across 4 continents, and under attacks. Although its performance is affected by attacks, RBBC scales in that its throughput increases to hundreds of consensus nodes and achieves 30k TPS throughput and 3 second latency on 1000 VMs, hence improving by 3× both the latency and the throughput of its closest competitor.

The problem of transaction reordering in blockchains, also known as the blockchain anomaly [Christopher Natoli and Vincent Gramoli, 2016], can lead to fairness limitations [Kelkar et al., 2020] and front-running activities [Philip Daian et al., 2020] in cryptocurrency. To cope with this problem despite f < n/3 byzantine processes, Zhang et al. [Zhang et al., 2020] have introduced the ordering linearizability property ensuring that if two transactions or commands are perceived by all correct processes in the same order, then they are executed in this order. They proposed a generic distributed protocol that first orders commands and then runs a leader-based consensus protocol to agree on these orders, hence requiring at least 11 message delays. In this paper, we parallelize the ordering with the execution of the consensus to require only 6 message delays. For the ordering, we introduce the ordered reliable broadcast primitive suitable for broadcast-based cryptocurrencies (e.g., [Daniel Collins et al., 2020]). For the agreement, we build upon the DBFT leaderless consensus protocol [Tyler Crain et al., 2018] that was recently formally verified [Bertrand et al., 2021]. The combination is thus suitable to ensure ordering linearizability in consensus-based cryptocurrencies (e.g., [Tyler Crain et al., 2021]).

There is an increasing interest in a fast-growing machine learning technique called Federated Learning (FL), in which the model training is distributed over mobile user equipment (UEs), exploiting UEs' local computation and training data. Despite its advantages such as preserving data privacy, FL still has challenges of heterogeneity across UEs' data and physical resources. To address these challenges, we first propose FEDL, a FL algorithm which can handle heterogeneous UE data without further assumptions except strongly convex and smooth loss functions. We provide a convergence rate characterizing the trade-off between local computation rounds of each UE to update its local model and global communication rounds to update the FL global model. We then employ FEDL in wireless networks as a resource allocation optimization problem that captures the trade-off between FEDL convergence wall clock time and energy consumption of UEs with heterogeneous computing and power resources. Even though the wireless resource allocation problem of FEDL is non-convex, we exploit this problem's structure to decompose it into three sub-problems and analyze their closed-form solutions as well as insights into problem design. Finally, we empirically evaluate the convergence of FEDL with PyTorch experiments, and provide extensive numerical results for the wireless resource allocation sub-problems. Experimental results show that FEDL outperforms the vanilla FedAvg algorithm in terms of convergence rate and test accuracy in various settings.

Blockchains have captured the attention of many, resulting in an abundance of new systems available for use. However, selecting an appropriate blockchain for an application is challenging due to the lack of comparative information discussing core metrics such as throughput, latency and scalability. Although a number of efforts have been devoted to performance evaluation, there is limited work dedicated to blockchains that are both efficient, due to avoiding complex Proof-of-Work cryptopuzzles, and secure, because they solve consensus deterministically despite Byzantine failures. In this paper, we evaluate the performance of three blockchains that cope with such malicious behaviors, namely Burrow, Quorum and Red Belly Blockchain. To this end, we modified the Hyperledger Caliper benchmark to solve three main limitations: unnecessary overheads, online cryptographic signatures and centralized clients. Our results identify the maximum send rate that Burrow and Quorum can process, and that Red Belly Blockchain can offer an 8-times higher throughput than the other blockchains.

We consider the problem of cross-chain payment whereby customers of different escrows---implemented by a bank or a blockchain smart contract---successfully transfer digital assets without trusting each other. Prior to this work, cross-chain payment problems did not require this success, or any form of progress. We demonstrate that it is possible to solve this problem when assuming synchrony, in the sense that each message is guaranteed to arrive within a known amount of time, but impossible to solve without assuming synchrony. Yet, we solve a weaker variant of this problem, where success is conditional on the patience of the participants, without assuming synchrony, and in the presence of Byzantine failures. We also discuss the relation with the recently defined cross-chain deals.

In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm. If among n users f < n/3 are malicious then it ensures consensus, otherwise it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchains as it allows to totally order blocks in a chain whenever possible, hence avoiding double spending and, otherwise, to punish at least n/3 malicious users when a fork occurs. This problem is more difficult than it first appears. Blockchains typically run in open networks whose delays are hard to predict, hence one cannot build upon synchronous techniques [Andreas Haeberlen et al., 2007; Vitalik Buterin and Virgil Griffith, 2019]. One may exploit cryptographic evidence of PBFT-like consensus [Miguel Castro and Barbara Liskov, 2002], however detecting equivocation would be insufficient. We show that it is impossible without extra logs of at least Ω(n) rounds [Pierre Civit et al., 2019]. Each round of Polygraph exchanges O(n²) messages.

Summary Selecting which blockchain participants can decide upon a new block is a difficult problem. Consortium blockchains need the participants to be predetermined while public blockchains incentivize all participants to waste their resources to decide every block. In this paper, we introduce the community blockchain that allows potentially all participants to decide upon “some” block while restricting the set of participants deciding upon “one” block. To this end, we propose a blockchain reconfiguration, a Byzantine consensus protocol that allows to dynamically change the set of blockchain participants deciding upon the upcoming blocks. The resulting blockchain, called ComChain, is resilience optimal and transitions through different configurations of participants recorded in dedicated blocks so that each configuration decides upon its subsequent transaction blocks. We evaluate an implementation that adds reconfiguration to the Red Belly Blockchain and demonstrates its practical performance in a distributed system.

Offchain protocols aim at bypassing the scalability and privacy limitations of classic blockchains by allowing a subset of participants to execute multiple transactions outside the blockchain. While existing solutions like payment networks and factories depend on a complex routing protocol, other solutions simply require participants to build a childchain, a secondary blockchain where their transactions are privately executed. Unfortunately, all childchain solutions assume either synchrony or a trusted execution environment. In this paper we present Platypus, an offchain protocol that requires neither synchony nor a trusted execution environment. Relieving the need for a trusted execution environment allows Platypus to ensure privacy without trusting a central authority, like Intel, that manufactures dedicated hardware chipset, like SGX. Relieving the need for synchrony means that no attacker can steal coins by leveraging clock drifts or message delays to lure timelocks. In order to prove our algorithm correct, we formalize the chilchain problem as a Byzantine variant of the classic Atomic Commit problem, where closing an offchain protocol is equivalent to committing the whole set of payments previously recorded on the childchain “atomically” on the main chain. Platypus is resilience optimal and we explain how to generalize it to crosschain payments.

Summary We introduce the first concurrent data structure algorithm designed for speculative executions. Prior to this work, concurrent structures were mainly designed for their pessimistic (non‐speculative) accesses to have a predictable asymptotic complexity. Researchers tried to evaluate transactional memory using such structures whose prominent example is the red‐black tree library developed by Oracle Labs that is part of multiple benchmark distributions. Although well‐engineered, such structures remain badly suited for speculative accesses, whose step complexity might raise dramatically with contention. We propose a binary search tree data structure whose key novelty stems from the decoupling of update operations, ie, instead of performing an update operation in a single large transaction, it is split into one transaction that modifies the abstraction state and several other transactions that restructure the tree implementation in the background. This results in a speculation‐friendly tree (s‐tree) that outperforms previous HTM‐based and STM‐based trees by being transiently unbalanced during contention peaks and by rebalancing in quadratic time when contention disappears. In particular, the s‐tree is shown correct, reusable, and speeds up a transaction‐based travel reservation application by up to 3.5×.

Rule updates, such as policy or routing changes, occur frequently and instantly in software-defined networks managed by the controller. In particular, the controller software can modify the network routes by introducing new forwarding rules and deleting old ones in a distributed set of switches, a challenge that has received lots of attention in the last few years. In this paper, we present a problem that consists of determining the appropriate point in the rule update where it is safe to garbage collect old rules. To illustrate the difficulty of the problem, we list the previously proposed assumptions, like the upper-bound on the transmission delay of every packet through the network, and we offer a solution that alleviates these assumptions and significantly reduces the rule update time with a guarantee that no data packet is lost due to the rule alteration through the use of dedicated clean-up packets that detect the absence of in-flight packets. We then prove that the proposed technique guarantees per-packet consistency, blackhole-freedom, and loop-freedom. Our evaluations, via network emulations and real deployment in an SDN testbed, demonstrate that by using the proposed garbage collection solution the rule update times of the two-phase rule update can be reduced by up to 99%.

A long body of research work has led to the conjecture that highly efficient IO processing at user-level would necessarily violate protection. In this paper, we debunk this myth by introducing DLibOS a new paradigm that consists of distributing a library OS on specialized cores to achieve performance and protection at the user-level. Its main novelty consists of leveraging network-on-chip to allow hardware message passing, rather than context switches, for communication between different address spaces. To demonstrate the feasibility of our approach, we implement a driver and a network stack at user-level on a Tilera many-core machine. We define a novel asynchronous socket interface and partition the memory such that the reception, the transmission and the application modify isolated regions. Our high performance results of 4.2 and 3.1 million requests per second obtained on a webserver and the Memcached applications, respectively, confirms the relevance of our design decisions. Finally, we compare DLibOS against a non-protected user-level network stack and show that protection comes at a negligible cost.

This paper introduces a new leaderless Byzantine consensus called the Democratic Byzantine Fault Tolerance (DBFT) for blockchains. While most blockchain consensus protocols rely on a correct leader or coordinator to terminate, our algorithm can terminate even when its coordinator is faulty. The key idea is to allow processes to complete asynchronous rounds as soon as they receive a threshold of messages, instead of having to wait for a message from a coordinator that may be slow. The resulting decentralization is particularly appealing for blockchains for two reasons: (i) each node plays a similar role in the execution of the consensus, hence making the decision inherently “democratic” (ii) decentralization avoids bottlenecks by balancing the load, making the solution scalable. DBFT is deterministic, assumes partial synchrony, is resilience optimal, time optimal and does not need signatures. We first present a simple safe binary Byzantine consensus algorithm, modify it to ensure termination, and finally present an optimized reduction from multivalue consensus to binary consensus whose fast path terminates in 4 message delays.

Recent theoretical attacks conjectured the vulnerabilities of mainstream blockchains through simulations or assumption violations. Unfortunately, previous results typically omit both the nature of the network under which the blockchain code runs and whether blockchains are private, consortium or public. In this paper, we study the public Ethereum blockchain as well as a consortium and private blockchains and quantify the feasibility of man-in-the-middle and double spending attacks against them. To this end, we list important properties of the Ethereum public blockchain topology, we deploy VMs with constrained CPU quantum to mimic the top-10 mining pools of Ethereum and we attack them, by first partitionning the network through BGP hijacking or ARP spooling before issuing a Balance Attack to steal coins. Our results demonstrate that attacking Ethereum is remarkably devastating in a consortium or private context as the adversary can multiply her digital assets by 200, 000× in 10 hours through BGP hijacking whereas it would be almost impossible in a public context.

Rolling upgradeis a widely-used industry technique for updating software while a service provided by multiple instances of the software remains available. In cloud deployments of software, it is usual to implement the update step for rolling upgrade by replacing entire virtual machine instances. During the process of rolling upgrade, various failures may occur due to the complexity of software stack and the uncertainties of cloud platforms. Instance health checking and replacement are standard functionalities in most cloud infrastructures, though these create uncertainty in the duration of the whole upgrade procedure. In contrast, software and configuration errors are not usually detected by infrastructure functionalities, and if these happen, the entire rolling upgrade normally is unsuccessful and the system is left in an unsuitable state. In this paper, we propose an approach, named R2C, which innovates the stat of the art with our early error detection and predictability to increase the robustness of rolling upgrade on cloud platforms. We evaluate our techniques through real life testing in Amazon Web Service (AWS) and through a simulation.

Most blockchain systems are forkable in that they require participants to agree on a chain out of multiple possible branches of blocks. In this paper, we identify a new form of attack, called the Balance attack, against these forkable blockchain systems. The novelty of this attack consists of delaying network communications between multiple subgroups of nodes with balanced mining power. Our theoretical analysis captures the tradeoff between the network delay and the mining power of the attacker needed to double-spend in the GHOST protocol with high probability. We quantify our analysis in the settings of the Ethereum testnet of the R3 consortium where we show that a single machine needs to delay messages for 20 minutes to double spend while a coalition with a third of the mining power would simply need 4 minutes to double spend with 94% of success. We experiment the attack in our private Ethereum chain before arguing for a non-forkable blockchain design to protect against Balance attacks.

Multi-cloud promises to substantially improve fault-tolerance, by tolerating disasters affecting a subset of providers. Unfortunately, multi-cloud solutions are premature and none of them are fully fledged. Their main impediment is the lack of network services: to date, it remains impossible for a customer to setup and control a multi-cloud network. Moreover, manually inter-connecting multiple clouds from various providers is challenging: each cloud provider may offer dissimilar services and incompatible APIs. In this paper, we present the first reconfigurable intercloud network, called Stratosphere. Stratosphere combines recent achievements in the context of container deployment and software defined networking (SDN) to build an SDN-based IP overlay of software containers across providers. Stratosphere aims at dynamically re-routing traffic based on service guarantees, congestion, or failures. We evaluate Stratosphere by reconfiguring the network between major cloud providers, namely Amazon EC2, Microsoft Azure, and Google Cloud. The comparison against the Docker Swarm baseline indicates that this unique reconfiguration feature presents an overhead of only 1% when not used but can improve bandwidth significantly when used.

Blockchain has recently gained momentum. Startups, enterprises, banks, and government agencies around the world are exploring the use of blockchain for broad applications including public registries, supply chains, health records, and voting. Dependability properties, like availability, are critical for many of these applications, but the guarantees offered by the blockchain technology remain unclear, especially from an application perspective. In this paper, we identify the availability limitations of two mainstream blockchains, Ethereum and Bitcoin. We demonstrate that while read availability of blockchains is typically high, write availability - for transaction management - is actually low. For Ethereum, we collected 6 million transactions over a period of 97 days. First, we measured the time for transactions to commit as required by the applications. Second, we observed that some transactions never commit, due to the inherent blockchain design. Third and perhaps even more dramatically, we identify the consequences of the lack of built-in options for explicit abort or retry that can maintain the application in an uncertain state, where transactions remain pending (neither aborted nor committed) for an unknown duration. Finally we propose techniques to mitigate the availability limitations of existing blockchains, and experimentally test the efficacy of these techniques.

Summary In this paper, we introduce the Rotating skip list, the fastest concurrent skip list to date. Existing concurrent data structures experience limited scalability with the growing core count for two main reasons: threads contend while accessing the same shared data, and they require off‐chip communication to synchronize. Our solution combines the rotation of a tree to maintain logarithmic complexity deterministically, a skip list structure to avoid the tree root bottleneck, and no locks to limit cache line bouncing. This combination requires us to trade usual skip list towers for wheels, a novel algorithmic design that favors spatial locality and allows for a constant‐time restructuring operation. We evaluate the performance of our skip list on AMD Opteron and Intel Xeon multicores, show that its rotations guarantee its balance and compare its performance against seven state‐of‐the‐art skip lists and trees using four different synchronisation techniques. The Rotating skip list shows an unprecedented peak performance of 200 Mops/second. Copyright © 2016 John Wiley & Sons, Ltd.

The controller placement problem (CPP) is one of the key challenges of software defined networks (SDNs) to increase performance. Given the locations of n switches, CPP consists of choosing the controller locations that minimize the latency between switches and SDN controllers. In its current form, however, CPP assumes a fixed traffic and no existing solutions adapt the placement to the load. In this paper, we have addressed the dynamic CPP that consists of: 1) determining the locations of controller modules to bound communication latencies and 2) determining the number of controllers per module to support the dynamic load. We propose an algorithm named LiDy+ that runs in O(n2) and combines a controller module placement algorithm with a dynamic flow management algorithm. We evaluate the number of controllers, the controller utilization, and the power consumption and the maintenance cost of LiDy+ on both sparse and dense networks. Our comparison against a previous solution shows that LiDy+ does not only achieve a smaller number of controllers and a higher controller utilization but also incurs less energy and maintenance costs than the previous solution. Finally, we run LiDy+ in a large-scale environment where the previous solution of time complexity Ω(n2logn) is impractical.

Dynamic virtual machine consolidation (DVMC) using live migration is one of the most promising solutions to reduce energy consumption in cloud data centers. Distributed DVMC often aggressively consolidates virtual machines (VMs) at the high expense of Service Level Agreement (SLA) of customers due to virtual machines (VMs) workload fluctuations. To alleviate this, static and adaptive threshold algorithms were proposed. However, the former is unable to predict the VMs future resource demands and the latter calculates a fixed threshold value for all physical machines (PMs) while each PM hosts VMs with different workload patterns. Moreover, both methods cannot consolidate VMs to maintain PMs in a long-term safe state. To overcome these problems, we propose a fully distributed and threshold-free DVMC algorithm called, GLAP. We combine Q-Learning with a gossip-based protocol to characterize workload patterns of VMs and take consolidation decisions. We also propose a novel two-phase distributed algorithm by which PMs unify the learned pattern which is vital for efficient execution of the algorithm. Finally, we compare GLAP experimentally against three existing techniques and show that GLAP reduces by from 43% to 78% the number of overloaded PMs under the Google Cluster VMs workload traces.

SDN efficiency is driven by the ability of controllers to process small packets based on a global view of the network. The goal of such controllers is thus to treat new flows coming from hundreds of switches in a timely fashion. In this paper, we show this ideal remains impossible through the most extensive evaluation of SDN controllers. We evaluated five state-of-the-art SDN controllers and discovered that the most efficient one spends a fifth of his time in packet serialization. More dramatically, we show that this limitation is inherent to the object oriented design principle of these controllers. They all treat each single packet as an individual object, a limitation that induces an unaffordable per-packet overhead. To eliminate the responsibility of the hardware from our results, we ported these controllers on a network-efficient architecture, Tilera, and showed even worse performance. We thus argue for an in-depth rethinking of the design of the SDN controller into a lower level software that leverages both operating system optimizations and modern hardware features.

Most popular blockchain solutions rely on proof-of-work to guarantee that participants reach consensus on a unique block per index of the chain. As consensus is impossible in the general case, it seems that these blockchain systems require messages are delivered fast and no participant mines faster than the crowd. To date, no experimental settings have however been proposed to demonstrate this hypothesis. In this paper, we identify conditions under which these blockchain systems fail to ensure consensus and present a reproducible execution on our Ethereum private chain. To this end, we introduce the Blockchain Anomaly, the impossibility for the blockchain to guarantee that a committed transaction is not abortable. This anomaly may translate into dramatic consequences for the user of proof-of-work blockchains. Named after the infamous Paxos anomaly, this anomaly makes dependent transactions, like “Bob sends money to Carole after he received money from Alice” impossible and may lead to double spending. We also explain how the anomaly differs from a 51-percent attack and how one could avoid it by adapting the Ethereum implementation or by exploiting smart contracts.

Blockchain is an emerging technology for decentralized and transactional data sharing across a large network of untrusted participants. It enables new forms of distributed software architectures, where components can find agreements on their shared states without trusting a central integration point or any particular participating components. Considering the blockchain as a software connector helps make explicitly important architectural considerations on the resulting performance and quality attributes (for example, security, privacy, scalability and sustainability) of the system. Based on our experience in several projects using blockchain, in this paper we provide rationales to support the architectural decision on whether to employ a decentralized blockchain as opposed to other software solutions, like traditional shared data storage. Additionally, we explore specific implications of using the blockchain as a software connector including design trade-offs regarding quality attributes.

Peer to peer (P2P) systems have moved from application specific architectures to a generic service oriented design philosophy. This raised interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The slicing problem consists of partitioning a P2P network into$k$groups (slices) of a given portion of the network nodes that share similar resource values. As the network is large and dynamic this partitioning is continuously updated without any node knowing the network size. In this paper, we propose the first algorithm to solve the slicing problem. We introduce the metric of slice disorder and show that the existing ordering algorithm cannot nullify this disorder. We propose a new algorithm that speeds up the existing ordering algorithm but that suffers from the same inaccuracy. Then, we propose another algorithm based on ranking that is provably convergent under reasonable assumptions. In particular, we notice experimentally that ordering algorithms suffer from resource-correlated churn while the ranking algorithm can cope with it. These algorithms are proved viable theoretically and experimentally.

Rolling upgrade consists of upgrading progressively the servers of a distributed system to reduce service downtime.Upgrading a subset of servers requires a well-engineered cluster membership protocol to maintain, in the meantime, the availability of the system state. Existing cluster membership reconfigurations, like CoreOS etcd, rely on a primary not only for reconfiguration but also for storing information. At any moment, there can be at most one primary, whose replacement induces disruption. We propose Rollup, a non-disruptive rolling upgrade protocol with a fast consensus-based reconfiguration. Rollup relies on a candidate leader only for the reconfiguration and scalable biquorums for service requests. While Rollup implements a non-disruptive cluster membership protocol, it does not offer a full-fledged coordination service. We analyzed Rollup theoretically and experimentally on an isolated network of 26 physical machines and an Amazon EC2 cluster of 59 virtual machines. Our results show an 8-fold speedup compared to a rolling upgrade based on a primary for reconfiguration.

The controller placement problem (CPP) is one of the key challenges of software defined networks to increase performance. Given the locations of switches, CPP consists of choosing the controller locations that minimize the latency between switches and controllers. In its current form, however, CPP assumes a fixed traffic and no existing solutions adapt the placement to the load. In this paper, we introduce the dynamic controller placement problem that consists of (i) determining the locations of controller modules to bound communication latencies, and of (ii) determining the number of controllers per module to support the load. We propose, LiDy, a solution that combines a controller placement algorithm with a dynamic flow management algorithm. We evaluate the latency and the controller utilization of LiDy on sparse and dense regions. Our results show that, in all settings, LiDy achieves a higher utilization than the most recent controller placement solution.

In this paper, we present the most extensive comparison of synchronization techniques. We evaluate 5 different synchronization techniques through a series of 31 data structure algorithms from the recent literature on 3 multicore platforms from Intel, Sun Microsystems and AMD. To this end, we developed in C/C++ and Java a new micro-benchmark suite, called Synchrobench, hence helping the community evaluate new data structures and synchronization techniques. The main conclusion of this evaluation is threefold: (i) although compare-and-swap helps achieving the best performance on multicores, doing so correctly is hard; (ii) optimistic locking offers varying performance results while transactional memory offers more consistent results; and (iii) copy-on-write and read-copy-update suffer more from contention than any other technique but could be combined with others to derive efficient algorithms.

Rolling upgrade is a practical industry technique for online updating of software in distributed systems. This paper focuses on rolling upgrade of software versions in virtual machine instances on cloud computing platforms, when various failures may occur. An operator can choose the number of instances that are updated in one round and system environments to minimise completion time, availability degradation, and monetary cost for entire rolling upgrade, and hence this is a multi-objective optimisation problem. To predict completion time in the presence of failures, we offer a stochastic model that represents the dynamics of rolling upgrade. To reduce the computational effort of decision making for large scale complex systems, we propose a technique that can find a Pareto set quickly via an upper bound of the expected completion time. Then an optimum of the original problem can be chosen from this set of potential solutions. We validate our approach to minimise the objectives, through both experiments in Amazon Web Service (AWS) and simulations.

Resource capacity is often over provisioned to primarily deal with short periods of peak load. Shaping these peaks by shifting them to low utilization periods (valleys) is referred to as "resource consumption shaping". While originally aimed at the data center level, the resource consumption shaping we consider focuses on local resources, like CPU or I/O as we have identified that individual jobs also incur load peaks and valleys on these resources. In this paper, we present Local Resource Shaper (LRS), which limits fairness in resource sharing between co-located MapReduce tasks. LRS enables Hadoop to maximize resource utilization and minimize resource contention independently of job type. Co-located MapReduce tasks are often prone to resource contention (i.e., Load peak) due to similar resource usage patterns particularly with traditional fair resource sharing. In essence, LRS differentiates co-located tasks through active and passive slots that serve as containers for interchangeable map or reduce tasks. LRS lets an active slot consume as much resources as possible, and a passive slot make use of any unused resources. LRS leverages such slot differentiation with its new scheduler, Interleave. Our results show that LRS always outperforms the best static slot configuration with three Hadoop schedulers in terms of both resource utilization and performance.

This paper presents a new non-blocking skip list algorithm. The algorithm alleviates contention by localizing synchronization at the least contended part of the structure without altering consistency of the implemented abstraction. The key idea lies in decoupling a modification to the structure into two stages: an eager abstract modification that returns quickly and whose update affects only the bottom of the structure, and a lazy selective adaptation updating potentially the entire structure but executed continuously in the background. On SPECjbb as well as on micro-benchmarks, we compared the performance of our new non-blocking skip list against the performance of the JDK non-blocking skip list. The results indicate that our implementation can me more than twice as fast as the JDK skip list.

As the classic transactional abstraction is sometimes considered too restrictive in leveraging parallelism, a lot of work has been devoted to devising relaxed transactional models with the goal of improving concurrency. Nevertheless, the quest for improving concurrency has somehow led to neglect one of the most appealing aspects of transactions: software composition, namely, the ability to develop pieces of software independently and compose them into applications that behave correctly in the face of concurrency. Indeed, a closer look at relaxed transactional models reveals that they do jeopardize composition, raising the fundamental question whether it is at all possible to devise such models while preserving composition. This paper shows that the answer is positive. We present outheritance, a necessary and sufficient condition for a (potentially relaxed) transactional memory to support composition. Basically, outheritance requires child transactions to pass their conflict information to their parent transaction, which in turn maintains this information until commit time. Concrete instantiations of this idea have been used before, classic transactions being the most prevalent example, but we believe to be the first to capture this as a general principle as well as to prove that it is, strictly speaking, equivalent to ensuring composition. We illustrate the benefits of outheritance using elastic transactions and show how they can satisfy outheritance and provide composition without hampering concurrency. We leverage this to present a new (transactional) Java package, a composable alternative to the concurrency package of the JDK, and evaluate efficiency through an implementation that speeds up state of the art software transactional memory implementations (TL2, LSA, SwissTM) by almost a factor of 3.

Transactional memory is an appealing paradigm for concurrent programming. Many software implementations of the paradigm were proposed in the last decades for both shared memory multi-core systems and clusters of distributed machines. However, chip manufacturers have started producing many-core architectures, with low network-on-chip communication latency and limited support for cache-coherence, rendering existing transactional memory implementations inapplicable.

No abstract available.

We introduce the first binary search tree algorithm designed for speculative executions. Prior to this work, tree structures were mainly designed for their pessimistic (non-speculative) accesses to have a bounded complexity. Researchers tried to evaluate transactional memory using such tree structures whose prominent example is the red-black tree library developed by Oracle Labs that is part of multiple benchmark distributions. Although well-engineered, such structures remain badly suited for speculative accesses, whose step complexity might raise dramatically with contention.

In this work, we present transaction polymorphism, a synchronization technique that consists of providing more control to the programmer than traditional (i.e., monomorphic) transactions to achieve comparable performance to generic lock-based and lock-free solutions.

Peer-to-peer (P2P) architectures are popular for tasks such as collaborative download, VoIP telephony, and backup. To maximize performance in the face of widely variable storage capacities and bandwidths, such systems typically need to shift work from poor nodes to richer ones. Similar requirements are seen in today's large data centers, where machines may have widely variable configurations, loads, and performance. In this paper, we consider the slicing problem, which involves partitioning the participating nodes into k subsets using a one-dimensional attribute, and updating the partition as the set of nodes and their associated attributes change. The mechanism thus facilitates the development of adaptive systems. We begin by motivating this problem statement and reviewing prior work. Existing algorithms are shown to have problems with convergence, manifesting as inaccurate slice assignments, and to adapt slowly as conditions change. Our protocol, Sliver, has provably rapid convergence, is robust under stress and is simple to implement. We present both theoretical and experimental evaluations of the protocol.

We adress the problem of estimating in a fully distributed way the dynamism over a network, called the churn. This BA presents, as far as we know, the first distributed method for monitoring churn in arbitrary networks, subject to arbitrary node departure and arrival patterns.

No abstract available.

Peer to peer (P2P) systems are moving from application specific architectures to a generic service oriented design philosophy. This raises interesting problems in connection with providing useful P2P middleware services capable of dealing with resource assignment and management in a large-scale, heterogeneous and unreliable environment. The slicing service, has been proposed to allow for an automatic partitioning of P2P networks into groups (slices) that represent a controllable amount of some resource and that are also relatively homogeneous with respect to that resource. In this paper we propose two gossip-based algorithms to solve the distributed slicing problem. The first algorithm speeds up an existing algorithm sorting a set of uniform random numbers. The second algorithm statistically approximates the rank of nodes in the ordering. The scalability, efficiency and resilience to dynamics of both algorithms rely on their gossip-based models. These algorithms are proved viable theoretically and experimentally.