We study Nordhaus–Gaddum problems for Kemeny’s constant K ( G ) of a connected graph G . We prove bounds on min { K ( G ) , K ( G ¯ ) } and the product K ( G ) K ( G ¯ ) for various families of graphs. In particular, we show that if the maximum degree of a graph G on n vertices is n − O ( 1 ) or n − Ω ( n ) , then min { K ( G ) , K ( G ¯ ) } is at most O ( n ) .

This paper develops a new technique for bounding the mixing rate of a Markov chain by decomposing the state space into factors. The first application is an efficient Monte Carlo Markov chain algorithm for generating random three-colorings of 2-dimensional lattice regions. This provides a rigorous tool for studying some properties of the 3-state Potts model and the ice model from statistical mechanics. As a second application, we develop similar techniques to bound the mixing rate of a Metropolis sampling algorithm by a type of "temperature factorization". Both factorization theorems work by using known mixing properties of related Markov chains to establish the efficiency of a new sampling algorithm.

Abstract. Fair Queuing is a novel queuing discipline with important applications to data networks that support variable-size packets and to systems where the cost of preempting jobs from service is high. The disciphne controls a single server shared by N job arrival streams with each stream allotted a separate queue. After every job completion, the server is assigned to serve, without possibihty of interruption, the job at the head of one of the queues (as soon as at least one job appears in the system). Fair Queuing is designed to handle arbitrary job arrival sequences with essentially no a priori knowledge of their attributes. such that each stream receives its ‘Lfam share ” of serwce. In this paper, we consider two variants of the fair queuing discipline, and rigorously establish their fairness wa sample path comparisons with the head-of-line processor sharing disclphne, a mathematical idealization that prowdes a fairness paradigm. An efficient Implementation of one of the fair queuing disciplines is presented, In passing, a new, fast method for simulating processor sharing is derived. Simulation results are presented to further explore the comparison between fair queuing and processor sharing.

Binary exponential backoff is a randomized protocol for regulating transmissions on a multiple-access broadcast channel. Ethernet, a local-area network, is built upon this protocol. The fundamental theoretical issue is stability: Does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough? It is assumedn≥ 2 stations share the channel, each having an infinite buffer where packets accumulate while the station attempts to transmit the first from the buffer. Here, it is established that binary exponential backoff is stable if the sum of the arrival rates is sufficiently small. Detailed results are obtained on which rates lead to stability whenn= 2 stations share the channel. In passing, several other results are derived bearing on the efficiency of the conflict resolution process. Simulation results are reported that, in particular, indicate alternative retransmission protocols can significantly improve performance.

We consider the stochastic behavior of binary exponential backoff, a probabilistic algorithm for regulating transmissions on a multiple access channel. Ethernet, a local area network, is built upon this algorithm. The fundamental theoretical issue is stability: does the backlog of packets awaiting transmission remain bounded in time, provided the rates of new packet arrivals are small enough?