Dynamics of the supermarket model

Details Dynamics of the supermarket model Dynamics of the supermarket model

2010-02-24

arxiv.org/abs/1002.4570v1

Mathematics

Probability

22 pages, O figures

Scientific paper

We consider the long term behaviour of a Markov chain \xi(t) on \Z^N based on the N station supermarket model. Different routing policies for the supermarket model give different Markov chains. We show that for a general class of local routing policies, "join the least weighted queue" (JLW), the N one-dimensional components \xi_i(t) can be partitioned into disjoint clusters C_k. Within each cluster C_k the "speed" of each component \xi_j converges to a constant V_k and under certain conditions \xi is recurrent in shape on each cluster. To establish these results we have assembled methods from two distinct areas of mathematics, semi-martingale techniques used for showing stability of Markov chains together with the theory of optimal flows in networks. As corollaries to our main result we obtain the stability classification of the supermarket model under any JLW policy and can explicitly compute the C_k and V_k for any instance of the model and specific JLW policy.

Affiliated with

Also associated with

No associations

Rating

Dynamics of the supermarket model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamics of the supermarket model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamics of the supermarket model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-260913