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

Vijay Garg

Vijay Garg contributes to research discovery and scholarly infrastructure.

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

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
1topics
3close 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

3 published item(s)

preprint2020arXiv

Amortized Constant Round Atomic Snapshot in Message-Passing Systems

We study the lattice agreement (LA) and atomic snapshot problems in asynchronous message-passing systems where up to $f$ nodes may crash. Our main result is a crash-tolerant atomic snapshot algorithm with \textit{amortized constant round complexity}. To the best of our knowledge, the best prior result is given by Delporte et al. [TPDS, 18] with amortized $O(n)$ complexity if there are more scans than updates. Our algorithm achieves amortized constant round if there are $Ω(\sqrt{k})$ operations, where $k$ is the number of actual failures in an execution and is bounded by $f$. Moreover, when there is no failure, our algorithm has $O(1)$ round complexity unconditionally. To achieve amortized constant round complexity, we devise a simple \textit{early-stopping} lattice agreement algorithm and use it to "order" the update and scan operations for our snapshot object. Our LA algorithm has $O(\sqrt{k})$ round complexity. It is the first early-stopping LA algorithm in asynchronous systems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Byzantine Lattice Agreement in Asynchronous Systems

We study the Byzantine lattice agreement (BLA) problem in asynchronous distributed message passing systems. In the BLA problem, each process proposes a value from a join semi-lattice and needs to output a value also in the lattice such that all output values of correct processes lie on a chain despite the presence of Byzantine processes. We present an algorithm for this problem with round complexity of $O(\log f)$ which tolerates $f < \frac{n}{5}$ Byzantine failures in the asynchronous setting without digital signatures, where $n$ is the number of processes. We also show how this algorithm can be modified to work in the authenticated setting (i.e., with digital signatures) to tolerate $f < \frac{n}{3}$ Byzantine failures.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Byzantine Lattice Agreement in Synchronous Systems

In this paper, we study the Byzantine lattice agreement problem in synchronous systems. The lattice agreement problem in crash failure model has been studied both in synchronous and asynchronous systems, which leads to the current best upper bound of $O(\log f)$ rounds in both systems. However, very few algorithmic results are known for the lattice agreement problem in Byzantine failure model. The paper [Nowak et al., DISC, 2019] first gives an algorithm for a variant of the lattice agreement problem on cycle-free lattices that tolerates up to $f < n/(h(X) + 1)$ Byzantine faults, where $n$ is the number of processes and $h(X)$ is the height of the input lattice $X$. The recent preprint by Di et al. studies this problem with a slightly modified validity condition in asynchronous systems. They present a $O(f)$ rounds algorithm by using the reliable broadcast primitive as a first step and following the similar algorithmic framework as the algorithms in crash failure model. In this paper, we propose three algorithms for the Byzantine lattice agreement problem in synchronous systems. The first algorithm takes $\min \{3h(X) + 6,6\sqrt{f} + 6\})$ rounds and $O(n^2 \min\{h(X), \sqrt{f}\})$ messages, where $h(X)$ is the height of the input lattice $X$, $n$ is the total number of processes. The second algorithm runs in $3\log n + 3$ rounds and takes $O(n^2 \log n)$ messages. The third algorithm takes $4 \log f + 3$ rounds and takes $O(n^2 \log f)$ messages. All algorithms can tolerate up to $f < \frac{n}{3}$ Byzantine failures.

0 citations0 reviewsNo code linkedOpen access