检索结果-内蒙古大学图书馆

Near-optimal dispersion on arbitrary anonymous graphs

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 152卷

作者： Kshemkalyani, Ajay D. Sharma, Gokarna Univ Illinois Dept Comp Sci Chicago IL USA Kent State Univ Dept Comp Sci Kent OH 44240 USA

Given an undirected, anonymous, port-labeled graph of n memory-less nodes, m edges, and degree Delta, we consider the problem of dispersing k <= n robots (or tokens) positioned initially arbitrarily on the nodes of the graph to exactly k different nodes, one on each node. The objective is to simultaneously minimize time and memory requirement at each robot. The best previously known algorithm solves this problem in O(min{m,k Delta}.log l) time storing O(log(k+Delta)) bits at each robot, where l <= k/2 is the number of nodes with multiple robots positioned on them in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in O(min{m,k Delta}) time with O(log(k+Delta)) bits at each robot. The memory complexity of our algorithm is already asymptotically optimal and the time complexity is asymptotically optimal for the graphs of constant degree Delta=O(1). The result holds in both synchronous and asynchronous settings. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC license (http://***/licenses/by-nc/4.0/).

关键词： Distributed algorithms Multi-agent systems Mobile robots Local communication Dispersion Exploration time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

Faster Leader Election and Its Applications for Mobile Agents with Parameter Advice 21st

Faster Leader Election and Its Applications for Mobile Agent...

引用

21st International Conference on Distributed Computing and Intelligent Technology

作者： Kshemkalyani, Ajay D. Kumar, Manish Molla, Anisur Rahaman Sharma, Gokarna Univ Illinois Chicago IL USA Indian Inst Technol Madras Chennai Tamil Nadu India Indian Stat Inst Kolkata India Kent State Univ Kent OH USA

ISBN: (纸本)9783031814037;9783031814044

Leader election is a critical and extensively studied problem in distributed computing. This paper introduces the study of leader election using mobile agents. Consider n agents initially placed arbitrarily on the nodes of an arbitrary, n-node, m-edge graph G. These agents move autonomously across the nodes of G and elect one agent as the leader such that the leader is aware of its status as the leader, and the other agents know they are not the leader. The goal is to minimize both time and memory usage. We study the leader election problem in a synchronous setting where each agent performs operations simultaneously with the others, allowing us to measure time complexity in terms of rounds. We assume that the agents have prior knowledge of the number of nodes n and the maximum degree of the graph Delta. We first elect a leader deterministically in O(n log(2) n + D Delta log n) rounds with each agent using O(log n) bits of memory, where D is the diameter of the graph. Leveraging this leader election result, we then present a deterministic algorithm for constructing a minimum spanning tree of G in O(m+ n log n) rounds, with each agent using O(Delta log n) bits of memory. Finally, using the same leader election result, we improve time and memory bounds for other key distributed graph problems, including gathering, maximal independent set, and minimal dominating set. For all the aforementioned problems, our algorithms remain memory-optimal.

关键词： Distributed algorithms mobile agents local communication leader election MST MIS gathering minimal dominating set time and memory complexity graph parameters

来源：评论

学校读者我要写书评

暂无评论

Dispersion of mobile robots using global communication

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2022年 161卷 100-117页

作者： Kshemkalyani, Ajay D. Molla, Anisur Rahaman Sharma, Gokarna Univ Illinois Chicago IL USA Indian Stat Inst Kolkata India Kent State Univ Kent OH 44242 USA

The dispersion problem on graphs asks k <= n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driven electric cars (robots) to recharge stations (nodes). In this paper, we consider dispersion using the global communication model where a robot can communicate with any other robot in the graph (but the graph is unknown to robots). We provide two novel deterministic algorithms for arbitrary graphs in a synchronous setting where all robots perform their actions in every time step. Our first algorithm is based on a DFS traversal and guarantees (i) O(k Delta) steps runtime using O (log(k + Delta))) bits at each robot and (ii) O(min(m, k Delta)) steps runtime using O(Delta + log k) bits at each robot, where m is the number of edges and Delta is the maximum degree of the graph. The second algorithm is based on a BFS traversal and guarantees O ((D + k)Delta(D + Delta)) steps runtime using O (log D + Delta log k)) bits at each robot, where D is the diameter of the graph. Our results complement the existing results established using the local communication model where a robot can communication only with other robots present at the same node. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Multi-agent systems Autonomous mobile robots Dispersion Distributed algorithms time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

