Lower Bounds for Distributed Computing (09w5114)
Description
The Banff International Research Station will host the “Lower Bounds for Distributed Computing” workshop next week, January 25 - January 30, 2009.
Distributed computing is an important area of computer science that studies processors which can run concurrently and can communicate with one another. Work needs to be done, despite component failures. Examples include telephone networks, banking systems, airline reservation systems, and the internet. It is well known that many distributed problems cannot be solved, because each processor has limited information. Among those problems that can be solved, there are many for which no efficient solutions are known.
This workshop focuses on mathematically proving that certain distributed computing problems cannot be solved efficiently. Such results are important because they tell us when to stop looking for better ways of solving those problems. They also help us understand the problems much better. Sometimes this can lead to a new, unexpected solution for a problem. It can also help us to carry on, despite bad news, for example, by identifying new features that could
be added to the hardware, or finding ways to change the problem slightly, so that it becomes much easier to solve.
Distributed computing is an important area of computer science that studies processors which can run concurrently and can communicate with one another. Work needs to be done, despite component failures. Examples include telephone networks, banking systems, airline reservation systems, and the internet. It is well known that many distributed problems cannot be solved, because each processor has limited information. Among those problems that can be solved, there are many for which no efficient solutions are known.
This workshop focuses on mathematically proving that certain distributed computing problems cannot be solved efficiently. Such results are important because they tell us when to stop looking for better ways of solving those problems. They also help us understand the problems much better. Sometimes this can lead to a new, unexpected solution for a problem. It can also help us to carry on, despite bad news, for example, by identifying new features that could
be added to the hardware, or finding ways to change the problem slightly, so that it becomes much easier to solve.
The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).
