Information and memory in dynamic resource allocation
From MaRDI portal
Abstract: We propose a general framework, dubbed Stochastic Processing under Imperfect Information (SPII), to study the impact of information constraints and memories on dynamic resource allocation. The framework involves a Stochastic Processing Network (SPN) scheduling problem in which the scheduler may access the system state only through a noisy channel, and resource allocation decisions must be carried out through the interaction between an encoding policy (who observes the state) and allocation policy (who chooses the allocation). Applications in the management of large-scale data centers and human-in-the-loop service systems are among our chief motivations. We quantify the degree to which information constraints reduce the size of the capacity region in general SPNs, and how such reduction depends on the amount of memories available to the encoding and allocation policies. Using a novel metric, capacity factor, our main theorem characterizes the reduction in capacity region (under "optimal" policies) for all non-degenerate channels, and across almost all combinations of memory sizes. Notably, the theorem demonstrates, in substantial generality, that (1) the presence of a noisy channel always reduces capacity, (2) more memory for the allocation policy always improves capacity, and (3) more memory for the encoding policy has little to no effect on capacity. Finally, all of our positive (achievability) results are established through constructive, implementable policies.
Recommendations
- Maximum Pressure Policies in Stochastic Processing Networks
- Stochastic knapsack revisited: the service level perspective
- Resource Allocation Under Uncertainty Using the Maximum Entropy Principle
- Optimal resource capacity management for stochastic networks
- On the capacity of information processing systems
Cites work
- A Stochastic Analysis of Queues with Customer Choice and Delayed Information
- Bandwidth sharing and admission control for elastic traffic
- Blind fair routing in large-scale service systems with heterogeneous customers and servers
- Brownian models of open processing networks: Canonical representation of workload.
- Control Under Communication Constraints
- Correction: Brownian models of open processing networks: canonical representation of workload
- Delay, memory, and messaging tradeoffs in distributed service systems
- scientific article; zbMATH DE number 1936531 (Why is no real title available?)
- Maximum Pressure Policies in Stochastic Processing Networks
- MaxWeight scheduling in a generalized switch: State space collapse and workload minimization in heavy traffic
- Necessity of future information in admission control
- On the power of (even a little) resource pooling
- Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers
- Pull-based load distribution in large-scale heterogeneous service systems
- Queueing system with selection of the shortest of two queues: An asymptotic approach
- Queuing with future information
- Random processes for engineers
- Robust scheduling for flexible processing networks
- Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
- Stability analysis of parallel server systems under longest queue first
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
- Stochastic networked control systems. Stabilization and optimization under information constraints
- Sufficient conditions for stability of longest-queue-first scheduling: second-order properties using fluid limits
- Switched networks with maximum weight policies: fluid approximation and multiplicative state space collapse
- The Necessity and Sufficiency of Anytime Capacity for Stabilization of a Linear System Over a Noisy Communication Link—Part I: Scalar Systems
- Tightness of invariant distributions of a large-scale flexible service system under a priority discipline
Cited in
(6)- Item and associative information in a distributed memory model
- Information processing for a finite resource allocation mechanism
- Balanced routing with partial information in a distributed parallel many-server queueing system
- On the capacity of information processing systems
- scientific article; zbMATH DE number 7453151 (Why is no real title available?)
- Choice-memory tradeoff in allocations
This page was built for publication: Information and memory in dynamic resource allocation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144790)
