Near-Linear Time Leader Election in Multiagent Networks

Title of the Talk: Near-Linear Time Leader Election in Multiagent Networks
Speakers: Manish Kumar
Host Faculty: Prof.Sathya Peri
Date: Dec 29, 2025
Time: 02:30 pm.
Venue: CS-105

Abstract: 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. We study leader election in the agent-based 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 n agents are arbitrarily placed on the nodes of an anonymous, arbitrary n-node, m-edge graph G. 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 the 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. Prior work appeared in [DISC’24] provides a deterministic solution that completes leader election in O(m) rounds, requiring O(n log n) bits of memory per agent.

We present a deterministic algorithm that significantly improves the memory requirement, using only O(log n) bits per agent, while achieving a near-linear time complexity of O(n log2 n) rounds. Furthermore, we show how this leader election result enables more efficient solutions to several key problems in agent-based distributed computing: minimum spanning tree construction, agent gathering, maximal independent set, and minimal dominating set.

Speaker’s Bio: Manish Kumar is a Postdoctoral Researcher under the ANRF–National Post Doctoral Fellowship (N-PDF) scheme at IIT Madras, affiliated with the DisTrA Lab, where he works with Prof. John Augustine. His research focuses on the design and analysis of efficient distributed algorithms, particularly in agent-based and message-passing models. The research interests include problems such as dispersion, leader election, agreement, and data download, with an emphasis on analyzing their complexity in terms of rounds, memory, and message complexity. He earned his PhD in Message-Efficient Fault-Tolerant Distributed Computations in 2023 from the Indian Statistical Institute, Kolkata, under the supervision of Dr.Anisur Rahaman Molla. Manish’s research has been published in leading conferences and journals, including AAMAS, PODC, DISC, SPAA, TPDS, and TCS.