Self-stabilizing Balls & Bins in Batches
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…
Multiple-Choice Balanced Allocation in (Almost) Parallel
We consider the problem of resource allocation in a parallel environment where new incoming resources are arriving online in groups or batches.
On the Influence of PRNGs on Data Distribution
The amount of digital information produced grows rapidly and constantly. Storage systems use clustered architectures designed to store and process this information efficiently. Their use introduces new challenges in storage systems development, like load-balancing and data distribution. A variety of randomized solutions handling data placement issues have been proposed and utilized. However, to the best of our knowledge, there has not yet been a structured analysis of the influence of pseudo random number generators (PRNGs) on the data distribution. In the first part of this paper we consider Consistent Hashing [1] as a combination of two consecutive phases: distribution of bins and distrib…
Distributing Storage in Cloud Environments
Cloud computing has a major impact on today's IT strategies. Outsourcing applications from IT departments to the cloud relieves users from building big infrastructures as well as from building the corresponding expertise, and allows them to focus on their main competences and businesses. One of the main hurdles of cloud computing is that not only the application, but also the data has to be moved to the cloud. Networking speed severely limits the amount of data that can travel between the cloud and the user, between different sites of the same cloud provider, or indeed between different cloud providers. It is therefore important to keep applications near the data itself. This paper investig…
Self-stabilizing Balls & Bins in Batches
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where $m$ balls (tasks) are to be distributed to $n$ bins (servers). In a seminal work, Azar et al. proposed the sequential strategy \greedy{d} for $n=m$. When thrown, a ball queries the load of $d$ random bins and is allocated to a least loaded of these. Azar et al. showed that $d=2$ yields an exponential improvement compared to $d=1$. Berenbrink et al. extended this to $m\gg n$, showing that the maximal load difference is independent of $m$ for $d=2$ (in contrast to $d=1$). W…
Random Slicing: Efficient and Scalable Data Placement for Large-Scale Storage Systems
The ever-growing amount of data requires highly scalable storage solutions. The most flexible approach is to use storage pools that can be expanded and scaled down by adding or removing storage devices. To make this approach usable, it is necessary to provide a solution to locate data items in such a dynamic environment. This article presents and evaluates the Random Slicing strategy, which incorporates lessons learned from table-based, rule-based, and pseudo-randomized hashing strategies and is able to provide a simple and efficient strategy that scales up to handle exascale data. Random Slicing keeps a small table with information about previous storage system insert and remove operations…
Randomized renaming in shared memory systems.
Abstract Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m . The problem is called tight if m = n , and loose if m > n . In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O ( log n ) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = ( 1 + ϵ ) ⋅ n and constant ϵ , they achieve a step complexity of O ( log log n ) . In this paper we consider tight as well as loos…
Balls into non-uniform bins
Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…