Research Project on Design and Analysis of Dynamic Processes:
A Stochastic Approach
# Research Project on:

The Design and Analysis of Dynamic Processes:

A Stochastic Approach

### Goal

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 algorithm
is measured by its long term, steady state, performance. Examples of dynamic
processes include communication protocols, memory management tools,
and time sharing policies.
The goals 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 algorithms 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.

### People

###
Publications

G. Pandurangan, P.Raghavan and E. Upfal.
Building Low-diameter Peer-to-Peer Networks,
*
Proceedings of the 42nd Annual IEEE Symposium on
the Foundations of Computer Science (FOCS)*,
Las Vegas, 2001.
postscript, pdf

G. Pandurangan and E.Upfal.
Can Entropy Characterize Performance of Online Algorithms?,
* Proceedings of the 12th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA) *, Washington D.C, 2001,
postscript, pdf

G. Pandurangan and E. Upfal.
Static and Dynamic Evaluation of QoS Properties.
*
Proceedings of the 31st ACM Symp. on Theory of Computing.*
1999, Atlanta, Georgia, pp. 566-573.
(postscript
version)

M. L. Luczak and E. Upfal.
Reducing Network Congestion and Blocking Probability Through
Balanced Allocation.
*
Proceedings of the 40th IEEE Symp. on Foundations of Computer Science.*
1999, New York, NY, pp 587-595.
(postscript
version)

This work is supported by an NSF grant.