2 Search Results for "Sharma, Gokarna"

Document
DOI: 10.4230/LIPIcs.OPODIS.2021.8
Near-Optimal Dispersion on Arbitrary Anonymous Graphs

Authors: Ajay D. Kshemkalyani and Gokarna Sharma

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Given an undirected, anonymous, port-labeled graph of n memory-less nodes, m edges, and degree Δ, we consider the problem of dispersing k ≤ 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Δ}⋅ log 𝓁) time storing Θ(log(k+Δ)) bits at each robot, where 𝓁 ≤ 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 𝓁) 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.
Cite as

Ajay D. Kshemkalyani and Gokarna Sharma. Near-Optimal Dispersion on Arbitrary Anonymous Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kshemkalyani_et_al:LIPIcs.OPODIS.2021.8,
  author =	{Kshemkalyani, Ajay D. and Sharma, Gokarna},
  title =	{{Near-Optimal Dispersion on Arbitrary Anonymous Graphs}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{8:1--8:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.8},
  URN =		{urn:nbn:de:0030-drops-157837},
  doi =		{10.4230/LIPIcs.OPODIS.2021.8},
  annote =	{Keywords: Distributed algorithms, Multi-agent systems, Mobile robots, Local communication, Dispersion, Exploration, Time and memory complexity}
}
Document
Short Paper
DOI: 10.4230/OASIcs.Tokenomics.2020.12
Blockguard: Adaptive Blockchain Security (Short Paper)

Authors: Shishir Rai, Kendric Hood, Mikhail Nesterenko, and Gokarna Sharma

Published in: OASIcs, Volume 82, 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)

Abstract
We change the security of blockchain transactions by varying the size of consensus committees. To improve performance, such committees operate concurrently. We present two algorithms that allow adaptive security by forming concurrent variable size consensus committees on demand. One is based on a single joint blockchain, the other is based on separate sharded blockchains. For in-committee consensus, we implement synchronous Byzantine fault tolerance algorithm (BFT), asynchronous BFT and proof-of-work consensus. We evaluate the performance of our adaptive security algorithms.
Cite as

Shishir Rai, Kendric Hood, Mikhail Nesterenko, and Gokarna Sharma. Blockguard: Adaptive Blockchain Security (Short Paper). In 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020). Open Access Series in Informatics (OASIcs), Volume 82, pp. 12:1-12:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rai_et_al:OASIcs.Tokenomics.2020.12,
  author =	{Rai, Shishir and Hood, Kendric and Nesterenko, Mikhail and Sharma, Gokarna},
  title =	{{Blockguard: Adaptive Blockchain Security}},
  booktitle =	{2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)},
  pages =	{12:1--12:5},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-157-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{82},
  editor =	{Anceaume, Emmanuelle and Bisi\`{e}re, Christophe and Bouvard, Matthieu and Bramas, Quentin and Casamatta, Catherine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2020.12},
  URN =		{urn:nbn:de:0030-drops-135347},
  doi =		{10.4230/OASIcs.Tokenomics.2020.12},
  annote =	{Keywords: Blockchain, Consensus, Security, Distributed algorithms}
}
  • Refine by Author
  • 2 Sharma, Gokarna
  • 1 Hood, Kendric
  • 1 Kshemkalyani, Ajay D.
  • 1 Nesterenko, Mikhail
  • 1 Rai, Shishir

  • Refine by Classification
  • 2 Computing methodologies → Distributed algorithms
  • 1 Computer systems organization → Robotics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Networks → Security protocols
  • 1 Security and privacy → Distributed systems security
  • Show More...

  • Refine by Keyword
  • 2 Distributed algorithms
  • 1 Blockchain
  • 1 Consensus
  • 1 Dispersion
  • 1 Exploration
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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