Design and Analysis of Dynamic Processes: A Stochastic Approach

这个项目研究动态计算机过程的设计和分析。 过去在理论计算机科学中的研究主要集中在静态计算问题上，其中输入在计算开始之前是已知的，目标是最小化直到终止的步骤数并获得正确的输出。 当今计算中的许多重要过程都是动态过程，输入不断注入系统，算法通过其长期稳定状态的性能来衡量。 动态进程的例子包括通信协议、内存管理工具和分时策略。 本课题的主要目标是：（1）开发新的动态过程性能分析工具，特别是将动态过程建模为无限随机过程。 (2)使用从上述分析中获得的洞察力来获得基本动态过程的可证明的更好算法，例如（a）动态数据结构，（B）通信协议和（c）资源共享协议。 (3)通过模拟分析，以开发具有实际和理论意义的算法。

This project studies the design and analysis of dynamic computer processes. Past research in theoretical computer science has focused mainly on static computation problems, where the input is known before the start of the computation and the goal is to minimize the number of steps till termination with a correct output. Many important processes in today's computing are dynamic processes, whereby input is continuously injected to the system, and the algorithms is measured by its long term, steady state, performance. Examples of dynamic processes include communication protocols, memory management tools, and time sharing policies. The goal of this project are: (1) To develop new tools for analyzing the performance of dynamic processes, in particular through modeling the dynamic process as an infinite stochastic processes. (2) Use the insight obtained from the above analysis to obtain provably better algorithm for fundamental dynamic processes such as (a) dynamic data structures, (b) communication protocols, and (c) resource sharing protocols. (3) Validate the analysis though simulations to develop algorithms of both practical and theoretical interest.