Collaborative Dispersion by Silent Robots 24th

Collaborative Dispersion by Silent Robots

引用

24th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)

作者： Gorain, Barun Mandal, Partha Sarathi Mondal, Kaushik Pandit, Supantha Indian Inst Technol Bhilai Sejbahar India Indian Inst Technol Guwahati Gauhati India Indian Inst Technol Ropar Rupnagar Punjab India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

ISBN: (纸本)9783031210167;9783031210174

In the dispersion problem, a set of k co-located mobile robots must relocate themselves in distinct nodes of an unknown network. The network is modeled as an anonymous graph G = (V, E), where the graph's nodes are not labeled. The edges incident to a node v with degree d are labeled with port numbers in the range {0, 1,..., d - 1} at v. The robots have unique IDs in the range [0, L], where L >= k, and are initially placed at a source node s. Each robot knows only its ID, however, it does not know the IDs of the other robots or the values of L or k. The task of the dispersion was traditionally achieved based on the assumption of two types of communication abilities: (a) when some robots are at the same node, they can communicate by exchanging messages between them, and (b) any two robots in the network can exchange messages between them. This paper investigates whether this communication ability among co-located robots is absolutely necessary to achieve the dispersion. We established that even in the absence of the ability of communication, the task of the dispersion by a set of mobile robots can be achieved in a much weaker model, where a robot at a node v has the access of following very restricted information at the beginning of any round: (1) am I alone at v? (2) did the number of robots at v increase or decrease compared to the previous round? We propose a deterministic distributed algorithm that achieves the dispersion on any given graph G = (V, E) in time O (k log L + k(2) log Delta), where. is the maximum degree of a node in G. Further, each robot uses O(log L + log Delta) additional memory. We also prove that the task of the dispersion cannot be achieved by a set of mobile robots with o(log L + log Delta) additional memory.

关键词： Autonomous mobile robots Anonymous graphs Dispersion Deterministic algorithm time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

Dispersion of Mobile Robots on Directed Anonymous Graphs 1

引用

29th International Colloquium on Structural Information and Communication complexity (SIROCCO)

作者： Italiano, Giuseppe F. Pattanayak, Debasish Sharma, Gokarna LUISS Univ Rome Italy Kent State Univ Kent OH 44242 USA

ISBN: (数字)9783031099939

ISBN: (纸本)9783031099939;9783031099922

Given any arbitrary initial configuration of k <= n robots positioned on the nodes of an n-node anonymous graph, the problem of dispersion is to autonomously reposition the robots such that each node will contain at most one robot. This problem gained significant interest due to its resemblance with several fundamental problems such as exploration, scattering, load balancing, relocation of electric cars to charging stations, etc. The objective is to solve dispersion simultaneously minimizing (or providing a trade-off between) time and memory requirement at each robot. The literature mainly dealt with dispersion on undirected anonymous graphs. In this paper, we initiate the study of dispersion on directed anonymous graphs. We first show that it may not always be possible to solve dispersion when the directed graph is not strongly connected. We then establish some lower bounds on both time and memory requirements at each robot for solving dispersion on a strongly connected directed graph. Finally, we provide two deterministic algorithms solving dispersion on any strongly connected directed graph. Let D be the graph diameter and Delta(out) be its maximum out-degree. The first algorithm solves dispersion in O(k(2) center dot Delta(out)) time with O(log(k + Delta(out))) bits at each robot. The second algorithm solves dispersion in O(k center dot D) time with O(k center dot log(k + Delta(out))) bits at each robot, provided that robots in the 1-hop neighborhood can communicate. Both algorithms extend to handle crash faults.

