Search Results

Documents authored by Kuznetsov, Petr

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.31
A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies

Authors: João Paulo Bezerra and Petr Kuznetsov

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
The last decade has seen a variety of Asset-Transfer systems designed for decentralized environments. The major problem these systems address is double-spending, and solving it inherently imposes strong trust assumptions on the system participants. In this paper, we take a non-orthodox approach to the double-spending problem that might suit better realistic environments in which these systems are to be deployed. We consider the decentralized trust setting, where each user may independently choose who to trust by forming their local quorums. In this setting, we define k-Spending Asset Transfer, a relaxed version of asset transfer which bounds the number of times a system participant may spend an asset it received. We establish a precise relationship between the decentralized trust assumptions and k, the optimal spending number of the system.
Cite as

João Paulo Bezerra and Petr Kuznetsov. A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.OPODIS.2023.31,
  author =	{Bezerra, Jo\~{a}o Paulo and Kuznetsov, Petr},
  title =	{{A Tight Bound on Multiple Spending in Decentralized Cryptocurrencies}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.31},
  URN =		{urn:nbn:de:0030-drops-195210},
  doi =		{10.4230/LIPIcs.OPODIS.2023.31},
  annote =	{Keywords: Quorum systems, decentralized trust, consistency measure, asset transfer, accountability}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.24
Distributed Randomness from Approximate Agreement

Authors: Luciano Freitas, Petr Kuznetsov, and Andrei Tonkikh

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Randomisation is a critical tool in designing distributed systems. The common coin primitive, enabling the system members to agree on an unpredictable random number, has proven to be particularly useful. We observe, however, that it is impossible to implement a truly random common coin protocol in a fault-prone asynchronous system. To circumvent this impossibility, we introduce two relaxations of the perfect common coin: (1) approximate common coin generating random numbers that are close to each other; and (2) Monte Carlo common coin generating a common random number with an arbitrarily small, but non-zero, probability of failure. Building atop the approximate agreement primitive, we obtain efficient asynchronous implementations of the two abstractions, tolerating up to one third of Byzantine processes. Our protocols do not assume trusted setup or public key infrastructure and converge to the perfect coin exponentially fast in the protocol running time. By plugging one of our protocols for Monte Carlo common coin in a well-known consensus algorithm, we manage to get a binary Byzantine agreement protocol with O(n³ log n) communication complexity, resilient against an adaptive adversary, and tolerating the optimal number f < n/3 of failures without trusted setup or PKI. To the best of our knowledge, the best communication complexity for binary Byzantine agreement achieved so far in this setting is O(n⁴). We also show how the approximate common coin, combined with a variant of Gray code, can be used to solve an interesting problem of Intersecting Random Subsets, which we introduce in this paper.
Cite as

