37 Search Results for "Romano, Paolo"


Volume

LIPIcs, Volume 184

24th International Conference on Principles of Distributed Systems (OPODIS 2020)

OPODIS 2020, December 14-16, 2020, Strasbourg, France (Virtual Conference)

Editors: Quentin Bramas, Rotem Oshman, and Paolo Romano

Document
Complete Volume
LIPIcs, Volume 184, OPODIS 2020, Complete Volume

Authors: Quentin Bramas, Rotem Oshman, and Paolo Romano

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
LIPIcs, Volume 184, OPODIS 2020, Complete Volume

Cite as

24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 1-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@Proceedings{bramas_et_al:LIPIcs.OPODIS.2020,
  title =	{{LIPIcs, Volume 184, OPODIS 2020, Complete Volume}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{1--514},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020},
  URN =		{urn:nbn:de:0030-drops-134842},
  doi =		{10.4230/LIPIcs.OPODIS.2020},
  annote =	{Keywords: LIPIcs, Volume 184, OPODIS 2020, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Quentin Bramas, Rotem Oshman, and Paolo Romano

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2020.0,
  author =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.0},
  URN =		{urn:nbn:de:0030-drops-134854},
  doi =		{10.4230/LIPIcs.OPODIS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Big Data Processing: Security and Scalability Challenges (Invited Talk)

Authors: Pascal Felber

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
The processing of large amonts of data requires significant computing power and scalable architectures. This trend makes the use of Cloud computing and off-premises data centres particularly attractive, but exposes companies to the risk of data theft. This is a key challenge toward exploiting public Clouds, as data represents for many companies their most valuable asset. In this talk, we will discuss about mechanisms to ensure secure and privacy-preserving Big Data processing on computing architectures supporting horizontal and vertical scalability.

Cite as

Pascal Felber. Big Data Processing: Security and Scalability Challenges (Invited Talk). In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{felber:LIPIcs.OPODIS.2020.1,
  author =	{Felber, Pascal},
  title =	{{Big Data Processing: Security and Scalability Challenges}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.1},
  URN =		{urn:nbn:de:0030-drops-134863},
  doi =		{10.4230/LIPIcs.OPODIS.2020.1},
  annote =	{Keywords: Big Data}
}
Document
Invited Talk
Byzantine Agreement and SMR with Sub-Quadratic Message Complexity (Invited Talk)

Authors: Idit Keidar

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
Byzantine Agreement (BA) has been studied for four decades by now, but until recently, has been considered at a fairly small scale. In recent years, however, we begin to see practical use-cases of BA in large-scale systems, which motivates a push for reduced communication complexity. Dolev and Reischuk’s well-known lower bound stipulates that any deterministic algorithm requires Ω(n²) communication in the worst-case, and until fairly recently, almost all randomized algorithms have had at least quadratic complexity as well. This talk will present two new algorithms breaking this barrier. The first part of the talk will consider a fully asynchronous setting, focusing on randomized BA whose safety and liveness guarantees hold with high probability. It will present the first asynchronous Byzantine Agreement algorithm with sub-quadratic communication complexity. This algorithm exploits VRF-based committee sampling, which it adapts for the asynchronous model. The second part of the talk will consider the eventually synchronous model, where BA and State Machine Replication (SMR) can be solved with deterministic safety and liveness guarantees. In this context, randomization is used in order to reduce the expected communication complexity. The talk will present an algorithm for round synchronization, which is a building block for BA and SMR and constitutes the main performance bottleneck therein. It will present an algorithm that, for the first time, achieves round synchronization with expected linear message complexity and expected constant latency. Existing protocols can use this round synchronization algorithm to solve Byzantine SMR with the same asymptotic performance. The first part of the talk is based on joint work with Shir Cohen and Alexander Spiegelman, and the second part of the talk is based on joint work with Oded Naor.

Cite as

Idit Keidar. Byzantine Agreement and SMR with Sub-Quadratic Message Complexity (Invited Talk). In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{keidar:LIPIcs.OPODIS.2020.2,
  author =	{Keidar, Idit},
  title =	{{Byzantine Agreement and SMR with Sub-Quadratic Message Complexity}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.2},
  URN =		{urn:nbn:de:0030-drops-134874},
  doi =		{10.4230/LIPIcs.OPODIS.2020.2},
  annote =	{Keywords: Distributed Computing, Byzantine Agreement}
}
Document
Invited Talk
Can We Automate Our Own Work - or Show That It Is Hard? (Invited Talk)

Authors: Jukka Suomela

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
Computer scientists seek to understand what can be automated, but what do we know about automating our own work? Can we outsource our own research questions to computers? In this talk I will discuss this question from the perspective of the theory of distributed computing. I will present not only recent examples of human-computer-collaborations that have resulted in major breakthroughs in our understanding of distributed computing, but I will also explore the fundamental limits of such approaches.

Cite as

Jukka Suomela. Can We Automate Our Own Work - or Show That It Is Hard? (Invited Talk). In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{suomela:LIPIcs.OPODIS.2020.3,
  author =	{Suomela, Jukka},
  title =	{{Can We Automate Our Own Work - or Show That It Is Hard?}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.3},
  URN =		{urn:nbn:de:0030-drops-134881},
  doi =		{10.4230/LIPIcs.OPODIS.2020.3},
  annote =	{Keywords: Distributed Computing}
}
Document
Byzantine Lattice Agreement in Asynchronous Systems

Authors: Xiong Zheng and Vijay Garg

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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 < 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 < 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 < n/3 Byzantine failures.

Cite as

Xiong Zheng and Vijay Garg. Byzantine Lattice Agreement in Asynchronous Systems. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{zheng_et_al:LIPIcs.OPODIS.2020.4,
  author =	{Zheng, Xiong and Garg, Vijay},
  title =	{{Byzantine Lattice Agreement in Asynchronous Systems}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.4},
  URN =		{urn:nbn:de:0030-drops-134894},
  doi =		{10.4230/LIPIcs.OPODIS.2020.4},
  annote =	{Keywords: Byzantine Lattice Agreement, Asynchronous}
}
Document
Heterogeneous Paxos

Authors: Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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 reduce latency.

Cite as

Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers. Heterogeneous Paxos. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{sheff_et_al:LIPIcs.OPODIS.2020.5,
  author =	{Sheff, Isaac and Wang, Xinwen and van Renesse, Robbert and Myers, Andrew C.},
  title =	{{Heterogeneous Paxos}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.5},
  URN =		{urn:nbn:de:0030-drops-134909},
  doi =		{10.4230/LIPIcs.OPODIS.2020.5},
  annote =	{Keywords: Consensus, Trust, Heterogeneous Trust}
}
Document
Multi-Threshold Asynchronous Reliable Broadcast and Consensus

Authors: Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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 multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as f ≤ t_v, f ≤ t_c and f ≤ t_t respectively. For consensus, we consider both variants of (1-ε)-consensus and almost-surely terminating consensus, where termination is guaranteed with probability (1-ε) 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-ε)-consensus is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n.

Cite as

Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang. Multi-Threshold Asynchronous Reliable Broadcast and Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{hirt_et_al:LIPIcs.OPODIS.2020.6,
  author =	{Hirt, Martin and Kastrati, Ard and Liu-Zhang, Chen-Da},
  title =	{{Multi-Threshold Asynchronous Reliable Broadcast and Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.6},
  URN =		{urn:nbn:de:0030-drops-134917},
  doi =		{10.4230/LIPIcs.OPODIS.2020.6},
  annote =	{Keywords: broadcast, byzantine agreement, multi-threshold}
}
Document
Echo-CGC: A Communication-Efficient Byzantine-Tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network

Authors: Qinzi Zhang and Lewis Tseng

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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., [Gupta and Vaidya, 2020; El-Mhamdi et al., 2020; Chen et al., 2017]. One limitation of prior algorithms in this domain is the 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 a 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. Motivated by this observation, we aim to reduce the communication complexity of Byzantine-tolerant DML algorithms in the single-hop radio network [Alistarh et al., 2010; Bhandari and Vaidya, 2005; Koo, 2004]. Inspired by the CGC filter developed by Gupta and Vaidya, PODC 2020 [Gupta and Vaidya, 2020], we propose a gradient descent-based algorithm, Echo-CGC. Our main novelty is a mechanism to utilize the broadcast properties of the radio network to avoid transmitting the raw gradients (full d-dimensional vectors). In the radio network, each worker is able to overhear previous gradients that were transmitted to the parameter server. Roughly speaking, in Echo-CGC, 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 ≫ n). 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 standard assumptions.

Cite as

Qinzi Zhang and Lewis Tseng. Echo-CGC: A Communication-Efficient Byzantine-Tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{zhang_et_al:LIPIcs.OPODIS.2020.7,
  author =	{Zhang, Qinzi and Tseng, Lewis},
  title =	{{Echo-CGC: A Communication-Efficient Byzantine-Tolerant Distributed Machine Learning Algorithm in Single-Hop Radio Network}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.7},
  URN =		{urn:nbn:de:0030-drops-134927},
  doi =		{10.4230/LIPIcs.OPODIS.2020.7},
  annote =	{Keywords: Distributed Machine Learning, Single-hop Radio Network, Byzantine Fault, Communication Complexity, Wireless Communication, Parameter Server}
}
Document
AKSEL: Fast Byzantine SGD

Authors: Amine Boussetta, El-Mahdi El-Mhamdi, Rachid Guerraoui, Alexandre Maurer, and Sébastien Rouault

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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 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 average the gradients estimated by the workers. However, averaging is not resilient to even one single Byzantine failure of a worker. Many alternative 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 < < f). We propose Aksel, a new scalable median-based GAR with optimal time complexity (𝒪(nd)), optimal breakdown point (n > 2f) and the lowest upper bound on the expected angular error (𝒪(√d)) among full gradient approaches. We also study the actual angular error of Aksel when the gradient distribution is normal and show that it only grows in 𝒪(√dlog{n}), which is the first logarithmic upper bound ever proven on the number of workers n assuming an optimal breakdown point. We also report on an empirical evaluation of Aksel on various classification tasks, which we compare to alternative GARs against state-of-the-art attacks. 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, Aksel can also easily be adapted to multi-server architectures that tolerate the Byzantine behavior of a fraction of the servers.

Cite as

Amine Boussetta, El-Mahdi El-Mhamdi, Rachid Guerraoui, Alexandre Maurer, and Sébastien Rouault. AKSEL: Fast Byzantine SGD. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{boussetta_et_al:LIPIcs.OPODIS.2020.8,
  author =	{Boussetta, Amine and El-Mhamdi, El-Mahdi and Guerraoui, Rachid and Maurer, Alexandre and Rouault, S\'{e}bastien},
  title =	{{AKSEL: Fast Byzantine SGD}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.8},
  URN =		{urn:nbn:de:0030-drops-134931},
  doi =		{10.4230/LIPIcs.OPODIS.2020.8},
  annote =	{Keywords: Machine learning, Stochastic gradient descent, Byzantine failures}
}
Document
ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication

Authors: Alexander Spiegelman, Arik Rinberg, and Dahlia Malkhi

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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 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 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 waves of parallel leaders and selecting a 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.

Cite as

Alexander Spiegelman, Arik Rinberg, and Dahlia Malkhi. ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{spiegelman_et_al:LIPIcs.OPODIS.2020.9,
  author =	{Spiegelman, Alexander and Rinberg, Arik and Malkhi, Dahlia},
  title =	{{ACE: Abstract Consensus Encapsulation for Liveness Boosting of State Machine Replication}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.9},
  URN =		{urn:nbn:de:0030-drops-134948},
  doi =		{10.4230/LIPIcs.OPODIS.2020.9},
  annote =	{Keywords: Framework, Asynchronous, Consensus boosting, State Machine Replication}
}
Document
Security Analysis of Ripple Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


Abstract
The Ripple network is one of the most prominent blockchain platforms and its native XRP token currently has one of the highest cryptocurrency market capitalizations. The Ripple consensus protocol powers this 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 initially by Ripple, and there is currently no appropriate understanding of its workings and its properties in the literature. This paper closes this gap and 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.

Cite as

Ignacio Amores-Sesar, Christian Cachin, and Jovana Mićić. Security Analysis of Ripple Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2020.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Mi\'{c}i\'{c}, Jovana},
  title =	{{Security Analysis of Ripple Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.10},
  URN =		{urn:nbn:de:0030-drops-134956},
  doi =		{10.4230/LIPIcs.OPODIS.2020.10},
  annote =	{Keywords: Ripple, Blockchain, Quorums, Consensus}
}
Document
Information Theoretic HotStuff

Authors: Ittai Abraham and Gilad Stern

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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, and in each view change, each party sends only a constant number of words to every other party. This yields an O(n²) 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.

Cite as

Ittai Abraham and Gilad Stern. Information Theoretic HotStuff. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2020.11,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{Information Theoretic HotStuff}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.11},
  URN =		{urn:nbn:de:0030-drops-134969},
  doi =		{10.4230/LIPIcs.OPODIS.2020.11},
  annote =	{Keywords: byzantine agreement, partial synchrony, bounded space}
}
Document
Rational Behaviors in Committee-Based Blockchains

