35 Search Results for "Palmieri, Roberto"


Volume

LIPIcs, Volume 253

26th International Conference on Principles of Distributed Systems (OPODIS 2022)

OPODIS 2022, December 13-15, 2022, Brussels, Belgium

Editors: Eshcar Hillel, Roberto Palmieri, and Etienne Rivière

Document
Complete Volume
LIPIcs, Volume 253, OPODIS 2022, Complete Volume

Authors: Eshcar Hillel, Roberto Palmieri, and Etienne Rivière

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
LIPIcs, Volume 253, OPODIS 2022, Complete Volume

Cite as

26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 1-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@Proceedings{hillel_et_al:LIPIcs.OPODIS.2022,
  title =	{{LIPIcs, Volume 253, OPODIS 2022, Complete Volume}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{1--536},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022},
  URN =		{urn:nbn:de:0030-drops-176190},
  doi =		{10.4230/LIPIcs.OPODIS.2022},
  annote =	{Keywords: LIPIcs, Volume 253, OPODIS 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Eshcar Hillel, Roberto Palmieri, and Etienne Rivière

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


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

Cite as

26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hillel_et_al:LIPIcs.OPODIS.2022.0,
  author =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.0},
  URN =		{urn:nbn:de:0030-drops-176203},
  doi =		{10.4230/LIPIcs.OPODIS.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Theory Meets Practice in the Algorand Blockchain (Invited Talk)

Authors: Victor Luchangco

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Robust and effective distributed systems require good theory and good engineering, not separately but in concert: user requirements and system constraints are not merely implementation details but often must inform the design of algorithms for such systems. Blockchains are an excellent example. The heart of a blockchain is its (Byzantine) consensus protocol, and consensus protocols have been extensively studied in the theory community for decades. But traditional consensus protocols are not directly applicable to blockchains, which have, or hope to have, millions of participants. Furthermore, public blockchains, which allow anyone to participate, must have some mechanism to guarantee the security of the protocol, and traditional fault models do not adequately capture the assumptions of such mechanisms. In this talk, I will discuss these and other ways in which theory and practice meet in the context of the Algorand blockchain, and how Algorand is able to achieve high transaction throughput with low latency.

Cite as

Victor Luchangco. Theory Meets Practice in the Algorand Blockchain (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{luchangco:LIPIcs.OPODIS.2022.1,
  author =	{Luchangco, Victor},
  title =	{{Theory Meets Practice in the Algorand Blockchain}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.1},
  URN =		{urn:nbn:de:0030-drops-176219},
  doi =		{10.4230/LIPIcs.OPODIS.2022.1},
  annote =	{Keywords: Theory and practice, Design of distributed systems, Blockchain, Consensus, Algorand}
}
Document
Invited Talk
Recoverable Computing (Invited Talk)

Authors: Panagiota Fatourou

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Non-Volatile Memory (NVM) is an emerging memory technology which aims to address the high computational demands of modern applications and support recovery from crashes. Recovery ensures that after a crash every executed operation is able to recover and return a correct response. This talk will shed light on different aspects of the question "How does concurrent computing change in systems with NVM and what will the impact of persistent memory be on the way we compute?". Specifically, this talk addresses the following four main challenges in NVM computing. - Challenge 1: How to appropriately model and abstract fundamental aspects of NVM computing? The talk will provide an overview of the theoretical framework for NVM computing, including a discussion of correctness conditions, progress guarantees, failure types, etc. - Challenge 2: How to compute in a recoverable way at no significant cost? The talk will summarize state-of-the-art generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of many widely-used concurrent data structures on top of them. The collection of data structures includes fundamental structures, such as stacks and queues, but also more complex structures that implement sets, such as linked-lists and trees. - Challenge 3: How to analyze the cost of recoverable algorithms? The talk will present a way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. This analysis reveals that understanding the actual persistence cost of an algorithm in machines with NVM, is more complicated than previously thought, and requires a thorough evaluation, since the performance impact of different persistence instructions may greatly vary. - Challenge 4: When is Recoverable Consensus Harder Than Consensus? The talk will briefly discuss the ability of different shared object types to solve recoverable consensus using NVM when processes crash and recover, and it will compare the difficulty of solving recoverable consensus to the difficulty of solving the standard consensus problem in a system with halting failures. For each of the above challenges, the talk will present main results, provide some of the details of the best-performing techniques, and discuss open problems and directions for further research. Some of the results that will be discussed in detail have appeared in [Attiya et al., 2022; Delporte-Gallet et al., 2022; Fatourou et al., 2022].

Cite as

Panagiota Fatourou. Recoverable Computing (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fatourou:LIPIcs.OPODIS.2022.2,
  author =	{Fatourou, Panagiota},
  title =	{{Recoverable Computing}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.2},
  URN =		{urn:nbn:de:0030-drops-176221},
  doi =		{10.4230/LIPIcs.OPODIS.2022.2},
  annote =	{Keywords: non-volatile memory, persistence, detectability, durability, recoverable algorithms, recoverable data structures, persistent objects, stacks, queues, heaps, synchronization, universal constructions, software combining, lock-freedom, wait-freedom, persistence cost analysis}
}
Document
Invited Talk
Realistic Self-Stabilization (Invited Talk)

Authors: Sébastien Tixeuil

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of "realistic" distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?

Cite as

Sébastien Tixeuil. Realistic Self-Stabilization (Invited Talk). In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{tixeuil:LIPIcs.OPODIS.2022.3,
  author =	{Tixeuil, S\'{e}bastien},
  title =	{{Realistic Self-Stabilization}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.3},
  URN =		{urn:nbn:de:0030-drops-176232},
  doi =		{10.4230/LIPIcs.OPODIS.2022.3},
  annote =	{Keywords: Self-stabilization, Distributed systems, Probable stabilization, Performance evaluation, Asynchronous message passing, Multi-tolerance}
}
Document
Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers

Authors: Colette Johnen, Adnane Khattabi, and Alessia Milani

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n). Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.

Cite as

Colette Johnen, Adnane Khattabi, and Alessia Milani. Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{johnen_et_al:LIPIcs.OPODIS.2022.4,
  author =	{Johnen, Colette and Khattabi, Adnane and Milani, Alessia},
  title =	{{Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.4},
  URN =		{urn:nbn:de:0030-drops-176240},
  doi =		{10.4230/LIPIcs.OPODIS.2022.4},
  annote =	{Keywords: Distributed computing, distributed algorithms, FIFO queue, shared memory, fault tolerance, concurrent data structures, relaxed specifications, complexity}
}
Document
EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation

Authors: Gali Sheffi, Pedro Ramalhete, and Erez Petrank

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Multi-Version Concurrency Control (MVCC) is a common mechanism for achieving linearizable range queries in database systems and concurrent data-structures. The core idea is to keep previous versions of nodes to serve range queries, while still providing atomic reads and updates. Existing concurrent data-structure implementations, that support linearizable range queries, are either slow, use locks, or rely on blocking reclamation schemes. We present EEMARQ, the first scheme that uses MVCC with lock-free memory reclamation to obtain a fully lock-free data-structure supporting linearizable inserts, deletes, contains, and range queries. Evaluation shows that EEMARQ outperforms existing solutions across most workloads, with lower space overhead and while providing full lock freedom.

Cite as

Gali Sheffi, Pedro Ramalhete, and Erez Petrank. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{sheffi_et_al:LIPIcs.OPODIS.2022.5,
  author =	{Sheffi, Gali and Ramalhete, Pedro and Petrank, Erez},
  title =	{{EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.5},
  URN =		{urn:nbn:de:0030-drops-176253},
  doi =		{10.4230/LIPIcs.OPODIS.2022.5},
  annote =	{Keywords: safe memory reclamation, lock-freedom, snapshot, concurrency, range query}
}
Document
The Step Complexity of Multidimensional Approximate Agreement

Authors: Hagit Attiya and Faith Ellen

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Approximate agreement allows a set of n processes to obtain outputs that are within a specified distance ε > 0 of one another and within the convex hull of the inputs. When the inputs are real numbers, there is a wait-free shared-memory approximate agreement algorithm [Moran, 1995] whose step complexity is in O(n log(S/ε)), where S, the spread of the inputs, is the maximal distance between inputs. There is another wait-free algorithm [Schenk, 1995] that avoids the dependence on n and achieves O(log(M/ε)) step complexity where M, the magnitude of the inputs, is the absolute value of the maximal input. This paper considers whether it is possible to obtain an approximate agreement algorithm whose step complexity depends on neither n nor the magnitude of the inputs, which can be much larger than their spread. On the negative side, we prove that Ω(min{(log M)/(log log M), (√log n)/(log log n)}) is a lower bound on the step complexity of approximate agreement, even when the inputs are real numbers. On the positive side, we prove that a polylogarithmic dependence on n and S/ε can be achieved, by presenting an approximate agreement algorithm with O(log n (log n + log(S/ε))) step complexity. Our algorithm works for multidimensional domains. The step complexity can be further restricted to be in O(min{log n (log n + log (S/ε)), log(M/ε)}) when the inputs are real numbers.

Cite as

Hagit Attiya and Faith Ellen. The Step Complexity of Multidimensional Approximate Agreement. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2022.6,
  author =	{Attiya, Hagit and Ellen, Faith},
  title =	{{The Step Complexity of Multidimensional Approximate Agreement}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.6},
  URN =		{urn:nbn:de:0030-drops-176261},
  doi =		{10.4230/LIPIcs.OPODIS.2022.6},
  annote =	{Keywords: approximate agreement, conflict detection, shared memory, wait-freedom, step complexity}
}
Document
Performance Anomalies in Concurrent Data Structure Microbenchmarks

Authors: Rosina F. Kharal and Trevor Brown

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Recent decades have witnessed a surge in the development of concurrent data structures with an increasing interest in data structures implementing concurrent sets (CSets). Microbenchmarking tools are frequently utilized to evaluate and compare the performance differences across concurrent data structures. The underlying structure and design of the microbenchmarks themselves can play a hidden but influential role in performance results. However, the impact of microbenchmark design has not been well investigated. In this work, we illustrate instances where concurrent data structure performance results reported by a microbenchmark can vary 10-100x depending on the microbenchmark implementation details. We investigate factors leading to performance variance across three popular microbenchmarks and outline cases in which flawed microbenchmark design can lead to an inversion of performance results between two concurrent data structure implementations. We further derive a set of recommendations for best practices in the design and usage of concurrent data structure microbenchmarks and explore advanced features in the Setbench microbenchmark.

Cite as

Rosina F. Kharal and Trevor Brown. Performance Anomalies in Concurrent Data Structure Microbenchmarks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{kharal_et_al:LIPIcs.OPODIS.2022.7,
  author =	{Kharal, Rosina F. and Brown, Trevor},
  title =	{{Performance Anomalies in Concurrent Data Structure Microbenchmarks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.7},
  URN =		{urn:nbn:de:0030-drops-176273},
  doi =		{10.4230/LIPIcs.OPODIS.2022.7},
  annote =	{Keywords: concurrent microbenchmarks, concurrent data structures, concurrent performance evaluation, PRNGs, parallel computing}
}
Document
Robust and Fast Blockchain State Synchronization

Authors: Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
State synchronization, the process by which a new or recovering peer catches up with the state of other operational peers, is critical to the operation of blockchain-based systems. Existing approaches to state synchronization typically involve downloading snapshots of system state. Such approaches introduce an attack vector from malicious peers that can significantly degrade performance. Moreover, the process of creating snapshots leads to performance hiccups. This paper presents a technique for peers to catch up with operational peers without trusting any particular peer and gracefully recover from misbehavior during the process. We have integrated our design into a production blockchain middleware. Our evaluation shows that during operation, the transaction throughput is consistently higher without pauses for snapshot construction. Moreover, the time it takes for a new peer to join the blockchain is halved, while at the same time tolerating Byzantine peers.

Cite as

Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone. Robust and Fast Blockchain State Synchronization. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{fynn_et_al:LIPIcs.OPODIS.2022.8,
  author =	{Fynn, Enrique and Buchman, Ethan and Milosevic, Zarko and Soul\'{e}, Robert and Pedone, Fernando},
  title =	{{Robust and Fast Blockchain State Synchronization}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.8},
  URN =		{urn:nbn:de:0030-drops-176280},
  doi =		{10.4230/LIPIcs.OPODIS.2022.8},
  annote =	{Keywords: state synchronization, replication, blockchain}
}
Document
A Privacy-Preserving and Transparent Certification System for Digital Credentials

Authors: Rodrigo Q. Saramago, Hein Meling, and Leander N. Jehl

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
A certification system is responsible for issuing digital credentials, which attest claims about a subject, e.g., an academic diploma. Such credentials are valuable for individuals and society, and widespread adoption requires a trusted certification system. Trust can be gained by being transparent when issuing and verifying digital credentials. However, there is a fundamental tradeoff between privacy and transparency. For instance, admitting a student to an academic program must preserve the student’s privacy, i.e., the student’s grades must not be revealed to unauthorized parties. At the same time, other applicants may demand transparency to ensure fairness in the admission process. Thus, building a certification system with the right balance between privacy and transparency is challenging. This paper proposes a novel design for a certification system that provides sufficient transparency and preserves privacy through selective disclosure of claims such that authorized parties can verify them. Moreover, unauthorized parties can also verify the correctness of the certification process without compromising privacy. We achieve this using an incremental Merkle tree of cryptographic commitments to users' credentials. The commitments are added to the tree based on verifying zero-knowledge issuance proofs. Users store credentials off-chain and can prove the ownership and authenticity of credentials without revealing their commitments. Further, our approach enables users to prove statements about the credential’s claims in zero-knowledge. Our design offers a cost-efficient solution, reducing the amount of linkable on-chain data by up to 79% per credential compared to prior work, while maintaining transparency.

Cite as

Rodrigo Q. Saramago, Hein Meling, and Leander N. Jehl. A Privacy-Preserving and Transparent Certification System for Digital Credentials. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 9:1-9:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{saramago_et_al:LIPIcs.OPODIS.2022.9,
  author =	{Saramago, Rodrigo Q. and Meling, Hein and Jehl, Leander N.},
  title =	{{A Privacy-Preserving and Transparent Certification System for Digital Credentials}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{9:1--9:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.9},
  URN =		{urn:nbn:de:0030-drops-176294},
  doi =		{10.4230/LIPIcs.OPODIS.2022.9},
  annote =	{Keywords: verifiable credentials, privacy-preserving, zero-knowledge, blockchain}
}
Document
When Is Spring Coming? A Security Analysis of Avalanche Consensus

Authors: Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Avalanche is a blockchain consensus protocol with exceptionally low latency and high throughput. This has swiftly established the corresponding token as a top-tier cryptocurrency. Avalanche achieves such remarkable metrics by substituting proof of work with a random sampling mechanism. The protocol also differs from Bitcoin, Ethereum, and many others by forming a directed acyclic graph (DAG) instead of a chain. It does not totally order all transactions, establishes a partial order among them, and accepts transactions in the DAG that satisfy specific properties. Such parallelism is widely regarded as a technique that increases the efficiency of consensus. Despite its success, Avalanche consensus lacks a complete abstract specification and a matching formal analysis. To address this drawback, this work provides first a detailed formulation of Avalanche through pseudocode. This includes features that are omitted from the original whitepaper or are only vaguely explained in the documentation. Second, the paper gives an analysis of the formal properties fulfilled by Avalanche in the sense of a generic broadcast protocol that only orders related transactions. Last but not least, the analysis reveals a vulnerability that affects the liveness of the protocol. A possible solution that addresses the problem is also proposed.

Cite as

Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi. When Is Spring Coming? A Security Analysis of Avalanche Consensus. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2022.10,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Tedeschi, Enrico},
  title =	{{When Is Spring Coming? A Security Analysis of Avalanche Consensus}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.10},
  URN =		{urn:nbn:de:0030-drops-176307},
  doi =		{10.4230/LIPIcs.OPODIS.2022.10},
  annote =	{Keywords: Avalanche, security analysis, generic broadcast}
}
Document
Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs

Authors: Taichi Inoue, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
We investigated the computational power of a single mobile agent in an n-node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and O(1)-bit storage is as powerful as that with O(n)-bit agent memory and O(1)-bit storage. Thus, we focus on the difference between one-bit memory and oblivious (i.e., zero-bit memory) agents. Although their computational powers are not equivalent, all the known results exhibiting such a difference rely on the fact that oblivious agents cannot transfer any information from one side to the other across the bridge edge. Hence, our main question is as follows: Are the computational powers of one-bit memory and oblivious agents equivalent in 2-edge-connected graphs or not? The main contribution of this study is to answer this question under the relaxed assumption that each node has O(logΔ)-bit storage (where Δ is the maximum degree of the graph). We present an algorithm for simulating any algorithm for a single one-bit memory agent using an oblivious agent with O(n²)-time overhead per round. Our results imply that the topological structure of graphs differentiating the computational powers of oblivious and non-oblivious agents is completely characterized by the existence of bridge edges.

Cite as

Taichi Inoue, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{inoue_et_al:LIPIcs.OPODIS.2022.11,
  author =	{Inoue, Taichi and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu},
  title =	{{Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.11},
  URN =		{urn:nbn:de:0030-drops-176311},
  doi =		{10.4230/LIPIcs.OPODIS.2022.11},
  annote =	{Keywords: mobile agent, depth-first search, space complexity}
}
Document
Line Search for an Oblivious Moving Target

Authors: Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)


Abstract
Consider search on an infinite line involving an autonomous robot starting at the origin of the line and an oblivious moving target at initial distance d ≥ 1 from it. The robot can change direction and move anywhere on the line with constant maximum speed 1 while the target is also moving on the line with constant speed v > 0 but is unable to change its speed or direction. The goal is for the robot to catch up to the target in as little time as possible. The classic case where v = 0 and the target’s initial distance d is unknown to the robot is the well-studied "cow-path problem". Alpert and Gal [Steve Alpern and Shmuel Gal, 2003] gave an optimal algorithm for the case where a target with unknown initial distance d is moving away from the robot with a known speed v < 1. In this paper we design and analyze search algorithms for the remaining possible knowledge situations, namely, when d and v are known, when v is known but d is unknown, when d is known but v is unknown, and when both v and d are unknown. Furthermore, for each of these knowledge models we consider separately the case where the target is moving away from the origin and the case where it is moving toward the origin. We design algorithms and analyze competitive ratios for all eight cases above. The resulting competitive ratios are shown to be optimal when the target is moving towards the origin as well as when v is known and the target is moving away from the origin.

Cite as

Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce. Line Search for an Oblivious Moving Target. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{coleman_et_al:LIPIcs.OPODIS.2022.12,
  author =	{Coleman, Jared and Kranakis, Evangelos and Krizanc, Danny and Morales-Ponce, Oscar},
  title =	{{Line Search for an Oblivious Moving Target}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.12},
  URN =		{urn:nbn:de:0030-drops-176325},
  doi =		{10.4230/LIPIcs.OPODIS.2022.12},
  annote =	{Keywords: Infinite Line, Knowledge, Oblivious, Robot, Search, Search-Time, Speed, Target}
}
  • Refine by Author
  • 6 Palmieri, Roberto
  • 3 Cachin, Christian
  • 3 Hassan, Ahmed
  • 2 Abraham, Ittai
  • 2 Hillel, Eshcar
  • Show More...

  • Refine by Classification
  • 17 Theory of computation → Distributed algorithms
  • 6 Theory of computation → Distributed computing models
  • 5 Software and its engineering → Distributed systems organizing principles
  • 4 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 4 Computing methodologies → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 4 blockchain
  • 3 consensus
  • 2 Consensus
  • 2 Self-stabilization
  • 2 Transactions
  • Show More...

  • Refine by Type
  • 34 document
  • 1 volume

  • Refine by Publication Year
  • 31 2023
  • 1 2018
  • 1 2019
  • 1 2020
  • 1 2022

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