关键词： Multi-agent systems Mobile robots Local and 1-hop communication Directed graphs Dispersion time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

Dispersion of Mobile Robots in the Global Communication Model 20

Dispersion of Mobile Robots in the Global Communication Mode...

引用

21st International Conference on Distributed Computing and Networking (ICDCN)

作者： Kshemkalyani, Ajay D. Molla, Anisur Rahaman Sharma, Gokarna Univ Illinois Chicago IL 60607 USA Indian Stat Inst Kolkata 700108 India Kent State Univ Kent OH 44240 USA

ISBN: (纸本)9781450377515

The dispersion problem on graphs asks k <= n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driven electric cars (robots) to recharge stations (nodes). In this paper, we consider dispersion in the global communication model where a robot can communicate with any other robot in the graph (but the graph is unknown to robots). We provide three novel deterministic algorithms, two for arbitrary graphs and one for arbitrary trees, in a synchronous setting where all robots perform their actions in every time step. For arbitrary graphs, our first algorithm is based on a DFS traversal and guarantees O(min(m, k Delta)) steps runtime using circle minus(log(max(k, Delta))) bits at each robot, where m is the number of edges and Lambda is the maximum degree of the graph. The second algorithm for arbitrary graphs is based on a BFS traversal and guarantees O(max(D, k)Delta(D + Delta)) steps runtime using O(max(D, Delta log k)) bits at each robot, where D is the diameter of the graph. The algorithm for arbitrary trees is also based on a BFS travesal and guarantees O(D max(D, k)) steps runtime using O(max(D, Delta log k)) bits at each robot. Our results are significant improvements compared to the existing results established in the local communication model where a robot can communication only with other robots present at the same node.

关键词： Multi-agent systems Mobile robots Dispersion Collective exploration Scattering Uniform deployment Load balancing Distributed algorithms time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

Collaborative dispersion by silent robots

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2024年 188卷

作者： Gorain, Barun Mandal, Partha Sarathi Mondal, Kaushik Pandit, Supantha Indian Inst Technol Bhilai Chhattisgarh India Indian Inst Technol Guwahati Gauhati India Indian Inst Technol Ropar Rupnagar Punjab India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

In the dispersion problem, a set of k co -located mobile robots must relocate themselves in distinct nodes of an unknown network. The network is modeled as an anonymous graph G = (V, E), where the graph's nodes are not labeled. The edges incident to a node v with degree d are labeled with port numbers in the range {0, 1, ..., d -1} at v. The robots have unique IDs in the range [0, L], where L >= k, and are initially placed at a source node s. The task of the dispersion was traditionally achieved based on the assumption of two types of communication abilities: (a) when some robots are at the same node, they can communicate by exchanging messages between them, and (b) any two robots in the network can exchange messages between them. This paper investigates whether this communication ability among co -located robots is absolutely necessary to achieve dispersion. We establish that even in the absence of the ability of communication, the task of the dispersion by a set of mobile robots can be achieved in a much weaker model, where a robot at a node v has access to following very restricted information at the beginning of any round: (1) am I alone at v? (2) did the number of robots at v increase or decrease compared to the previous round? We propose a deterministic distributed algorithm that achieves the dispersion on any given graph G = (V, E) in time O (k log L + k2 log A), where A is the maximum degree of a node in G. Further, each robot uses O(log L + log A) additional memory, i.e., memory other than the memory required to store its id. We also prove that the task of the dispersion cannot be achieved by a set of mobile robots with o(log L + log A) additional memory.

关键词： Mobile robots Anonymous graphs Dispersion Deterministic algorithm time and memory complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：