Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T08:39:05.115Z Has data issue: false hasContentIssue false

Space filling and depletion

Published online by Cambridge University Press:  14 July 2016

Yuliy Baryshnikov*
Affiliation:
Bell Laboratories
E. G. Coffman Jr*
Affiliation:
Columbia University
Predrag Jelenković*
Affiliation:
Columbia University
*
∗ Postal address: Bell Laboratories, 2C-261, 600 Mountain Avenue, Murray Hill, NJ 07974, USA
∗∗ Postal address: Department of Electrical Engineering, Columbia University, 1312 Seeley W. Mudd, Mail Code 4712, 500 West 120th Street, New York, NY 10027, USA
∗∗ Postal address: Department of Electrical Engineering, Columbia University, 1312 Seeley W. Mudd, Mail Code 4712, 500 West 120th Street, New York, NY 10027, USA

Abstract

For a given k ≥ 1, subintervals of a given interval [0, X] arrive at random and are accepted (allocated) so long as they overlap fewer than k subintervals already accepted. Subintervals not accepted are cleared, while accepted subintervals remain allocated for random retention times before they are released and made available to subsequent arrivals. Thus, the system operates as a generalized many-server queue under a loss protocol. We study a discretized version of this model that appears in reference theories for a number of applications, including communication networks, surface adsorption-desorption processes, and reservation systems. Our primary interest is in steady-state estimates of the vacant space, i.e. the total length of available subintervals kX - ∑ℓi , where the ℓi are the lengths of the subintervals currently allocated. We obtain explicit results for k = 1 and for general k with all subinterval lengths equal to 2, the classical dimer case of chemical applications. Our focus is on the asymptotic regime of large retention times.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2004 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable