Efficient Algorithms for Problems in the Next Generation of Computing

Columbia University, New York NY

Investigators

Abstract

Efficient Algorithms for Problems in the Next Generation of Computing Cliff Stein Columbia University Computers, computer systems and the computational infrastructure provided by the Internet are now essential for many aspects of modern life. It is well-known and well-documented that, even as computing power and network bandwidth increase at a rapid rate, the demands that users and applications place on these resource increase at roughly the same pace. Thus, no matter how much progress we make on the hardware and network ends, we will always need efficient algorithms to manage these resources. This research focuses on several algorithmic problems in computer systems and networks; arising both from existing technologies and at technologies that are evolving, or have been proposed. By improve the efficiency with which we manage our devices and infrastructure, there will be tremendous savings, both in time and economically. In addition, the investigator integrates theory and systems and encourages more collaboration between these areas, with obvious benefits. This work has an impact on the decisions that are being made presently about the next generation of the Internet, of routing, and of scheduling in operating systems. In particular, the investigator studies four concrete problem areas: scheduling in operating systems -- finding schedules that are low overhead and use resources fairly; scheduling in the next generation of routers -- designing algorithms that allow packets with different levels of service to be routed efficiently; network coding -- designing algorithms to manage this exciting new routing technology, and power management -- designing algorithms that schedule jobs to provide good response time and to use power efficiently. While the details of these various areas differ, the overall goals are to design simple, low overhead algorithms, use algorithms with rigorously proved bounds and analysis, design new theory and transfer existing theory closer to the systems. The investigator also designs educational materials suitable for teaching algorithms to a wider audience.