Luciano Freitas, Petr Kuznetsov, and Andrei Tonkikh. Distributed Randomness from Approximate Agreement. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{freitas_et_al:LIPIcs.DISC.2022.24,
  author =	{Freitas, Luciano and Kuznetsov, Petr and Tonkikh, Andrei},
  title =	{{Distributed Randomness from Approximate Agreement}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{24:1--24:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.24},
  URN =		{urn:nbn:de:0030-drops-172157},
  doi =		{10.4230/LIPIcs.DISC.2022.24},
  annote =	{Keywords: Asynchronous, approximate agreement, weak common coin, consensus, Byzantine agreement}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.OPODIS.2021.2
Accountable Distributed Computing (Invited Talk)

Authors: Petr Kuznetsov

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
There are two major ways to deal with failures in distributed computing: fault-tolerance and accountability. Fault-tolerance intends to anticipate failures by investing into replication and synchronization, so that the system’s correctness is not affected by faulty components. In contrast, accountability enables detecting failures a posteriori and raising undeniable evidences against faulty components. In this talk, we discuss how accountability can be achieved, both in generic and application-specific ways. We begin with an overview of fault detection mechanisms used in benign, crash-prone system, with a focus on the weakest failure detector question. We then consider the fault detection problem in systems with general, Byzantine failures and explore which classes of misbehavior can be detected and which - cannot. We then study the mechanism of application-specific accountability that, intuitively, only accounts for instances of misbehavior that affect particular correctness criteria. Finally, we discuss how fault detection can be combined with reconfiguration, opening an avenue of "self-healing" systems that seamlessly replace faulty system components with correct ones.
Cite as

Petr Kuznetsov. Accountable Distributed Computing (Invited Talk). In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kuznetsov:LIPIcs.OPODIS.2021.2,
  author =	{Kuznetsov, Petr},
  title =	{{Accountable Distributed Computing}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.2},
  URN =		{urn:nbn:de:0030-drops-157775},
  doi =		{10.4230/LIPIcs.OPODIS.2021.2},
  annote =	{Keywords: Fault-tolerance, fault detection, accountability, application-specific}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.23
RandSolomon: Optimally Resilient Random Number Generator with Deterministic Termination

Authors: Luciano Freitas de Souza, Andrei Tonkikh, Sara Tucci-Piergiovanni, Renaud Sirdey, Oana Stan, Nicolas Quero, and Petr Kuznetsov

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Multi-party random number generation is a key building-block in many practical protocols. While straightforward to solve when all parties are trusted to behave correctly, the problem becomes much more difficult in the presence of faults. This paper presents RandSolomon, a partially synchronous protocol that allows a system of N processes to produce an unpredictable common random number shared by correct participants. The protocol is optimally resilient, as it allows up to f = ⌊(N-1)/3⌋ of the processes to behave arbitrarily, ensures deterministic termination and, contrary to prior solutions, does not, at any point, expect faulty processes to be responsive.
Cite as

Luciano Freitas de Souza, Andrei Tonkikh, Sara Tucci-Piergiovanni, Renaud Sirdey, Oana Stan, Nicolas Quero, and Petr Kuznetsov. RandSolomon: Optimally Resilient Random Number Generator with Deterministic Termination. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{freitasdesouza_et_al:LIPIcs.OPODIS.2021.23,
  author =	{Freitas de Souza, Luciano and Tonkikh, Andrei and Tucci-Piergiovanni, Sara and Sirdey, Renaud and Stan, Oana and Quero, Nicolas and Kuznetsov, Petr},
  title =	{{RandSolomon: Optimally Resilient Random Number Generator with Deterministic Termination}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.23},
  URN =		{urn:nbn:de:0030-drops-157986},
  doi =		{10.4230/LIPIcs.OPODIS.2021.23},
  annote =	{Keywords: Byzantine Fault Tolerance, Partially Synchronous, Deterministic Termination, Randomness Beacon, Multi Party Computation, BFT-RNG}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.25
Accountability and Reconfiguration: Self-Healing Lattice Agreement

Authors: Luciano Freitas de Souza, Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
An accountable distributed system provides means to detect deviations of system components from their expected behavior. It is natural to complement fault detection with a reconfiguration mechanism, so that the system could heal itself, by replacing malfunctioning parts with new ones. In this paper, we describe a framework that can be used to implement a large class of accountable and reconfigurable replicated services. We build atop the fundamental lattice agreement abstraction lying at the core of storage systems and cryptocurrencies. Our asynchronous implementation of accountable lattice agreement ensures that every violation of consistency is followed by an undeniable evidence of misbehavior of a faulty replica. The system can then be seamlessly reconfigured by evicting faulty replicas, adding new ones and merging inconsistent states. We believe that this paper opens a direction towards asynchronous "self-healing" systems that combine accountability and reconfiguration.
Cite as

Luciano Freitas de Souza, Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Accountability and Reconfiguration: Self-Healing Lattice Agreement. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{freitasdesouza_et_al:LIPIcs.OPODIS.2021.25,
  author =	{Freitas de Souza, Luciano and Kuznetsov, Petr and Rieutord, Thibault and Tucci-Piergiovanni, Sara},
  title =	{{Accountability and Reconfiguration: Self-Healing Lattice Agreement}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.25},
  URN =		{urn:nbn:de:0030-drops-158007},
  doi =		{10.4230/LIPIcs.OPODIS.2021.25},
  annote =	{Keywords: Reconfiguration, accountability, asynchronous, lattice agreement}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.28
Permissionless and Asynchronous Asset Transfer

Authors: Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, and Andrei Tonkikh

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Most modern asset transfer systems use consensus to maintain a totally ordered chain of transactions. It was recently shown that consensus is not always necessary for implementing asset transfer. More efficient, asynchronous solutions can be built using reliable broadcast instead of consensus. This approach has been originally used in the closed (permissioned) setting. In this paper, we extend it to the open (permissionless) environment. We present {Pastro}, a permissionless and asynchronous asset-transfer implementation, in which quorum systems, traditionally used in reliable broadcast, are replaced with a weighted Proof-of-Stake mechanism. {Pastro} tolerates a dynamic adversary that is able to adaptively corrupt participants based on the assets owned by them.
Cite as

Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, and Andrei Tonkikh. Permissionless and Asynchronous Asset Transfer. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2021.28,
  author =	{Kuznetsov, Petr and Pignolet, Yvonne-Anne and Ponomarev, Pavel and Tonkikh, Andrei},
  title =	{{Permissionless and Asynchronous Asset Transfer}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.28},
  URN =		{urn:nbn:de:0030-drops-148307},
  doi =		{10.4230/LIPIcs.DISC.2021.28},
  annote =	{Keywords: Asset transfer, permissionless, asynchronous, dynamic adversary}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.54
Brief Announcement: Accountability and Reconfiguration — Self-Healing Lattice Agreement

Authors: Luciano Freitas de Souza, Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
An accountable distributed system provides means to detect deviations of system components from their expected behavior. It is natural to complement fault detection with a reconfiguration mechanism, so that the system could heal itself, by replacing malfunctioning parts with new ones. In this paper, we describe a framework that can be used to implement a large class of accountable and reconfigurable replicated services. We build atop the fundamental lattice agreement abstraction lying at the core of storage systems and cryptocurrencies. Our asynchronous implementation of accountable lattice agreement ensures that every violation of consistency is followed by an undeniable evidence of misbehavior of a faulty replica. The system can then be seamlessly reconfigured by evicting faulty replicas, adding new ones and merging inconsistent states. We believe that this paper opens a direction towards asynchronous "self-healing" systems that combine accountability and reconfiguration.
Cite as

Luciano Freitas de Souza, Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Brief Announcement: Accountability and Reconfiguration — Self-Healing Lattice Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 54:1-54:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{desouza_et_al:LIPIcs.DISC.2021.54,
  author =	{de Souza, Luciano Freitas and Kuznetsov, Petr and Rieutord, Thibault and Tucci-Piergiovanni, Sara},
  title =	{{Brief Announcement: Accountability and Reconfiguration — Self-Healing Lattice Agreement}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{54:1--54:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.54},
  URN =		{urn:nbn:de:0030-drops-148565},
  doi =		{10.4230/LIPIcs.DISC.2021.54},
  annote =	{Keywords: Reconfiguration, accountability, asynchronous, lattice agreement}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.23
Dynamic Byzantine Reliable Broadcast

Authors: Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh

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

Abstract
Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a completely asynchronous environment, unlike stronger primitives like consensus and total-order broadcast, and yet (ii) reliable broadcast is powerful enough to implement important applications like payment systems. The problem we tackle in this paper is that of dynamic reliable broadcast, i.e., enabling processes to join or leave the system. This property is desirable for long-lived applications (aiming to be highly available), yet has been precluded in previous asynchronous reliable broadcast protocols. We study this property in a general adversarial (i.e., Byzantine) environment. We introduce the first specification of a dynamic Byzantine reliable broadcast (dbrb) primitive that is amenable to an asynchronous implementation. We then present an algorithm implementing this specification in an asynchronous network. Our dbrb algorithm ensures that if any correct process in the system broadcasts a message, then every correct process delivers that message unless it leaves the system. Moreover, if a correct process delivers a message, then every correct process that has not expressed its will to leave the system delivers that message. We assume that more than 2/3 of processes in the system are correct at all times, which is tight in our context. We also show that if only one process in the system can fail - and it can fail only by crashing - then it is impossible to implement a stronger primitive, ensuring that if any correct process in the system broadcasts or delivers a message, then every correct process in the system delivers that message - including those that leave.
Cite as

Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh. Dynamic Byzantine Reliable Broadcast. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.OPODIS.2020.23,
  author =	{Guerraoui, Rachid and Komatovic, Jovan and Kuznetsov, Petr and Pignolet, Yvonne-Anne and Seredinschi, Dragos-Adrian and Tonkikh, Andrei},
  title =	{{Dynamic Byzantine Reliable Broadcast}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{23:1--23: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.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.23},
  URN =		{urn:nbn:de:0030-drops-135087},
  doi =		{10.4230/LIPIcs.OPODIS.2020.23},
  annote =	{Keywords: Byzantine reliable broadcast, deterministic distributed algorithms, dynamic distributed systems}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.27
Asynchronous Reconfiguration with Byzantine Failures

Authors: Petr Kuznetsov and Andrei Tonkikh

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Replicated services are inherently vulnerable to failures and security breaches. In a long-running system, it is, therefore, indispensable to maintain a reconfiguration mechanism that would replace faulty replicas with correct ones. An important challenge is to enable reconfiguration without affecting the availability and consistency of the replicated data: the clients should be able to get correct service even when the set of service replicas is being updated. In this paper, we address the problem of reconfiguration in the presence of Byzantine failures: faulty replicas or clients may arbitrarily deviate from their expected behavior. We describe a generic technique for building asynchronous and Byzantine fault-tolerant reconfigurable objects: clients can manipulate the object data and issue reconfiguration calls without reaching consensus on the current configuration. With the help of forward-secure digital signatures, our solution makes sure that superseded and possibly compromised configurations are harmless, that slow clients cannot be fooled into reading stale data, and that Byzantine clients cannot cause a denial of service by flooding the system with reconfiguration requests. Our approach is modular and based on dynamic lattice agreement abstraction, and we discuss how to extend it to enable Byzantine fault-tolerant implementations of a large class of reconfigurable replicated services.
Cite as

Petr Kuznetsov and Andrei Tonkikh. Asynchronous Reconfiguration with Byzantine Failures. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2020.27,
  author =	{Kuznetsov, Petr and Tonkikh, Andrei},
  title =	{{Asynchronous Reconfiguration with Byzantine Failures}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.27},
  URN =		{urn:nbn:de:0030-drops-131054},
  doi =		{10.4230/LIPIcs.DISC.2020.27},
  annote =	{Keywords: Reconfiguration, Asynchronous Models, Byzantine Faults}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.54
Brief Announcement: On Decidability of 2-Process Affine Models

Authors: Petr Kuznetsov and Thibault Rieutord

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Affine models of computation, defined as subsets of iterated immediate-snapshot runs, capture a wide variety of shared-memory systems: wait-freedom, t-resilience, k-concurrency, and fair shared-memory adversaries. The question of whether a given task is solvable in a given affine model is, in general, undecidable. In this paper, we focus on affine models defined for a system of two processes. We show that task computability of 2-process affine models is decidable and presents a complete hierarchy of five equivalence classes of 2-process affine models.
Cite as

Petr Kuznetsov and Thibault Rieutord. Brief Announcement: On Decidability of 2-Process Affine Models. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 54:1-54:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2020.54,
  author =	{Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Brief Announcement: On Decidability of 2-Process Affine Models}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{54:1--54:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.54},
  URN =		{urn:nbn:de:0030-drops-131328},
  doi =		{10.4230/LIPIcs.DISC.2020.54},
  annote =	{Keywords: Affine tasks, Decidability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.31
Reconfigurable Lattice Agreement and Applications

Authors: Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni

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

Abstract
Reconfiguration is one of the central mechanisms in distributed systems. Due to failures and connectivity disruptions, the very set of service replicas (or servers) and their roles in the computation may have to be reconfigured over time. To provide the desired level of consistency and availability to applications running on top of these servers, the clients of the service should be able to reach some form of agreement on the system configuration. We observe that this agreement is naturally captured via a lattice partial order on the system states. We propose an asynchronous implementation of reconfigurable lattice agreement that implies elegant reconfigurable versions of a large class of lattice abstract data types, such as max-registers and conflict detectors, as well as popular distributed programming abstractions, such as atomic snapshot and commit-adopt.
Cite as

Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Reconfigurable Lattice Agreement and Applications. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.OPODIS.2019.31,
  author =	{Kuznetsov, Petr and Rieutord, Thibault and Tucci-Piergiovanni, Sara},
  title =	{{Reconfigurable Lattice Agreement and Applications}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{31:1--31: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.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.31},
  URN =		{urn:nbn:de:0030-drops-118177},
  doi =		{10.4230/LIPIcs.OPODIS.2019.31},
  annote =	{Keywords: Reconfigurable services, lattice agreement}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.22
Scalable Byzantine Reliable Broadcast

Authors: Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as they typically build on quorum systems with strong intersection guarantees, which results in linear per-process communication and computation complexity. We generalize the Byzantine reliable broadcast abstraction to the probabilistic setting, allowing each of its properties to be violated with a fixed, arbitrarily small probability. We leverage these relaxed guarantees in a protocol where we replace quorums with stochastic samples. Compared to quorums, samples are significantly smaller in size, leading to a more scalable design. We obtain the first Byzantine reliable broadcast protocol with logarithmic per-process communication and computation complexity. We conduct a complete and thorough analysis of our protocol, deriving bounds on the probability of each of its properties being compromised. During our analysis, we introduce a novel general technique that we call adversary decorators. Adversary decorators allow us to make claims about the optimal strategy of the Byzantine adversary without imposing any additional assumptions. We also introduce Threshold Contagion, a model of message propagation through a system with Byzantine processes. To the best of our knowledge, this is the first formal analysis of a probabilistic broadcast protocol in the Byzantine fault model. We show numerically that practically negligible failure probabilities can be achieved with realistic security parameters.
Cite as

Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. Scalable Byzantine Reliable Broadcast. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.DISC.2019.22,
  author =	{Guerraoui, Rachid and Kuznetsov, Petr and Monti, Matteo and Pavlovic, Matej and Seredinschi, Dragos-Adrian},
  title =	{{Scalable Byzantine Reliable Broadcast}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.22},
  URN =		{urn:nbn:de:0030-drops-113293},
  doi =		{10.4230/LIPIcs.DISC.2019.22},
  annote =	{Keywords: Byzantine reliable broadcast, probabilistic distributed algorithms, scalable distributed systems, stochastic processes}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.11
Parallel Combining: Benefits of Explicit Synchronization

Authors: Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
A parallel batched data structure is designed to process synchronized batches of operations on the data structure using a parallel program. In this paper, we propose parallel combining, a technique that implements a concurrent data structure from a parallel batched one. The idea is that we explicitly synchronize concurrent operations into batches: one of the processes becomes a combiner which collects concurrent requests and initiates a parallel batched algorithm involving the owners (clients) of the collected requests. Intuitively, the cost of synchronizing the concurrent calls can be compensated by running the parallel batched algorithm. We validate the intuition via two applications. First, we use parallel combining to design a concurrent data structure optimized for read-dominated workloads, taking a dynamic graph data structure as an example. Second, we use a novel parallel batched priority queue to build a concurrent one. In both cases, we obtain performance gains with respect to the state-of-the-art algorithms.
Cite as

Vitaly Aksenov, Petr Kuznetsov, and Anatoly Shalyto. Parallel Combining: Benefits of Explicit Synchronization. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aksenov_et_al:LIPIcs.OPODIS.2018.11,
  author =	{Aksenov, Vitaly and Kuznetsov, Petr and Shalyto, Anatoly},
  title =	{{Parallel Combining: Benefits of Explicit Synchronization}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.11},
  URN =		{urn:nbn:de:0030-drops-100713},
  doi =		{10.4230/LIPIcs.OPODIS.2018.11},
  annote =	{Keywords: concurrent data structure, parallel batched data structure, combining}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.23
Task Computability in Unreliable Anonymous Networks

Authors: Petr Kuznetsov and Nayuta Yanagisawa

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
We consider the anonymous broadcast model: a set of n anonymous processes communicate via send-to-all primitives. We assume that underlying communication channels are asynchronous but reliable, and that the processes are subject to crash failures. We show first that in this model, even a single faulty process precludes implementations of atomic objects with non-commuting operations, even as simple as read-write registers or add-only sets. We, however, show that a sequentially consistent read-write memory and add-only sets can be implemented t-resiliently for t<n/2, i.e., provided that a majority of the processes do not fail. We use this implementation to establish an equivalence between the t-resilient read-write anonymous shared-memory model and the t-resilient anonymous broadcast model in terms of colorless task solvability. As a result, we obtain the first task computability characterization for unreliable anonymous message-passing systems.
Cite as

Petr Kuznetsov and Nayuta Yanagisawa. Task Computability in Unreliable Anonymous Networks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.OPODIS.2018.23,
  author =	{Kuznetsov, Petr and Yanagisawa, Nayuta},
  title =	{{Task Computability in Unreliable Anonymous Networks}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.23},
  URN =		{urn:nbn:de:0030-drops-100830},
  doi =		{10.4230/LIPIcs.OPODIS.2018.23},
  annote =	{Keywords: Distributed tasks, anonymous broadcast, fault-tolerance}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.9
Progress-Space Tradeoffs in Single-Writer Memory Implementations

Authors: Damien Imbs, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Many algorithms designed for shared-memory distributed systems assume the single-writer multi- reader (SWMR) setting where each process is provided with a unique register that can only be written by the process and read by all. In a system where computation is performed by a bounded number n of processes coming from a large (possibly unbounded) set of potential participants, the assumption of an SWMR memory is no longer reasonable. If only a bounded number of multi- writer multi-reader (MWMR) registers are provided, we cannot rely on an a priori assignment of processes to registers. In this setting, implementing an SWMR memory, or equivalently, ensuring stable writes (i.e., every written value persists in the memory), is desirable. In this paper, we propose an SWMR implementation that adapts the number of MWMR registers used to the desired progress condition. For any given k from 1 to n, we present an algorithm that uses n + k − 1 registers to implement a k-lock-free SWMR memory. In the special case of 2-lock-freedom, we also give a matching lower bound of n + 1 registers, which supports our conjecture that the algorithm is space-optimal. Our lower bound holds for the strictly weaker progress condition of 2-obstruction-freedom, which suggests that the space complexity for k-obstruction-free and k-lock-free SWMR implementations might coincide.
Cite as

Damien Imbs, Petr Kuznetsov, and Thibault Rieutord. Progress-Space Tradeoffs in Single-Writer Memory Implementations. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{imbs_et_al:LIPIcs.OPODIS.2017.9,
  author =	{Imbs, Damien and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Progress-Space Tradeoffs in Single-Writer Memory Implementations}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.9},
  URN =		{urn:nbn:de:0030-drops-86290},
  doi =		{10.4230/LIPIcs.OPODIS.2017.9},
  annote =	{Keywords: Single-writer memory implementation, comparison-based algorithms, space complexity, progress conditions}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.56
Brief Announcement: Compact Topology of Shared-Memory Adversaries

Authors: Petr Kuznetsov, Thibault Rieutord, and Yuan He

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.
Cite as

Petr Kuznetsov, Thibault Rieutord, and Yuan He. Brief Announcement: Compact Topology of Shared-Memory Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 56:1-56:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.DISC.2017.56,
  author =	{Kuznetsov, Petr and Rieutord, Thibault and He, Yuan},
  title =	{{Brief Announcement: Compact Topology of Shared-Memory Adversaries}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{56:1--56:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.56},
  URN =		{urn:nbn:de:0030-drops-80108},
  doi =		{10.4230/LIPIcs.DISC.2017.56},
  annote =	{Keywords: Adversarial models, Affine tasks, Topological characterization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.6
Read-Write Memory and k-Set Consensus as an Affine Task

Authors: Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.
Cite as

Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-Write Memory and k-Set Consensus as an Affine Task. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gafni_et_al:LIPIcs.OPODIS.2016.6,
  author =	{Gafni, Eli and He, Yuan and Kuznetsov, Petr and Rieutord, Thibault},
  title =	{{Read-Write Memory and k-Set Consensus as an Affine Task}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.6},
  URN =		{urn:nbn:de:0030-drops-70759},
  doi =		{10.4230/LIPIcs.OPODIS.2016.6},
  annote =	{Keywords: iterated affine tasks, k-set consensus, k-concurrency, simplicial complexes, immediate snapshot}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.7
Set-Consensus Collections are Decidable

Authors: Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its set-consensus power.
Cite as

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov. Set-Consensus Collections are Decidable. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{delportegallet_et_al:LIPIcs.OPODIS.2016.7,
  author =	{Delporte-Gallet, Carole and Fauconnier, Hugues and Gafni, Eli and Kuznetsov, Petr},
  title =	{{Set-Consensus Collections are Decidable}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.7},
  URN =		{urn:nbn:de:0030-drops-70761},
  doi =		{10.4230/LIPIcs.OPODIS.2016.7},
  annote =	{Keywords: Decidability, distributed tasks, set consensus, Knapsack problem}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.12
On the Uncontended Complexity of Anonymous Consensus

Authors: Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
Cite as

Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{capdevielle_et_al:LIPIcs.OPODIS.2015.12,
  author =	{Capdevielle, Claire and Johnen, Colette and Kuznetsov, Petr and Milani, Alessia},
  title =	{{On the Uncontended Complexity of Anonymous Consensus}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.12},
  URN =		{urn:nbn:de:0030-drops-66034},
  doi =		{10.4230/LIPIcs.OPODIS.2015.12},
  annote =	{Keywords: space and time complexity, lower bounds, consensus, interval contention, solo-fast}
}
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