39 Search Results for "Miller, Avery"

Volume

LIPIcs, Volume 153

23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

OPODIS 2019, December 17-19, 2019, Neuchâtel, Switzerland

Editors: Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller

Document
DOI: 10.4230/LIPIcs.DISC.2023.29
Fast Deterministic Rendezvous in Labeled Lines

Authors: Avery Miller and Andrzej Pelc

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Two mobile agents, starting from different nodes of a network modeled as a graph, and woken up at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous in the infinite line, i.e., the infinite graph with all nodes of degree 2. Each node has a distinct label which is a positive integer. An agent currently located at a node can see its label and both ports 0 and 1 at the node. The time of rendezvous is the number of rounds until meeting, counted from the starting round of the earlier agent. We consider three scenarios. In the first scenario, each agent knows its position in the line, i.e., each of them knows its initial distance from the smallest-labeled node, on which side of this node it is located, and the direction towards it. For this scenario, we design a rendezvous algorithm working in time O(D), where D is the initial distance between the agents. This complexity is clearly optimal. In the second scenario, each agent knows a priori only the label of its starting node and the initial distance D between them. In this scenario, we design a rendezvous algorithm working in time O(Dlog^*𝓁), where 𝓁 is the larger label of the starting nodes. We also prove a matching lower bound Ω(Dlog^*𝓁). Finally, in the most general scenario, where each agent knows a priori only the label of its starting node, we design a rendezvous algorithm working in time O(D²(log^*𝓁)³), which is thus at most cubic in the lower bound. All our results remain valid (with small changes) for arbitrary finite lines and for cycles. Our algorithms are drastically better than approaches that use graph exploration, which have running times that depend on the size or diameter of the graph. Our main methodological tool, and the main novelty of the paper, is a two way reduction: from fast colouring of the infinite labeled line using a constant number of colours in the LOCAL model to fast rendezvous in this line, and vice-versa. In one direction we use fast node colouring to quickly break symmetry between the identical agents. In the other direction, a lower bound on colouring time implies a lower bound on the time of breaking symmetry between the agents, and hence a lower bound on their meeting time.
Cite as