Authors: Yackolley Amoussou-Guenou, Bruno Biais, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)


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 encapsulate the main actions of the participants: voting for a block, and 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.

Cite as

Yackolley Amoussou-Guenou, Bruno Biais, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni. Rational Behaviors in Committee-Based Blockchains. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{amoussouguenou_et_al:LIPIcs.OPODIS.2020.12,
  author =	{Amoussou-Guenou, Yackolley and Biais, Bruno and Potop-Butucaru, Maria and Tucci-Piergiovanni, Sara},
  title =	{{Rational Behaviors in Committee-Based Blockchains}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.12},
  URN =		{urn:nbn:de:0030-drops-134973},
  doi =		{10.4230/LIPIcs.OPODIS.2020.12},
  annote =	{Keywords: BFT Consensus, Blockchains, Game Theory}
}
  • Refine by Author
  • 3 Romano, Paolo
  • 2 Attiya, Hagit
  • 2 Bramas, Quentin
  • 2 Castañeda, Armando
  • 2 Censor-Hillel, Keren
  • Show More...

  • Refine by Classification
  • 17 Theory of computation → Distributed algorithms
  • 9 Computing methodologies → Distributed algorithms
  • 6 Theory of computation → Concurrent algorithms
  • 6 Theory of computation → Distributed computing models
  • 4 Computer systems organization → Dependable and fault-tolerant systems and networks
  • Show More...

  • Refine by Keyword
  • 3 Distributed Computing
  • 2 Asynchronous
  • 2 Broadcast
  • 2 Byzantine failures
  • 2 Consensus
  • Show More...

  • Refine by Type
  • 36 document
  • 1 volume

  • Refine by Publication Year
  • 36 2021
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail