Petr Kuznetsov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Petr Kuznetsov has a total of 61 co-authors. Here are the top co-authors by number of shared publications:
- Rachid Guerraoui
EPFL
6 shared publications - Vitaly Aksenov
City St George's, University of London, London, United Kingdom
6 shared publications - Andrei Tonkikh
LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France
4 shared publications - Guillermo Toyos-Marfurt
Institut Polytechnique de Paris
3 shared publications - Pavel Ponomarev
Georgia Institute of Technology, Atlanta, GA, USA
3 shared publications - Yvonne-Anne Pignolet
Dfinity, Zurich, Switzerland
3 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 456-466
Conflict-Freedom as a Progress Condition
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 456-466
Open AccessConflict-Freedom as a Progress Condition
- Open Access
- 5 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-5
DScale: a Simulation Framework for Large-Scale Distributed Systems
- 5 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1-5
Open AccessDScale: a Simulation Framework for Large-Scale Distributed Systems
- 18 November 2025
- Published by Springer Nature
- p. 458-474
Space-Time Trade-Off in Bounded Iterated Memory
- 18 November 2025
- Published by Springer Nature
- p. 458-474
Space-Time Trade-Off in Bounded Iterated Memory
- Open Access
Space-Time Trade-off in Bounded Iterated Memory
The celebrated asynchronous computability theorem (ACT) characterizes tasks solvable in the read-write shared-memory model using the unbounded full-information protocol, where in every round of computation, each process shares its complete knowledge of the system with the other processes. Therefore, ACT assumes shared-memory variables of unbounded capacity. It has been recently shown that boundedvariables can achieve the same computational power at the expense of extra rounds. However, the exact relationship between the bit capacity of the shared memory and the number of rounds required in order to implement one round of the full-information protocol remained unknown. In this paper, we focus on the asymptotic round complexity of bounded iterated shared-memory algorithms that simulate, up to isomorphism, the unbounded full-information protocol. We relate the round complexity to the number of processes $n$, the number of iterations of the full information protocol $r$, and the bit size per shared-memory entry $b$. By analyzing the corresponding protocol complex, a combinatorial structure representing reachable states, we derive necessary conditions and present a bounded full-information algorithm tailored to the bits available $b$ per shared memory entry. We show that for $n>2$, the round complexity required to implement the full-information protocol satisfies $Ω((n!)^{r-1} \cdot 2^{n-b})$. Our results apply to a range of iterated shared-memory models, from regular read-write registers to atomic and immediate snapshots. Moreover, our bounded full-information algorithm is asymptotically optimal for the iterated collect model and within a linear factor $n$ of optimal for the snapshot-based models.Open AccessSpace-Time Trade-off in Bounded Iterated Memory
The celebrated asynchronous computability theorem (ACT) characterizes tasks solvable in the read-write shared-memory model using the unbounded full-information protocol, where in every round of computation, each process shares its complete knowledge of the system with the other processes. Therefore, ACT assumes shared-memory variables of unbounded capacity. It has been recently shown that boundedvariables can achieve the same computational power at the expense of extra rounds. However, the exact relationship between the bit capacity of the shared memory and the number of rounds required in order to implement one round of the full-information protocol remained unknown. In this paper, we focus on the asymptotic round complexity of bounded iterated shared-memory algorithms that simulate, up to isomorphism, the unbounded full-information protocol. We relate the round complexity to the number of processes $n$, the number of iterations of the full information protocol $r$, and the bit size per shared-memory entry $b$. By analyzing the corresponding protocol complex, a combinatorial structure representing reachable states, we derive necessary conditions and present a bounded full-information algorithm tailored to the bits available $b$ per shared memory entry. We show that for $n>2$, the round complexity required to implement the full-information protocol satisfies $Ω((n!)^{r-1} \cdot 2^{n-b})$. Our results apply to a range of iterated shared-memory models, from regular read-write registers to atomic and immediate snapshots. Moreover, our bounded full-information algorithm is asymptotically optimal for the iterated collect model and within a linear factor $n$ of optimal for the snapshot-based models. - Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 260-263
Brief Announcement: Fast Atomic Snapshot and Asynchronous Latency
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 260-263
Open AccessBrief Announcement: Fast Atomic Snapshot and Asynchronous Latency
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 62-65
Brief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 62-65
Open AccessBrief Announcement: Optimal Construction of Unique Identifiers from Bounded Registers
- Open Access
- 20 February 2024
- Published by Association for Computing Machinery (ACM)
- p. 188-199
Memory Bounds for Concurrent Bounded Queues
Concurrent data structures often require additional memory for handling synchronization issues in addition to memory for storing elements. Depending on the amount of this additional memory, implementations can be more or less memory-friendly. A memory-optimal implementation enjoys the minimal possible memory overhead, which, in practice, reduces cache misses and unnecessary memory reclamation. In this paper, we discuss the memory-optimality of non-blocking bounded queues. Essentially, we investigate the possibility of constructing an implementation that utilizes a pre-allocated array to store elements and constant memory overhead, e.g., two positioning counters for enqueue(..) and dequeue() operations. Such an implementation can be readily constructed when the ABA problem is precluded, e.g., assuming that the hardware supports LL/SC instructions or all inserted elements are distinct. However, in the general case, we show that a memory-optimal non-blocking bounded queue incurs linear overhead in the number of concurrent processes. These results not only provide helpful intuition for concurrent algorithm developers but also open a new research avenue on the memory-optimality phenomenon in concurrent data structures. The full version of this paper is available on arXiv [2].
- 20 February 2024
- Published by Association for Computing Machinery (ACM)
- p. 188-199
Open AccessMemory Bounds for Concurrent Bounded Queues
Concurrent data structures often require additional memory for handling synchronization issues in addition to memory for storing elements. Depending on the amount of this additional memory, implementations can be more or less memory-friendly. A memory-optimal implementation enjoys the minimal possible memory overhead, which, in practice, reduces cache misses and unnecessary memory reclamation. In this paper, we discuss the memory-optimality of non-blocking bounded queues. Essentially, we investigate the possibility of constructing an implementation that utilizes a pre-allocated array to store elements and constant memory overhead, e.g., two positioning counters for enqueue(..) and dequeue() operations. Such an implementation can be readily constructed when the ABA problem is precluded, e.g., assuming that the hardware supports LL/SC instructions or all inserted elements are distinct. However, in the general case, we show that a memory-optimal non-blocking bounded queue incurs linear overhead in the number of concurrent processes. These results not only provide helpful intuition for concurrent algorithm developers but also open a new research avenue on the memory-optimality phenomenon in concurrent data structures. The full version of this paper is available on arXiv [2].
- Open Access
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 1556-1570
CryptoConcurrency: (Almost) Consensusless Asset Transfer with Shared Accounts
A typical blockchain protocol uses consensus to make sure that mutually mistrusting users agree on the order in which their operations on shared data are executed. However, it is known that asset transfer systems, by far the most popular application of blockchains, can be implemented without consensus. Assuming that no account can be accessed concurrently and every account belongs to a single owner, one can efficiently implement an asset transfer system in a purely asynchronous, consensus-free manner. It has also been shown that implementing asset transfer with shared accounts is impossible without consensus. In this paper, we propose CryptoConcurrency, an asset transfer protocol that allows concurrent accesses to be processed in parallel, without involving consensus, whenever possible. More precisely, if concurrent transfer operations on a given account do not lead to overspending, i.e. can all be applied without the account balance going below zero, they proceed in parallel. Otherwise, the account's owners may have to access an external consensus object. Notably, we avoid relying on a central, universally-trusted, consensus mechanism and allow each account to use its own consensus implementation, which only the owners of this account trust. This provides greater decentralization and flexibility.
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 1556-1570
Open AccessCryptoConcurrency: (Almost) Consensusless Asset Transfer with Shared Accounts
A typical blockchain protocol uses consensus to make sure that mutually mistrusting users agree on the order in which their operations on shared data are executed. However, it is known that asset transfer systems, by far the most popular application of blockchains, can be implemented without consensus. Assuming that no account can be accessed concurrently and every account belongs to a single owner, one can efficiently implement an asset transfer system in a purely asynchronous, consensus-free manner. It has also been shown that implementing asset transfer with shared accounts is impossible without consensus. In this paper, we propose CryptoConcurrency, an asset transfer protocol that allows concurrent accesses to be processed in parallel, without involving consensus, whenever possible. More precisely, if concurrent transfer operations on a given account do not lead to overspending, i.e. can all be applied without the account balance going below zero, they proceed in parallel. Otherwise, the account's owners may have to access an external consensus object. Notably, we avoid relying on a central, universally-trusted, consensus mechanism and allow each account to use its own consensus implementation, which only the owners of this account trust. This provides greater decentralization and flexibility.
- 18 May 2023
- Published by Springer Nature in Distributed Computing
- Vol. 36 (3) , 349-371
Permissionless and asynchronous asset transfer
- 18 May 2023
- Published by Springer Nature in Distributed Computing
- Vol. 36 (3) , 349-371
Permissionless and asynchronous asset transfer