12 Search Results for "Sharma, Gokarna"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.32
Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Authors: Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. They analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the φ-free graphs, a class that includes every graph with maximum degree at most three and every cactus.
Cite as

Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo. Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.OPODIS.2025.32,
  author =	{Takahashi, Shota and Kanaya, Haruki and Hiraoka, Shoma and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.32},
  URN =		{urn:nbn:de:0030-drops-252052},
  doi =		{10.4230/LIPIcs.OPODIS.2025.32},
  annote =	{Keywords: mobile agents, recolorable graphs, graph exploration}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.2
On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding

Authors: Ramesh Adhikari, Costas Busch, and Miroslav Popovic

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Sharding is a technique to speed up transaction processing in blockchains, where the n processing nodes in the blockchain are divided into s disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph G_s where transactions arrive online over time and are not known in advance. Each transaction may access at most k shards, and we denote by d the worst distance between a transaction and its accessing (destination) shards (the parameter d is unknown to the shards). To handle different values of d, we assume a locality sensitive decomposition of G_s into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model, where leaders are not aware of the current state of the transaction accounts, and we prove a O(d log² s ⋅ min{k, √s}) competitive ratio for latency. We then consider the stateful model, where leader shards gather the current state of accounts, and we prove a O(log s⋅ min{k, √s}+log² s) competitive ratio for latency. Each leader calculates the schedule in polynomial time for each transaction that it processes. We show that for any ε > 0, approximating the optimal schedule within a (min{k, √s})^{1 -ε} factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. To the best of our knowledge, this is the first work to establish provably efficient dynamic scheduling algorithms for blockchain sharding systems.
Cite as

