# Agentic Distributed Computing

arXiv: https://arxiv.org/abs/2507.04459 · HTML: https://mlsanity.com/paper/2507.04459/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 6 Jul 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 6 of 6)

- [On the Distributed Complexity of Large-Scale Graph Computations](https://mlsanity.com/paper/1602.08481/) (2016)
- [Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs](https://mlsanity.com/paper/1707.05629/) (2017)
- [Run for Cover: Dominating Set via Mobile Agents](https://mlsanity.com/paper/2309.02200/) (2023)
- [Agent-based Leader Election, MST, and Beyond](https://mlsanity.com/paper/2403.13716/) (2024)
- [Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots](https://mlsanity.com/paper/2305.01753/) (2023)
- [Dispersion is (Almost) Optimal under (A)synchrony](https://mlsanity.com/paper/2503.16216/) (2025)

## Abstract (arXiv)

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≤ n. Previous studies only considered the case of k=n.