Efficient Algorithms for Problems in the Next Generation of Computing

点击翻译按钮获取中文摘要

Efficient Algorithms for Problems in the Next Generation of ComputingCliff SteinColumbia UniversityComputers, computer systems and the computational infrastructureprovided by the Internet are now essential for many aspects of modernlife. It is well-known and well-documented that, even as computingpower and network bandwidth increase at a rapid rate, the demands thatusers and applications place on these resource increase at roughly thesame pace. Thus, no matter how much progress we make on the hardwareand network ends, we will always need efficient algorithms to managethese resources. This research focuses on several algorithmicproblems in computer systems and networks; arising both from existingtechnologies and at technologies that are evolving, or have beenproposed. By improve the efficiency with which we manage our devicesand infrastructure, there will be tremendous savings, both in time andeconomically. In addition, the investigator integrates theory andsystems and encourages more collaboration between these areas, withobvious benefits. This work has an impact on the decisions that arebeing made presently about the next generation of the Internet, ofrouting, 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 algorithmsthat allow packets with different levels of service to be routedefficiently; network coding -- designing algorithms to manage thisexciting new routing technology, and power management -- designingalgorithms that schedule jobs to provide good response time and to usepower efficiently. While the details of these various areas differ,the overall goals are to design simple, low overhead algorithms, usealgorithms with rigorously proved bounds and analysis, design newtheory and transfer existing theory closer to the systems. Theinvestigator also designs educational materials suitable for teachingalgorithms to a wider audience.