Areas of Research

Why Distributed Algorithms?

Distributed algorithms are crucial for building scalable, robust, and efficient systems. They allow us to:

• Scale systems by adding or removing components without downtime.
• Ensure robustness against failures, making systems resilient.
• Leverage parallelism to speed up computations.
• Operate in an asynchronous manner, allowing components to work independently.

Popular Problems in Distributed Computing

Some of the popular problems that provides a taste of what research in distributed algorithms entails include:

• Leader Election: How can a group of robots elect a leader to coordinate tasks?
• Rendezvous Problem: Two robots must meet at a common point in an unknown environment.
• Treasure Hunt: Robots search for a treasure in a grid, learning to coordinate their movements.
• Pattern Formation: Robots arrange themselves in specific geometric shapes.

Look-Compute-Move Model

The Look-Compute-Move (LCM) model is a foundational framework in distributed computing. It describes how agents can:

• Look: Observe their environment and gather information.
• Compute: Process the information to make decisions.
• Move: Act based on their computations to achieve goals.

This model is essential for understanding how simple agents can work together to solve complex problems.

Dispersion Problem

• Goal: Scatter k mobile robots on an n-node graph to ensure each robot occupies a unique node.
• Challenges: Robots are anonymous, operate with limited memory, and in synchronous or asynchronous settings. The graph can be directed or undirected. Faulty (Byzantine) robots can disrupt the process.
• Key Research: Designing time and memory-optimal algorithms. Investigating trade-offs between synchrony, memory, and time. Handling Byzantine faults and directed graphs.
• Recent Results: We have developed optimal time algorithms for dispersion in both synchronous and asynchronous models, and provided solutions for directed graphs and environments with faulty robots.

Circle Formation Problem

• Goal: Arrange n autonomous mobile robots, initially in the plane, to be equally spaced on the circumference of a circle.
• Challenges: Robots are anonymous, asynchronous, and oblivious (no memory). The circle's center and radius are not predefined.
• Key Research: Achieving faster runtime using minimal capabilities like "luminous" robots (with colored lights). Analyzing time-color trade-offs.
• Recent Results: We have developed an optimal algorithm in terms of the number of colors required, and have established key trade-offs between time and the number of colors.

Black Hole Search Problem

• Goal: Locate a "black hole" (a harmful node that destroys incoming agents) in a network.
• Challenges: Some of the searching agents can be Byzantine (malicious) and collude with the black hole. Agents may or may not have a map of the network.
• Key Research: Determining the minimum number of agents required to find the black hole safely. Analyzing the impact of prior knowledge (maps) and communication models (e.g., whiteboards vs. local communication).
• Recent Results: We have established the number of agents needed and the time complexity for solving the problem under various conditions, including the presence of Byzantine agents.

Black Hole Search Simulator

Explore the Black Hole Search Problem with this interactive simulator. Adjust parameters and see how agents search for the black hole.

Collaborator Network

Research is a global endeavor. This map showcases my network of co-authors from institutions around the world.

Mobile Robot Simulators

Explore some of the concepts we study with these interactive simulators for different mobile robot models.