Search for: All records

In recent decades, cloud computing as a service has emerged as a major computing paradigm. These services (e.g., Amazon EC2, Google Compute Engine, Azure Virtual Machines) all offer variations of the following basic model for how storage works: a compute instance can choose between placing data on something that resembles a local disk (e.g., Amazon EBS, Google Block Store, Azure Managed Disks) versus what we will refer to as a global disk (e.g., Amazon S3, Google GCS, Azure Blob Storage). The disks are distinguished by two features:(1) Bandwidth: Whereas the local disk has a fixed limited bandwidth, the global disk offers essentially unlimited bandwidth.(2) Cost: The local disk supports I/Os for free, while the global disk charges money each time an object is read or written.This storage model suggests a natural algorithmic problem: How should a system manage its storage across local and global disk in order to simultaneously optimize cost and performance?In this paper, we formalize this local/global disk problem as follows. A scheduler running many (potentially parallel) processes must serve I/O requests to local/global disks and can move objects between the disks over time. The local disk performs I/Os for free, but can only perform one I/O per timestep, while the global disk charges a fee for each I/O, but has unlimited bandwidth. The scheduler wishes to optimize both the stretch of each process that it runs (the running-time blowup compared to if that process used only global disk) and the overall cost savings (the amount of money saved compared to a world in which we use only the global disk).We show, for any ε ∈ (0, 1] that it is possible to support an expected stretch of 1 + O(ε) while saving a total of εE[T] expected dollars, where T is the number of distinct timesteps in which I/Os are performed. We also offer a second tradeoff curve that, for any δ \v{s} (0, 1), supports expected stretch 1 + O(δ−1) with expected cost savings (1 − δ)E[T]. Finally, we prove that both of these tradeoff curves are asymptotically optimal. 

A box-ball system is a collection of discrete time states. At each state, we have a collection of countably many boxes with each integer from 1 to n assigned to a unique box; the remaining boxes are considered empty. A permutation on n objects gives a box-ball system state by assigning the permutation in one-line notation to the first n boxes. After a finite number of steps, the system will reach a so-called soliton decomposition which has an integer partition shape. We prove the following: if the soliton decomposition of a permutation is a standard Young tableau or if its shape coincides with its Robinson–Schensted (RS) partition, then its soliton decomposition and its RS insertion tableau are equal. We study the time required for a box-ball system to reach a steady state. We also generalize Fukuda’s single-carrier algorithm to algorithms with more than one carrier.