Avery Miller and Andrzej Pelc. Fast Deterministic Rendezvous in Labeled Lines. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{miller_et_al:LIPIcs.DISC.2023.29,
  author =	{Miller, Avery and Pelc, Andrzej},
  title =	{{Fast Deterministic Rendezvous in Labeled Lines}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.29},
  URN =		{urn:nbn:de:0030-drops-191550},
  doi =		{10.4230/LIPIcs.DISC.2023.29},
  annote =	{Keywords: rendezvous, deterministic algorithm, mobile agent, labeled line, graph colouring}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2019
LIPIcs, Vol. 153, OPODIS 2019, Complete Volume

Authors: Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
LIPIcs, Vol. 153, OPODIS 2019, Complete Volume
Cite as

23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 1-564, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{felber_et_al:LIPIcs.OPODIS.2019,
  title =	{{LIPIcs, Vol. 153, OPODIS 2019, Complete Volume}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{1--564},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019},
  URN =		{urn:nbn:de:0030-drops-119510},
  doi =		{10.4230/LIPIcs.OPODIS.2019},
  annote =	{Keywords: LIPIcs, Vol. 153, OPODIS 2019, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

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

23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{felber_et_al:LIPIcs.OPODIS.2019.0,
  author =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{0:i--0:xxii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.0},
  URN =		{urn:nbn:de:0030-drops-117869},
  doi =		{10.4230/LIPIcs.OPODIS.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2019.1
Demystifying Bitcoin (Keynote Abstract)

Authors: Rachid Guerraoui

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
This talk will explain the bitcoin algorithm from the distributed computing perspective, precisely define the underlying double-payment problem, and present a much simpler alternative to solve the problem without relying on consensus and consuming so much energy. Rachid Guerraoui is professor in Computer Science at EPFL where he leads the Distributed Computing Laboratory. He worked in the past with École des Mines de Paris, CEA Saclay, HP Labs in Palo Alto and MIT. He has been elected ACM Fellow and Professor of the College de France. He was awarded a Senior ERC Grant and a Google Focused Award.
Cite as

Rachid Guerraoui. Demystifying Bitcoin (Keynote Abstract). In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guerraoui:LIPIcs.OPODIS.2019.1,
  author =	{Guerraoui, Rachid},
  title =	{{Demystifying Bitcoin}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.1},
  URN =		{urn:nbn:de:0030-drops-117870},
  doi =		{10.4230/LIPIcs.OPODIS.2019.1},
  annote =	{Keywords: Bitcoin, Payment systems}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2019.2
Distributed Optimization And Approximation: How Difficult Can It Be? (Keynote Abstract)

Authors: Keren Censor-Hillel

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We know that exact distributed algorithms for optimization problems cannot be fast. To overcome these barriers, very efficient approximation algorithms have been designed in various distributed settings. But for very small approximation factors, a mystery remains: Why do we not have fast distributed algorithms for very small approximations factors in bandwidth restricted settings? This talk will overview the state-of-the-art of distributed optimization and approximation algorithms and discuss the major challenges in determining the complexity of small approximations.
Cite as

Keren Censor-Hillel. Distributed Optimization And Approximation: How Difficult Can It Be? (Keynote Abstract). In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{censorhillel:LIPIcs.OPODIS.2019.2,
  author =	{Censor-Hillel, Keren},
  title =	{{Distributed Optimization And Approximation: How Difficult Can It Be?}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.2},
  URN =		{urn:nbn:de:0030-drops-117886},
  doi =		{10.4230/LIPIcs.OPODIS.2019.2},
  annote =	{Keywords: Distributed graph algorithms, Optimization and approximations}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2019.3
Snap ML - Accelerated Machine Learning for Big Data (Keynote Abstract)

Authors: Haris Pozidis

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Snap Machine Learning (Snap ML) is a new software library for training popular machine learning models, characterized by very high performance, scalability to TB-scale datasets and high resource efficiency. It continuously evolves and currently supports generalized linear models, decision trees, random forests and gradient boosting machines. Snap ML has been built to address the needs of business applications, which often have to deal with high-volume data, react fast to changing environments, and use resources efficiently to drive down cost. The high efficiency of Snap ML, in particular in dealing with big data, comes from innovations in distributed optimization, among other things. This talk will review the principles of the Snap ML library, explain how it achieves high speed and scalability, and present several cases of business workloads that demonstrate the benefits offered by Snap ML. Haris Pozidis manages the Cloud Storage and Analytics group at IBM Research in Zurich, Switzerland. He was with Philips Research, Eindhoven, The Netherlands, before joining IBM. He has worked on read channel design for DVD and Blu-ray Disc at Philips, and played a key role in developing the first scanning probe-based data storage system at IBM, the “Millipede”. His current focus is on the development of Flash memory controllers for all-flash arrays, on phase change memory technology and system solutions, and on accelerated software libraries for machine learning. He holds over 120 US patents, has co-authored more than 120 publications, is an IBM Principal Research Scientist and Master Inventor, and a Senior Member of the IEEE.
Cite as

Haris Pozidis. Snap ML - Accelerated Machine Learning for Big Data (Keynote Abstract). In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pozidis:LIPIcs.OPODIS.2019.3,
  author =	{Pozidis, Haris},
  title =	{{Snap ML - Accelerated Machine Learning for Big Data}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.3},
  URN =		{urn:nbn:de:0030-drops-117899},
  doi =		{10.4230/LIPIcs.OPODIS.2019.3},
  annote =	{Keywords: Machine Learning, Big Data}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.4
FairLedger: A Fair Blockchain Protocol for Financial Institutions

Authors: Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Financial institutions nowadays are looking into technologies for permissioned blockchains. A major effort in this direction is Hyperledger, an open source project hosted by the Linux Foundation and backed by a consortium of over a hundred companies. A key component in permissioned blockchain protocols is a byzantine fault tolerant (BFT) consensus engine that orders transactions. However, currently available BFT solutions in Hyperledger (as well as in the literature at large) are inadequate for financial settings; they are not designed to ensure fairness or to tolerate the selfish behavior that inevitably arises when financial institutions strive to maximize their own profit. We present FairLedger, a permissioned BFT blockchain protocol, which is fair, deigned to deal with rational behavior, and, no less important, easy to understand and implement. Our secret sauce is a new communication abstraction called detectable all-to-all (DA2A), which allows us to detect players (byzantine or rational) that deviate from the protocol and punish them. We implement FairLedger in the Hyperledger open source project using the Iroha framework - one of the biggest projects therein. To evaluate FairLegder’s performance, we also implement it in the PBFT framework and compare the two protocols. Our results show that in failure-free scenarios in wide-area settings, FairLedger achieves better throughput than both Iroha’s implementation and PBFT.
Cite as

Kfir Lev-Ari, Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. FairLedger: A Fair Blockchain Protocol for Financial Institutions. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{levari_et_al:LIPIcs.OPODIS.2019.4,
  author =	{Lev-Ari, Kfir and Spiegelman, Alexander and Keidar, Idit and Malkhi, Dahlia},
  title =	{{FairLedger: A Fair Blockchain Protocol for Financial Institutions}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.4},
  URN =		{urn:nbn:de:0030-drops-117904},
  doi =		{10.4230/LIPIcs.OPODIS.2019.4},
  annote =	{Keywords: Blockchain, Fairness, Byzantine fault tolerance, Rational players, Equilibrium}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.5
Deconstructing Stellar Consensus

Authors: Álvaro García-Pérez and Maria A. Schett

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Some of the recent blockchain proposals, such as Stellar and Ripple, allow for open membership while using quorum-like structures typical for classical Byzantine consensus with closed membership. This is achieved by constructing quorums in a decentralised way: each participant independently chooses whom to trust, and quorums arise from these individual decisions. Unfortunately, the consensus protocols underlying such blockchains are poorly understood, and their correctness has not been rigorously investigated. In this paper we rigorously prove correct the Stellar Consensus Protocol (SCP), with our proof giving insights into the protocol structure and its use of lower-level abstractions. To this end, we first propose an abstract version of SCP that uses as a black box Stellar’s federated voting primitive (analogous to reliable Byzantine broadcast), previously investigated by García-Pérez and Gotsman [Álvaro García-Pérez and Alexey Gotsman, 2018]. The abstract consensus protocol highlights a modular structure in Stellar and can be proved correct by reusing the previous results on federated voting. However, it is unsuited for realistic implementations, since its processes maintain infinite state. We thus establish a refinement between the abstract protocol and the concrete SCP that uses only finite state, thereby carrying over the result about the correctness of former to the latter. Our results help establish the theoretical foundations of decentralised blockchains like Stellar and gain confidence in their correctness.
Cite as

Álvaro García-Pérez and Maria A. Schett. Deconstructing Stellar Consensus. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{garciaperez_et_al:LIPIcs.OPODIS.2019.5,
  author =	{Garc{\'\i}a-P\'{e}rez, \'{A}lvaro and Schett, Maria A.},
  title =	{{Deconstructing Stellar Consensus}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.5},
  URN =		{urn:nbn:de:0030-drops-117910},
  doi =		{10.4230/LIPIcs.OPODIS.2019.5},
  annote =	{Keywords: Blockchain, Consensus protocol, Stellar, Byzantine quorum systems}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.6
Byzantine-Tolerant Set-Constrained Delivery Broadcast

Authors: Alex Auvolat, Michel Raynal, and François Taïani

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Set-Constrained Delivery Broadcast (SCD-broadcast), recently introduced at ICDCN 2018, is a high-level communication abstraction that captures ordering properties not between individual messages but between sets of messages. More precisely, it allows processes to broadcast messages and deliver sets of messages, under the constraint that if a process delivers a set containing a message m before a set containing a message m', then no other process delivers first a set containing m' and later a set containing m. It has been shown that SCD-broadcast and read/write registers are computationally equivalent, and an algorithm implementing SCD-broadcast is known in the context of asynchronous message passing systems prone to crash failures. This paper introduces a Byzantine-tolerant SCD-broadcast algorithm, which we call BSCD-broadcast. Our proposed algorithm assumes an underlying basic Byzantine-tolerant reliable broadcast abstraction. We first introduce an intermediary communication primitive, Byzantine FIFO broadcast (BFIFO-broadcast), which we then use as a primitive in our final BSCD-broadcast algorithm. Unlike the original SCD-broadcast algorithm that is tolerant to up to t<n/2 crashing processes, and unlike the underlying Byzantine reliable broadcast primitive that is tolerant to up to t<n/3 Byzantine processes, our BSCD-broadcast algorithm is tolerant to up to t<n/4 Byzantine processes. As an illustration of the high abstraction power provided by the BSCD-broadcast primitive, we show that it can be used to implement a Byzantine-tolerant read/write snapshot object in an extremely simple way.
Cite as

Alex Auvolat, Michel Raynal, and François Taïani. Byzantine-Tolerant Set-Constrained Delivery Broadcast. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{auvolat_et_al:LIPIcs.OPODIS.2019.6,
  author =	{Auvolat, Alex and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Byzantine-Tolerant Set-Constrained Delivery Broadcast}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.6},
  URN =		{urn:nbn:de:0030-drops-117922},
  doi =		{10.4230/LIPIcs.OPODIS.2019.6},
  annote =	{Keywords: Algorithm, Asynchronous system, Byzantine process, Communication abstraction, Distributed computing, Distributed software engineering, Fault-tolerance, Message-passing, Modularity, Read/write snapshot object, Reliable broadcast, Set-constrained message delivery}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.7
Asymmetric Distributed Trust

Authors: Christian Cachin and Björn Tackmann

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Quorum systems are a key abstraction in distributed fault-tolerant computing for capturing trust assumptions. They can be found at the core of many algorithms for implementing reliable broadcasts, shared memory, consensus and other problems. This paper introduces asymmetric Byzantine quorum systems that model subjective trust. Every process is free to choose which combinations of other processes it trusts and which ones it considers faulty. Asymmetric quorum systems strictly generalize standard Byzantine quorum systems, which have only one global trust assumption for all processes. This work also presents protocols that implement abstractions of shared memory and broadcast primitives with processes prone to Byzantine faults and asymmetric trust. The model and protocols pave the way for realizing more elaborate algorithms with asymmetric trust.
Cite as

Christian Cachin and Björn Tackmann. Asymmetric Distributed Trust. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cachin_et_al:LIPIcs.OPODIS.2019.7,
  author =	{Cachin, Christian and Tackmann, Bj\"{o}rn},
  title =	{{Asymmetric Distributed Trust}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.7},
  URN =		{urn:nbn:de:0030-drops-117933},
  doi =		{10.4230/LIPIcs.OPODIS.2019.7},
  annote =	{Keywords: Quorums, consensus, distributed trust, blockchains, cryptocurrencies}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.8
Uniform Partition in Population Protocol Model Under Weak Fairness

Authors: Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We focus on a uniform partition problem in a population protocol model. The uniform partition problem aims to divide a population into k groups of the same size, where k is a given positive integer. In the case of k=2 (called uniform bipartition), a previous work clarified space complexity under various assumptions: 1) an initialized base station (BS) or no BS, 2) weak or global fairness, 3) designated or arbitrary initial states of agents, and 4) symmetric or asymmetric protocols, except for the setting that agents execute a protocol from arbitrary initial states under weak fairness in the model with an initialized base station. In this paper, we clarify the space complexity for this remaining setting. In this setting, we prove that P states are necessary and sufficient to realize asymmetric protocols, and that P+1 states are necessary and sufficient to realize symmetric protocols, where P is the known upper bound of the number of agents. From these results and the previous work, we have clarified the solvability of the uniform bipartition for each combination of assumptions. Additionally, we newly consider an assumption on a model of a non-initialized BS and clarify solvability and space complexity in the assumption. Moreover, the results in this paper can be applied to the case that k is an arbitrary integer (called uniform k-partition).
Cite as

Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Uniform Partition in Population Protocol Model Under Weak Fairness. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2019.8,
  author =	{Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko},
  title =	{{Uniform Partition in Population Protocol Model Under Weak Fairness}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.8},
  URN =		{urn:nbn:de:0030-drops-117947},
  doi =		{10.4230/LIPIcs.OPODIS.2019.8},
  annote =	{Keywords: population protocol, uniform k-partition, distributed protocol}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.9
Split and Migrate: Resource-Driven Placement and Discovery of Microservices at the Edge

Authors: Genc Tato, Marin Bertier, Etienne Rivière, and Cédric Tedeschi

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Microservices architectures combine the use of fine-grained and independently-scalable services with lightweight communication protocols, such as REST calls over HTTP. Microservices bring flexibility to the development and deployment of application back-ends in the cloud. Applications such as collaborative editing tools require frequent interactions between the front-end running on users' machines and a back-end formed of multiple microservices. User-perceived latencies depend on their connection to microservices, but also on the interaction patterns between these services and their databases. Placing services at the edge of the network, closer to the users, is necessary to reduce user-perceived latencies. It is however difficult to decide on the placement of complete stateful microservices at one specific core or edge location without trading between a latency reduction for some users and a latency increase for the others. We present how to dynamically deploy microservices on a combination of core and edge resources to systematically reduce user-perceived latencies. Our approach enables the split of stateful microservices, and the placement of the resulting splits on appropriate core and edge sites. Koala, a decentralized and resource-driven service discovery middleware, enables REST calls to reach and use the appropriate split, with only minimal changes to a legacy microservices application. Locality awareness using network coordinates further enables to automatically migrate services split and follow the location of the users. We confirm the effectiveness of our approach with a full prototype and an application to ShareLatex, a microservices-based collaborative editing application.
Cite as

Genc Tato, Marin Bertier, Etienne Rivière, and Cédric Tedeschi. Split and Migrate: Resource-Driven Placement and Discovery of Microservices at the Edge. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{tato_et_al:LIPIcs.OPODIS.2019.9,
  author =	{Tato, Genc and Bertier, Marin and Rivi\`{e}re, Etienne and Tedeschi, C\'{e}dric},
  title =	{{Split and Migrate: Resource-Driven Placement and Discovery of Microservices at the Edge}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.9},
  URN =		{urn:nbn:de:0030-drops-117954},
  doi =		{10.4230/LIPIcs.OPODIS.2019.9},
  annote =	{Keywords: Distributed applications, Microservices, State management, Edge computing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.10
HaTS: Hardware-Assisted Transaction Scheduler

Authors: Zhanhao Chen, Ahmed Hassan, Masoomeh Javidi Kishi, Jacob Nelson, and Roberto Palmieri

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
In this paper we present HaTS, a Hardware-assisted Transaction Scheduler. HaTS improves performance of concurrent applications by classifying the executions of their atomic blocks (or in-memory transactions) into scheduling queues, according to their so called conflict indicators. The goal is to group those transactions that are conflicting while letting non-conflicting transactions proceed in parallel. Two core innovations characterize HaTS. First, HaTS does not assume the availability of precise information associated with incoming transactions in order to proceed with the classification. It relaxes this assumption by exploiting the inherent conflict resolution provided by Hardware Transactional Memory (HTM). Second, HaTS dynamically adjusts the number of the scheduling queues in order to capture the actual application contention level. Performance results using the STAMP benchmark suite show up to 2x improvement over state-of-the-art HTM-based scheduling techniques.
Cite as

Zhanhao Chen, Ahmed Hassan, Masoomeh Javidi Kishi, Jacob Nelson, and Roberto Palmieri. HaTS: Hardware-Assisted Transaction Scheduler. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.OPODIS.2019.10,
  author =	{Chen, Zhanhao and Hassan, Ahmed and Kishi, Masoomeh Javidi and Nelson, Jacob and Palmieri, Roberto},
  title =	{{HaTS: Hardware-Assisted Transaction Scheduler}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.10},
  URN =		{urn:nbn:de:0030-drops-117965},
  doi =		{10.4230/LIPIcs.OPODIS.2019.10},
  annote =	{Keywords: Transactions, Scheduling, Hardware Transactional Memory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.11
Minha: Large-Scale Distributed Systems Testing Made Practical

Authors: Nuno Machado, Francisco Maia, Francisco Neves, Fábio Coelho, and José Pereira

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Testing large-scale distributed system software is still far from practical as the sheer scale needed and the inherent non-determinism make it very expensive to deploy and use realistically large environments, even with cloud computing and state-of-the-art automation. Moreover, observing global states without disturbing the system under test is itself difficult. This is particularly troubling as the gap between distributed algorithms and their implementations can easily introduce subtle bugs that are disclosed only with suitably large scale tests. We address this challenge with Minha, a framework that virtualizes multiple JVM instances in a single JVM, thus simulating a distributed environment where each host runs on a separate machine, accessing dedicated network and CPU resources. The key contributions are the ability to run off-the-shelf concurrent and distributed JVM bytecode programs while at the same time scaling up to thousands of virtual nodes; and enabling global observation within standard software testing frameworks. Our experiments with two distributed systems show the usefulness of Minha in disclosing errors, evaluating global properties, and in scaling tests orders of magnitude with the same hardware resources.
Cite as

Nuno Machado, Francisco Maia, Francisco Neves, Fábio Coelho, and José Pereira. Minha: Large-Scale Distributed Systems Testing Made Practical. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{machado_et_al:LIPIcs.OPODIS.2019.11,
  author =	{Machado, Nuno and Maia, Francisco and Neves, Francisco and Coelho, F\'{a}bio and Pereira, Jos\'{e}},
  title =	{{Minha: Large-Scale Distributed Systems Testing Made Practical}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.11},
  URN =		{urn:nbn:de:0030-drops-117979},
  doi =		{10.4230/LIPIcs.OPODIS.2019.11},
  annote =	{Keywords: Distributed software testing, Large scale distributed systems, Simulation}
}
  • Refine by Author
  • 3 Flocchini, Paola
  • 3 Miller, Avery
  • 3 Santoro, Nicola
  • 2 Felber, Pascal
  • 2 Friedman, Roy
  • Show More...

  • Refine by Classification
  • 17 Theory of computation → Distributed algorithms
  • 10 Theory of computation → Distributed computing models
  • 4 Computing methodologies → Distributed algorithms
  • 3 Computing methodologies → Concurrent algorithms
  • 3 Software and its engineering → Distributed systems organizing principles
  • Show More...

  • Refine by Keyword
  • 3 consensus
  • 2 Blockchain
  • 2 Consensus
  • 2 Massively Parallel Computation
  • 2 concurrency
  • Show More...

  • Refine by Type
  • 38 document
  • 1 volume

  • Refine by Publication Year
  • 38 2020
  • 1 2023

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact