Balls-and-bins games have been a successful tool for modeling load balancing problems. In this paper, we study a new scenario, which we call the ball-recycling game, defined as follows: Throw m balls into n bins i.i.d. according to a given probability distribution p. Then, at each time step, pick a non-empty bin and recycle its balls: take the balls from the selected bin and re-throw them according to p. This balls-and-bins game closely models memory-access heuristics in databases. The goal is to have a bin-picking method that maximizes the recycling rate, defined to be the expected number of balls recycled per step in the stationary distribution. We study two natural strategies for ball recycling: Fullest Bin, which greedily picks the bin with the maximum number of balls, and Random Ball, which picks a ball at random and recycles its bin. We show that for general p, random Ball is Θ(1)-optimal, whereas Fullest Bin can be pessimal. However, when p = u, the uniform distribution, Fullest Bin is optimal to within an additive constant.

Today's (predominantly cloud-based) File sharing products leave users at the mercy of providers and nation-state adversaries with subpoena and National Security Letter (NSL) powers. In-transit and provider-side at-rest encryption do little to handle this.Almost-weekly breaches [7-13, 17] and NSL revelations [2] show that the problem becomes only worse with increasingly privacy-unfriendly regulation [14]. We believe it is important to provide hype-free, easy-to-use strongly-secure solutions that protect individual privacy while also defeating cloud breaches and compromises. CipherLocker provides practical, easy-to-use, client-side encrypted File sharing with integrated ranked search. All data and metadata is strongly encrypted before leaving the client. Users can securely store, share, sync, and search. The design does not allow even a compromised or compelled cloud provider to ever access user data or search queries. CipherLocker shows that highly-scalable, fast ranked search on encrypted data is possible without the deployment of expensive and often insecure server-side search-on-encrypted-data cryptography which would require 3-5 orders of magnitude more resources and cannot scale to even thousands of users, or the simplest sharing scenarios without breaking security. CipherLocker is the result of several years of work and it cannot be exhaustively detailed and analyzed in this space. This is the first of a series of papers discussing CipherLocker design, implementation and security properties. The main goal here is to briefly overview and introduce key design decisions and behaviors.