[Colloq] **Hiring Talk** Monday March 4, 11am 149CN

[Rachel Bates]

Gopal Pandurangan
who will speak on:
Stochastic Analysis of Dynamic Computer Processes

Monday, March 4, 2002
11:00 am
149 Cullinane Hall
Northeastern University


ABSTRACT

Stochastic processes can model a variety of dynamic computer phenomena
such as growth of the World Wide Web, traffic in communication networks,
structure of dynamic networks, and input for caching and load balancing.
Stochastic analysis enables us to characterize properties of such
processes that dynamically change with time.

In this talk, I will present two results in different settings in which
stochastic processes serve as natural models for dynamic computer phenomena.
The models are useful not only in understanding these phenomena
but also in designing practical algorithms/schemes for the associated
algorithmic problems.

The two results are:

(1) Stochastic Analysis of Peer-to-Peer (P2P) Networks : I will first
motivate
    the problem of building connected low-diameter P2P networks. Then I will
    present a simple distributed protocol for building P2P networks and
    prove (under a reasonable stochastic model) that it results in connected
    networks of constant degree and logarithmic diameter. An important
    feature of our protocol is that it operates without any global knowledge
    of all the nodes in the network. To our knowledge, this is the first
such
    protocol with provable guarantees on connectivity and diameter.

(2) Stochastic Analysis of Online Computation:  In the second part of
    the talk, I will discuss a novel way of measuring online performance
    based on the characteristics of the input sequence; this is
    fundamentally different from the traditional competitive analysis of
    online computation. Assuming a very general stochastic model for the
    input sequence, I will present bounds between entropy of the input
    and the performance of the best online algorithm for various online
    problems. In particular, I will present a simple online algorithm for
    prefetching and show that it performs well on any input sequence.
    I will also mention a few practical applications of our approach.
Host:
Rajmohan Rajaraman

Rachel Bates
Administrative Secretary
College of Computer Science
rachelb@ccs.neu.edu
X2462