Design and Analysis of Dynamic Processes: A Stochastic Approach

动态过程的设计和分析：随机方法

• 批准号: 9731477
• 负责人: Eli Upfal
• 金额: $ 28.63万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-15 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9731477&HistoricalAwards=false
• 关键词: Design; Analysis; Dynamic; Processes; Stochastic

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.

该项目研究动态计算机流程的设计和分析。 过去的理论计算机科学研究主要集中在静态计算问题上，在计算开始之前，该输入是已知的，目标是最大程度地减少以正确输出为止终止的步骤数量。 当今计算中的许多重要过程都是动态过程，将输入连续注入系统，并且该算法是通过其长期，稳态和性能来衡量的。 动态过程的示例包括通信协议，内存管理工具和时间共享策略。 该项目的目的是：（1）开发用于分析动态过程性能的新工具，特别是通过将动态过程建模为无限随机过程。 （2）使用从上述分析获得的见解，以获取基本动态过程（例如（a）动态数据结构，（b）通信协议和（c）资源共享协议等基本动态过程的更好的算法。 （3）验证分析的模拟，以开发实用和理论兴趣的算法。