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

Gokarna Sharma

Gokarna Sharma contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsPerformanceRobotics

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
4topics
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

4 published item(s)

preprint2022arXiv

Blockchain in Dynamic Networks

We consider blockchain in dynamic networks. We define the Blockchain Decision Problem. It requires miners that maintain the blockchain to confirm whether a particular block is accepted. We establish the necessary conditions for the existence of a solution. We, however, prove that the solution, even under these necessary conditions is, in general, impossible. We then present two algorithms that solve the Blockchain Decision Problem under either the knowledge of the maximum source pool propagation time or the knowledge of the source pool membership. We evaluate the performance of the two algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Near-Optimal Dispersion on Arbitrary Anonymous Graphs

Given an undirected, anonymous, port-labeled graph of $n$ memory-less nodes, $m$ edges, and degree $Δ$, we consider the problem of dispersing $k\leq n$ robots (or tokens) positioned initially arbitrarily on one or more nodes of the graph to exactly $k$ different nodes of the graph, one on each node. The objective is to simultaneously minimize time to achieve dispersion and memory requirement at each robot. If all $k$ robots are positioned initially on a single node, depth first search (DFS) traversal solves this problem in $O(\min\{m,kΔ\})$ time with $Θ(\log(k+Δ))$ bits at each robot. However, if robots are positioned initially on multiple nodes, the best previously known algorithm solves this problem in $O(\min\{m,kΔ\}\cdot \log \ell)$ time storing $Θ(\log(k+Δ))$ bits at each robot, where $\ell\leq k/2$ is the number of multiplicity nodes in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in $O(\min\{m,kΔ\})$ time with $Θ(\log(k+Δ))$ bits at each robot, improving the time bound of the best previously known algorithm by $O(\log \ell)$ and matching asymptotically the single-source DFS traversal bounds. This is the first algorithm for dispersion that is optimal in both time and memory in arbitrary anonymous graphs of constant degree, $Δ=O(1)$. Furthermore, the result holds in both synchronous and asynchronous settings.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Competitive Analysis for Balanced Transactional Memory Workloads

We consider transactional memory contention management in the context of balanced workloads, where if a transaction is writing, the number of write operations it performs is a constant fraction of its total reads and writes. We explore the theoretical performance boundaries of contention management in balanced workloads from the worst-case perspective by presenting and analyzing two new contention management algorithms. The first algorithm Clairvoyant is O(\surd s)-competitive, where s is the number of shared resources. This algorithm depends on explicitly knowing the conflict graph. The second algorithm Non-Clairvoyant is O(\surd s \cdot log n)-competitive, with high probability, which is only a O(log n) factor worse, but does not require knowledge of the conflict graph, where n is the number of transactions. Both of these algorithms are greedy. We also prove that the performance of Clairvoyant is tight since there is no contention management algorithm that is better than O((\surd s)^(1-ε))-competitive for any constant ε> 0, unless NP\subseteq ZPP. To our knowledge, these results are significant improvements over the best previously known O(s) competitive ratio bound.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Window-Based Greedy Contention Management for Transactional Memory

We consider greedy contention managers for transactional memory for M x N execution windows of transactions with M threads and N transactions per thread. Assuming that each transaction conflicts with at most C other transactions inside the window, a trivial greedy contention manager can schedule them within CN time. In this paper, we show that there are much better schedules. We present and analyze two new randomized greedy contention management algorithms. The first algorithm Offline-Greedy produces a schedule of length O(C + N log(MN)) with high probability, and gives competitive ratio O(log(MN)) for C <= N log(MN). The offline algorithm depends on knowing the conflict graph. The second algorithm Online-Greedy produces a schedule of length O(C log(MN) + N log^2(MN)) with high probability which is only a O(log(NM)) factor worse, but does not require knowledge of the conflict graph. We also give an adaptive version which achieves similar worst-case performance and C is determined on the fly under execution. Our algorithms provide new tradeoffs for greedy transaction scheduling that parameterize window sizes and transaction conflicts within the window.

0 citations0 reviewsNo code linkedOpen access