Search Results

Documents authored by Tonkikh, Andrei

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
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.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
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}
}
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