-------------------------------------------------------------------------------
*******************************************************************************
-------------------------------------------------------------------------------
                                       
                                       
		   B O S T O N   U N I V E R S I T Y
                                       
		      Computer Science Department
                                       
			  C O L L O Q U I U M
                                       
		       Wednesday, April 10, 1996
                                       
				11:00 am
                                       
		      (Coffee served at 10:30 am)

			 Seminar Room / MCS 135

-------------------------------------------------------------------------------
*******************************************************************************
-------------------------------------------------------------------------------
		   Large Markovian Particle Processes
		and Some Applications to Load Balancing

			  Michael Mitzenmacher
		  University of California at Berkeley

   Consider the following dynamic problem: jobs arrive as a Poisson stream
   of rate $\lambda n$, $\lambda < 1$, to a collection of $n$ servers.
   Each job chooses some constant $d$ servers independently and uniformly
   at random from the $n$ servers, and waits for service at the one
   currently containing the fewest jobs (ties are broken arbitrarily).
   Jobs are served using the first-in first-out (FIFO) protocol, and the
   service time for a job is exponentially distributed with mean 1.  We
   wish to know how this system behaves, and in particular we are
   interested in the expected time a job spends in the system.
   
   We provide a novel approach to analyzing such a system, based on
   studying an idealized, infinitely large version of the system and
   showing that the behavior of the finite system is "close" to the
   behavior of the infinite system in a well-defined sense.  This
   methodology proves quite general, and can be used to study the behavior
   of many similar load balancing problems.
   
-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
   For more information contact Prof. Mark Crovella <crovella@bu.edu>
-------------------------------------------------------------------------------