BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Petr Kuznetsov

Petr Kuznetsov contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster Computing

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2022arXiv

Distributed Randomness from Approximate Agreement

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^3 \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^4)$. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

How to Tame Multiple Spending in Decentralized Cryptocurrencies

The last decade has seen a variety of Asset-Transfer systems designed for decentralized environments. To address the problem of double-spending, these systems inherently make strong model assumptions and spend a lot of resources. 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 its local quorums. In this setting, we define $k$-Spending Asset Transfer, a relaxed version of asset transfer which bounds the number of times the same asset can be spent. We establish a precise relationship between the decentralized trust assumptions and $k$, the optimal spending number of the system.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Concurrency-Optimal List-Based Set

Designing an efficient concurrent data structure is an important challenge that is not easy to meet. Intuitively, efficiency of an implementation is defined, in the first place, by its ability to process applied operations in parallel, without using unnecessary synchronization. As we show in this paper, even for a data structure as simple as a linked list used to implement the set type, the most efficient algorithms known so far are not concurrency-optimal: they may reject correct concurrent schedules. We propose a new algorithm for the list-based set based on a value-aware try-lock that we show to achieve optimal concurrency: it only rejects concurrent schedules that violate correctness of the implemented set type. We show empirically that reaching optimality does not induce a significant overhead. In fact, our implementation of the concurrency-optimal algorithm outperforms both the Lazy Linked List and the Harris-Michael state-of-the-art algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Asynchronous Computability Theorem for Fair Adversaries

This paper proposes a simple topological characterization of a large class of fair adversarial 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. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and $k$-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Decidability of 2-process Affine Models

An affine model of computation is defined as a subset of iterated immediate-snapshot runs, capturing a wide variety of shared-memory systems, such as 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 the task computability of 2-process affine models is decidable and presents a complete hierarchy of the five equivalence classes of 2-process affine models.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Online Payments by Merely Broadcasting Messages (Extended Version)

We address the problem of online payments, where users can transfer funds among themselves. We introduce Astro, a system solving this problem efficiently in a decentralized, deterministic, and completely asynchronous manner. Astro builds on the insight that consensus is unnecessary to prevent double-spending. Instead of consensus, Astro relies on a weaker primitive---Byzantine reliable broadcast---enabling a simpler and more efficient implementation than consensus-based payment systems. In terms of efficiency, Astro executes a payment by merely broadcasting a message. The distinguishing feature of Astro is that it can maintain performance robustly, i.e., remain unaffected by a fraction of replicas being compromised or slowed down by an adversary. Our experiments on a public cloud network show that Astro can achieve near-linear scalability in a sharded setup, going from $10K$ payments/sec (2 shards) to $20K$ payments/sec (4 shards). In a nutshell, Astro can match VISA-level average payment throughput, and achieves a $5\times$ improvement over a state-of-the-art consensus-based solution, while exhibiting sub-second $95^{th}$ percentile latency.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reconfigurable Lattice Agreement and Applications

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Scalable Byzantine Reliable Broadcast (Extended Version)

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 we call adversary decorators. Adversary decorators allow us to make claims about the optimal strategy of the Byzantine adversary without having to make 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.

0 citations0 reviewsNo code linkedOpen access