提出可移动智能体模型,实现高效分布式图计算。
Agentic Distributed Computing
- 将节点视为容器,智能体需移动至同节点才能通信
- 设计新算法解决领头选举与最小生成树问题,优化时间和内存
- 首次研究k≤n场景,适用于资源受限的移动计算系统
传统分布式计算以消息传递模型为主,每个节点为固定计算设备。本文提出新型智能体模型,将计算设备视为可移动的智能体,通信需移动至同一节点。研究在该模型下两个基础图任务:领头选举与最小生成树构建,目标是最小化时间与内存开销。在同步设定下,分别针对k<n和k=n两种情况设计确定性算法,其中k为智能体数,n为节点数。基于领头选举结果,进一步开发最小生成树构建算法,均实现时间与内存复杂度最优。据我们所知,这是首个在k≤n条件下研究分布式图任务的工作,此前研究仅限于k=n情形。
原文摘要 · Abstract (English)
The most celebrated and extensively studied model of distributed computing is the {\em message-passing model,} in which each vertex/node of the (distributed network) graph corresponds to a static computational device that communicates with other devices through passing messages. In this paper, we consider the {\em agentic model} of distributed computing which extends the message-passing model in a new direction. In the agentic model, computational devices are modeled as relocatable or mobile computational devices (called agents in this paper), i.e., each vertex/node of the graph serves as a container for the devices, and hence communicating with another device requires relocating to the same node. We study two fundamental graph level tasks, leader election, and minimum spanning tree, in the agentic model, which will enhance our understanding of distributed computation across paradigms. The objective is to minimize both time and memory complexities. 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. In this paper, we present two deterministic algorithms for leader election: one for the case of $k<n$ and another for the case of $k=n$, minimizing both time and memory complexities, where $k$ and $n$, respectively, are the number of agents and number of nodes of the graph. Using these leader election results, we develop deterministic algorithms for agents to construct a minimum spanning tree of the graph, minimizing both time and memory complexities. To the best of our knowledge, this is the first study of distributed graph level tasks in the agentic model with $k\leq n$. Previous studies only considered the case of $k=n$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。