Anisur Rahaman Molla

Abhijit Sadhukhan, Adri Bhattacharya, Anisur Rahaman Molla

We study the message complexity of leader election in synchronous networks of diameter two. Our main contribution is a refined analysis of the randomized algorithm proposed by Chatterjee et al. [DC, 2020]. In their work, the authors established a lower bound of $Ω(n)$ messages ($n$ is the number of nodes in the network) and presented a randomized algorithm that elects a leader in ${O}(1)$ rounds using $O(n \log^3 n)$ messages with high probability. In this paper, we improve their $\polylog n$ gap in the message bound by providing a tighter analysis of their algorithm, reducing the message complexity to $O(n\log n)$, while preserving the $O(1)$-round complexity and high-probability correctness guarantee.

Ashish Saxena, Anisur Rahaman Molla, Kaushik Mondal et al.

We study the fundamental problem of graph exploration in dynamic graphs using mobile agents. We consider $1$-interval connected dynamic graphs, where the topology may change arbitrarily from round to round as long as the graph remains connected, and edges are assigned with the dynamic port labeling at each round. The execution follows a semi-synchronous scheduler, under which an adversary may deactivate an arbitrary subset of agents in each round. For a graph with $n$ nodes and $k$ agents, we show that exploration is impossible if the adversary can deactivate at least $ \left\lceil \frac{k}{n-2} \right\rceil - 1$ agents per round, even when agents are equipped with unbounded memory, have global communication and full visibility. This yields an upper bound, implying that exploration is solvable only when the adversary deactivates at most $\left\lceil \frac{k}{n-2} \right\rceil - 2$ agents per round. We further establish that achieving exploration at this threshold requires agents to have both $1$-hop visibility and $1$-hop communication. Finally, we present the exploration algorithm using $k$ agents when the adversary deactivates at most $ \left\lceil \frac{k}{n-2} \right\rceil - 2$ agents, assuming agents are equipped with $1$-hop visibility and global communication, and matches the adversarial deactivation bound implied by the impossibility results.

Ajay D. Kshemkalyani, Anisur Rahaman Molla, Gokarna Sharma

The dispersion problem on graphs asks $k\leq 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 etc. In this paper, we consider dispersion in the {\em 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Δ))$ steps runtime using $Θ(\log (\max(k,Δ)))$ bits at each robot, where $m$ is the number of edges and $Δ$ 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) Δ(D+Δ))$ steps runtime using $O(\max(D,Δ\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,Δ\log k))$ bits at each robot. Our results are significant improvements compared to the existing results established in the {\em local communication} model where a robot can communication only with other robots present at the same node. Particularly, the DFS-based algorithm is optimal for both memory and time in constant-degree arbitrary graphs. The BFS-based algorithm for arbitrary trees is optimal with respect to runtime when $k\leq O(D)$.