Research Projects

Distributed networks form the backbone of many modern systems, such as peer-to-peer platforms, wireless ad hoc networks, social and cryptocurrency infrastructures, and biological systems like the human brain. In an AI-driven era, autonomous agents must compute global properties using only local information, often in the absence of centralized control. These environments are susceptible to faults—both benign (crash) and adversarial (Byzantine)—making fault tolerance a core challenge in distributed computing. Agent-based models are ideal for such settings, with applications in military networks, underwater communication, disaster-response swarms, and sensor deployments. Ensuring correctness and resilience in such systems requires secure, scalable, and memory-efficient algorithms that tolerate faults and work under minimal assumptions. Rationale and Objectives This project aims to develop fault-tolerant distributed protocols for testing key graph properties—connectivity, degree boundedness, acyclicity, and bipartiteness—under crash and Byzantine faults. These properties are foundational in theory and essential for real-world system robustness. The scientific goals are: 1. To design distributed algorithms that tolerate faults while using only local interactions. 2. To analyze these protocols in terms of correctness, time complexity, and space usage under the LOCAL model. 3. To ensure practical deployability in resource-constrained, adversarial environments. Hypothesis and Model The core hypothesis is that deterministic algorithms can solve these problems efficiently in anonymous, bounded-memory systems. The LOCAL model assumes synchronous rounds, local communication via adjacent edges by reaching at the same location, and agents with at least Ω(log n) bits of memory, placed arbitrarily. We will use neighbor-meeting strategies, agent oscillation, and explore Universal Exploration Sequences (UXS) selectively. Methodology Each problem will be addressed theoretically and supported, where feasible, by simulations. We begin with deterministic protocols in fault-free settings and gradually incorporate fault-tolerant and randomized techniques. Research phases include: 1. Problem Formalization 2. Algorithm Design 3. Formal Analysis 4. Empirical Evaluation 5. Documentation and Dissemination Significance This work addresses a major research gap by offering the first systematic study of fault-tolerant graph protocols in the LOCAL model. Anticipated outcomes include novel algorithms with formal guarantees, scalable implementations for agent systems, and publications in top conferences. The project will enhance foundational tools in distributed computing and strengthen India’s research presence globally.