Ramesh Adhikari, Costas Busch, and Miroslav Popovic. On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adhikari_et_al:LIPIcs.DISC.2025.2,
  author =	{Adhikari, Ramesh and Busch, Costas and Popovic, Miroslav},
  title =	{{On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{2:1--2:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.2},
  URN =		{urn:nbn:de:0030-drops-248191},
  doi =		{10.4230/LIPIcs.DISC.2025.2},
  annote =	{Keywords: Blockchain, Blockchain Sharding, Dynamic Transaction Scheduling}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.56
Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers

Authors: Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, aka perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the LUMI model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities). However, we prove that, to be solvable under LUMI, the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots. We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.
Cite as

Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro. Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 56:1-56:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.DISC.2025.56,
  author =	{Feletti, Caterina and Flocchini, Paola and Pattanayak, Debasish and Prencipe, Giuseppe and Santoro, Nicola},
  title =	{{Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{56:1--56:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.56},
  URN =		{urn:nbn:de:0030-drops-248724},
  doi =		{10.4230/LIPIcs.DISC.2025.56},
  annote =	{Keywords: Luminous Robots, Sequence of Patterns, Pattern Formation, Sequential Scheduler}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.63
Brief Announcement: Optimal Dispersion Under Asynchrony

Authors: Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.
Cite as

Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. Brief Announcement: Optimal Dispersion Under Asynchrony. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 63:1-63:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pattanayak_et_al:LIPIcs.DISC.2025.63,
  author =	{Pattanayak, Debasish and Kshemkalyani, Ajay D. and Kumar, Manish and Molla, Anisur Rahaman and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Dispersion Under Asynchrony}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{63:1--63:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.63},
  URN =		{urn:nbn:de:0030-drops-248795},
  doi =		{10.4230/LIPIcs.DISC.2025.63},
  annote =	{Keywords: Distributed algorithms, mobile agents, local communication, dispersion, asynchrony, port-one tree, time and memory complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.10
Amnesiac Flooding: Easy to Break, Hard to Escape

Authors: Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/ STACS'20/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults? In this paper we make progress on both of these fronts. Under a reasonable restriction (obliviousness to message content) additional to the fault-free synchronous model, we prove that Amnesiac Flooding is the only strictly stateless deterministic protocol that can achieve terminating broadcast. We achieve this by identifying four natural properties of a terminating broadcast protocol that Amnesiac Flooding uniquely satisfies. In contrast, we prove that even minor relaxations of any of these four criteria allow the construction of other terminating broadcast protocols. On the other hand, we prove that Amnesiac Flooding can become non-terminating or non-broadcasting, even if we allow just one node to drop a single message on a single edge in a single round. As a tool for proving this, we focus on the set of all configurations of transmissions between nodes in the network, and obtain a dichotomy characterizing the configurations, starting from which, Amnesiac Flooding terminates. Additionally, we characterise the structure of sets of Byzantine agents capable of forcing non-termination or non-broadcast of the protocol on arbitrary networks.
Cite as

Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan. Amnesiac Flooding: Easy to Break, Hard to Escape. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austin_et_al:LIPIcs.DISC.2025.10,
  author =	{Austin, Henry and Gadouleau, Maximilien and Mertzios, George B. and Trehan, Amitabh},
  title =	{{Amnesiac Flooding: Easy to Break, Hard to Escape}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.10},
  URN =		{urn:nbn:de:0030-drops-248273},
  doi =		{10.4230/LIPIcs.DISC.2025.10},
  annote =	{Keywords: Amnesiac flooding, Terminating protocol, Algorithm state, Stateless protocol, Flooding algorithm, Network algorithms, Graph theory, Termination, Communication, Broadcast}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.41
Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

Authors: Ashish Saxena and Kaushik Mondal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the exploration problem by mobile agents in Connectivity Time dynamic graphs. The Connectivity Time model was introduced by Michail et al. [JPDC 2014] and is arguably one of the weakest dynamic graph connectivity models. We prove that exploration is impossible in such graphs using ((n-1)(n-2))/2 mobile agents starting from an arbitrary initial configuration, even when agents have full knowledge of system parameters, global communication, full visibility, and infinite memory. We then present an exploration algorithm that uses ((n-1)(n-2))/2 + 1 agents equipped with global communication, 1-hop visibility and O(log n) memory.
Cite as

Ashish Saxena and Kaushik Mondal. Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 41:1-41:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.DISC.2025.41,
  author =	{Saxena, Ashish and Mondal, Kaushik},
  title =	{{Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{41:1--41:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.41},
  URN =		{urn:nbn:de:0030-drops-248585},
  doi =		{10.4230/LIPIcs.DISC.2025.41},
  annote =	{Keywords: Mobile agents, Anonymous graphs, Exploration, Dynamic graphs, Deterministic algorithm}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.10
Fault Detection and Identification by Autonomous Mobile Robots

Authors: Stefano Clemente and Caterina Feletti

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
The Look-Compute-Move model (LCM) is adopted to study swarms of mobile robots that have to solve a given problem. Robots are generally assumed to be autonomous, indistinguishable, anonymous, homogeneous and to move on the Euclidean plane. Different LCM sub-models have been theorized to study different settings and their computational power. Notably, the literature has focused on four base models (i.e., OBLOT, FSTA, FCOM, LUMI) that differ in memory and communication capabilities, and in different synchronization modes (e.g., fully synchronous FSYNCH, semi-synchronous SSYNCH). In this paper, we consider fault-prone models where robots can suffer from crash faults: each robot may irremediably stop working after an unpredictable time. We study the general Fault Detection (FD) problem which is solved by a swarm if it correctly detects whether a faulty robot exists in the swarm. The Fault Identification (FI) problem additionally requires identifying which robots are faulty. We consider 12 LCM sub-models (OBLOT, FSTA, FCOM, LUMI, combined with FSYNCH, SSYNCH, and the round-robin RROBIN) and we study the (im)possibility of designing reliable procedures to solve FD or FI. In particular, we propose three distributed algorithms so that a swarm can collectively solve FD under the models LUMI^FSYNCH, FCOM^FSYNCH, and LUMI^RROBIN.
Cite as

Stefano Clemente and Caterina Feletti. Fault Detection and Identification by Autonomous Mobile Robots. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.SAND.2025.10,
  author =	{Clemente, Stefano and Feletti, Caterina},
  title =	{{Fault Detection and Identification by Autonomous Mobile Robots}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.10},
  URN =		{urn:nbn:de:0030-drops-230639},
  doi =		{10.4230/LIPIcs.SAND.2025.10},
  annote =	{Keywords: Autonomous mobile robots, Faulty robots, Look-Compute-Move, Fault detection, Fault identification, Round-robin}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.12
Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings

Authors: Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, and Yuichi Sudo

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2).
Cite as

Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, and Yuichi Sudo. Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ooshita_et_al:LIPIcs.OPODIS.2024.12,
  author =	{Ooshita, Fukuhito and Kitamura, Naoki and Eguchi, Ryota and Inoue, Michiko and Kakugawa, Hirotsugu and Kamei, Sayaka and Shibata, Masahiro and Sudo, Yuichi},
  title =	{{Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.12},
  URN =		{urn:nbn:de:0030-drops-225486},
  doi =		{10.4230/LIPIcs.OPODIS.2024.12},
  annote =	{Keywords: mobile robots, crash faults, LCM model, exploration}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.46
Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots

Authors: Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We study the Uniform Circle Formation (UCF) problem for a swarm of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the Euclidean plane. We assume our robots are luminous, i.e. equipped with a persistent light that can assume a color chosen from a fixed palette, and opaque, i.e. not able to see beyond a collinear robot. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. To solve UCF, a swarm of n robots must autonomously arrange themselves so that each robot occupies a vertex of the same regular n-gon not fixed in advance. In terms of efficiency, the goal is to design an algorithm that optimizes (or provides a tradeoff between) two fundamental performance metrics: (i) the execution time and (ii) the size of the color palette. In this paper, we develop a deterministic algorithm solving UCF avoiding collisions in O(1)-time with O(1) colors under the asynchronous scheduler, which is asymptotically optimal with respect to both time and number of colors used, the first such result. Furthermore, the algorithm proposed here minimizes for the first time what we call the computational SEC, i.e. the smallest circular area where robots operate throughout the whole algorithm.
Cite as

Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma. Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 46:1-46:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.DISC.2024.46,
  author =	{Feletti, Caterina and Pattanayak, Debasish and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{46:1--46:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.46},
  URN =		{urn:nbn:de:0030-drops-212748},
  doi =		{10.4230/LIPIcs.DISC.2024.46},
  annote =	{Keywords: Uniform Circle Formation, Robots with Lights, Autonomous Robots, Rank Encoding, Time and Color Complexities, Computational SEC}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.50
Brief Announcement: Agent-Based Leader Election, MST, and Beyond

Authors: Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
Leader election is one of the fundamental and well-studied problems in distributed computing. In this paper, we initiate the study of leader election using mobile agents. Suppose n agents are positioned initially arbitrarily on the nodes of an arbitrary, anonymous, n-node, m-edge graph G. The agents relocate themselves autonomously on the nodes of G and elect an agent as a leader such that the leader agent knows it is a leader and the other agents know they are not leaders. The objective is to minimize time and memory requirements. Following the literature, we consider the synchronous setting in which each agent performs its operations synchronously with others and hence the time complexity can be measured in rounds. The quest in this paper is to provide solutions without agents knowing any graph parameter, such as n, a priori. We first establish that, without agents knowing any graph parameter a priori, there exists a deterministic algorithm to elect an agent as a leader in O(m) rounds with O(nlog n) bits at each agent. Using this leader election result, we develop a deterministic algorithm for agents to construct a minimum spanning tree of G in O(m+nlog n) rounds using O(n log n) bits memory at each agent, without agents knowing any graph parameter a priori. Finally, using the same leader election result, we provide improved time/memory results for other fundamental distributed graph problems, namely, gathering, maximal independent set, and minimal dominating sets, removing the assumptions on agents knowing graph parameters a priori.
Cite as

Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. Brief Announcement: Agent-Based Leader Election, MST, and Beyond. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 50:1-50:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kshemkalyani_et_al:LIPIcs.DISC.2024.50,
  author =	{Kshemkalyani, Ajay D. and Kumar, Manish and Molla, Anisur Rahaman and Sharma, Gokarna},
  title =	{{Brief Announcement: Agent-Based Leader Election, MST, and Beyond}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{50:1--50:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.50},
  URN =		{urn:nbn:de:0030-drops-212782},
  doi =		{10.4230/LIPIcs.DISC.2024.50},
  annote =	{Keywords: Distributed algorithms, mobile agents, local communication, leader election, MST, MIS, gathering, minimal dominating sets, time and memory complexity, graph parameters}
}
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.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.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 Type
  • 12 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 2 2024
  • 1 2022
  • 1 2021

  • Refine by Author
  • 5 Sharma, Gokarna
  • 3 Feletti, Caterina
  • 3 Kshemkalyani, Ajay D.
  • 3 Pattanayak, Debasish
  • 2 Eguchi, Ryota
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 10 Theory of computation → Distributed algorithms
  • 3 Computing methodologies → Distributed algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 1 Computer systems organization → Robotics
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 4 Distributed algorithms
  • 3 mobile agents
  • 2 Blockchain
  • 2 Exploration
  • 2 local communication
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact