[Brown CS Talks] Brown CS Thesis Defense: Gopal Pandurangan in Lubrano on 4/12/02 at 2:30 pm

[talks-admin@list.cs.brown.edu]

		  The Department of Computer Science
			   BROWN UNIVERSITY

			      
			       presents

			  Gopal Pandurangan

			    Thesis Defense

				 
		  Friday, April 12, 2002 at 2:30 pm

	       Lubrano Conference Room (CIT 4th floor)
			       

	  Stochastic Analyses of Dynamic Computer Processes


			       Abstract

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

In this thesis, we present four results in different settings in which
stochastic processes serve as natural models for dynamic computer
phenomena that arise in practical applications. The models are useful
not only in understanding these phenomena but also in designing and
analyzing practical algorithms/schemes for the associated algorithmic
problems.

The results are: (1) Evaluating Quality-of-Service (QoS) parameters
in a statistically multiplexed communication network fed by bursty
traffic (modeled as a stochastic source); (2) Online computation
under a general stochastic model, where we characterize online
performance using entropy as a measure; (3) Design and analysis
(under a stochastic model) of a novel distributed protocol to build
Peer-to-Peer (P2P) networks with good topological properties; and 
(4) Developing new stochastic models for the Web graph which capture
the PageRank distribution, a global property used to rank Web pages.

In this talk, I will first focus on our third result where we address
the fundamental problem of building P2P networks with good topological
properties. We present a practical 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.  To our knowledge this is the first P2P
protocol with provable guarantees on connectivity and diameter under a
realistic dynamic setting.
   
In the second part of my talk, I will focus on our fourth result where
we develop and analyze new models for the Web graph which capture a
global property of the Web: the {PageRank} distribution.  We study
the distribution of PageRank values (used in the Google search engine)
on the Web.  We show that PageRank values on the Web follow a power
law.  We then develop detailed models for the Web graph that explain
this observation, and moreover remain faithful to previously studied
degree distributions (a ``local'' property of the Web).  We analyze
these models, and compare the analysis to both snapshots from the Web
and to graphs generated by simulations on the new models.  To our
knowledge this represents the first modeling of the Web that goes
beyond fitting degree distributions on the Web.


		      Host:  Professor Eli Upfal