Near-Linear Time Leader Election in Multiagent Networks

Leader election is a fundamental and widely studied problem in distributed computing, traditionally explored in the message-passing model, where each node in a distributed network graph represents a static computational device that communicates with others by exchanging messages. This paper studies leader election in the agentbased network, in which the computational devices are modeled as relocatable or mobile agents that explore a graph and perform computations. Each node in the graph serves as a container or host for these mobile agents, and communication occurs between agents when they move to the same node. We consider the scenario where 𝑛 agents are arbitrarily placed on the nodes of an anonymous, arbitrary 𝑛-node, 𝑚-edge graph 𝐺. The goal is for the agents to elect a leader such that one agent is designated as the leader, knowing it is the leader, while all other agents recognize they are not the leader. The objective is to minimize the time to elect the leader and memory usage per agent. Following the literature, we consider the synchronous setting where each agent performs its operations synchronously with others and hence the time complexity is measured in rounds. There exists a deterministic solution that elects a leader in 𝑂 (𝑚) rounds with 𝑂 (𝑛 log 𝑛) bits of memory at each agent in the agent-based network. In this paper, we present a deterministic algorithm that elects a leader in 𝑂 (𝑛 log 2 𝑛) rounds with each agent using only 𝑂 (log 𝑛) bits. This is a significant improvement, as the memory usage is optimal and the time complexity is almost linear in 𝑛 (up to 𝑂 (log 2 𝑛) factor). Additionally, leveraging this leader election result, we provide improved time and/or memory bounds for four core distributed graph problems: minimum spanning tree, gathering, maximal independent set, and minimal dominating set.