Stanford Research Communication Program
  Home   Researchers Professionals  About
Archive by Major Area


Social Science

Natural Science

Archive by Year

Fall 1999 - Spring 2000

Fall 2000 - Summer 2001

Fall 2001 - Spring 2002

Fall 2002 - Summer 2003




I-RITE Statement Archive
About I-RITE

Socializing in a Networked World: Asynchronous Distributed Algorithms

Lin Xiao
Department of Aeronautics and Astronautics
Stanford University
March 2002

My research is to develop optimization algorithms and control laws for large-scale networked systems. In particular, I am interested in asynchronous distributed algorithms, which are implemented by individual components of the network, when there is no central controller.

Our lives interact more and more with a wide variety of networks in the area of transportation, communication, energy and finance. For example, the air traffic control system, the Internet, the electric power system and the global economic system. These modern networked systems consist of millions of interacting components and are inherently very complex. It is of great interest to optimize and control these networked systems for them to operate efficiently and obtain desired overall performance.

Traditional algorithms for optimization and control of engineering systems are implemented by a central controller. The central controller collects global information about the system and makes overall decision, and the components of the system follow the central controller's command and act synchronously to carry out their specified tasks. This type of algorithms and control laws are very successful for systems as large as launching a space shuttle and operation of a satellite. But they are inadequate for modern large-scale networked systems mentioned above. The very large scale and great complexity of these networks makes it very difficult, if not impossible, to have a central controller that knows everything happening in the whole network and commands every single components.

My research is to analyze and design asynchronous distributed algorithms --- control laws implemented by individual components without a central controller. These algorithms are based only on limited local information, often performed out of step with each other, yet achieving a similar overall performance as if everything are planed altogether.

Most asynchronous distributed algorithms are deduced from traditional centralized ones. By exploiting the special structures of the network of interest, the optimization or control problem usually can be decomposed into many weakly coupled sub-problems. Each sub-problem only involves a small group of closely related components. These sub-problems can be solved locally within the small groups, based on local information. Sometimes, some critical global information needs to be broadcasted globally to coordinate the solutions to local sub-problems. The key question to be answered in developing asynchronous distributed algorithms is: who should know what, when and where? In other words, how should individuals socialize in a networked world.

One excellent example is routing on the Internet, where millions of computers are connected via wires made of copper or optical fiber. When you send an email to your friend, your message is grouped into data packets, sent to the destination along a certain route --- a series of computers. There may be millions of possible routes to reach your friend. How would you plan a safe trip for your message? This sounds like a ``Mission Impossible'' since you even don't know how the whole Internet is connected! In fact, no one can plan the whole routing process alone. The Internet is too large and complex for any central controller to work successfully.

Routing on the Internet is done in a distributed way: each computer on the route only needs to figure out where the message should go next, based on its own knowledge of the network, which is partial and might be inaccurate. The computers exchange information about the Internet regularly with their neighbors, to learn what the neighbors think and if there are new changes around. Typically they don't care what happens far away. If a computer knows that certain frequently used links are congested, it might send the message to a neighbor which seems be able to find a better route. The destination will send back an acknowledgment whenever it receives a data packet. The computers also have a set of rules to determine if the message has arrived safely, and resend it if it is lost. The above rules, or communication protocols, used by computers over the Internet to transmit data packets, are examples of asynchronous distributed algorithms.

I have been working on data routing and resource allocation for wireless communication networks --- ``wireless Internet''. This problem is even more complicated than the Internet routing problem. For wired networks like the Internet, each wire has a fixed capacity, the maximum information it can carry in unit time. In wireless networks, information is sent through wireless channels --- the air among the radio stations. A wireless channel occupies some signal bandwidth and consumes certain amount of electrical power. The capacity of a wireless channel is determined by the amount of communication resources allocated to it, such as the signal bandwidth and transmitter power. These communication resources are themselves limited by a total amount at a local radio station or within the whole network. Adjusting the resource allocation changes the channel capacities and influences the optimal data routing in wireless networks.

In my research, I design asynchronous distributed algorithms, which can be implemented by individual radio stations to simultaneously allocate communication resources and find optimal routes to transmit data packets. The goal is to send more information more efficiently by applying these algorithms in future wireless networks.