CAREER: Dynamic Processes and Network Algorithms

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

AbstractPI: Michael MitzenmacherProposal Number: 9983832Institution: Harvard UniversityThis research addresses several problems in the intersection of networks and random processes, including the design of erasure and error-correcting codes based on random graphs, the analysis of dynamic load balancing schemes, and the development of new algorithmic approaches for studying the size and structure of the World Wide Web. These problems, besides all relating to the design and analysis of networks, share a common framework: they can be embedded into models of dynamic random processes. As such, they often can be attacked using theoretical techniques such as fluid limit models and Lyapunov analysis. A major goal of this research is to develop the proper framework for using, improving, and simplifying these techniques, so that they may be applied more easily in these and other areas.Another major goal of the proposed research is to connect theory and practice. For example, the research on codes is being applied to the problem of reliable multicast. The models for load balancing in the face of delay are being applied to systems of Web servers. As part of the effort to bridge theoretical work and practical problems in modern networks, the PI is planning a new graduate course that covers issues in information retrieval, codes, cryptography, and compression.