Abstract We study the problem of determining whether a given random matching can be implemented as a lottery over weakly stable deterministic matchings – a property known as ex-post stability. This concept arises in randomized allocation mechanisms such as school choice, where stability in each realized outcome is essential for fairness. Despite its importance in practice, the computational complexity of verifying ex-post stability has remained unresolved. We settle this question by showing that testing ex-post stability is NP-complete, even under highly restricted conditions – specifically, when both sides have dichotomous preferences or one of the sides has strict preferences. On the positive side, we present an integer programming formulation that finds a decomposition of a random matching with maximum weight on stable matchings. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time.

The {balls-into-bins model} randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ⩾ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is log_d log n + 𝒪(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from ℋ^(t) uniformly at random, and then chooses a set D of d ⩾ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n^{1-ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

The asynchronous rumor spreading algorithm propagates a piece of information, the so-called rumor, in a network. Starting with a single informed node, each node is associated with an exponential time clock with rate 1 and calls a random neighbor in order to possibly exchange the rumor. A well-studied parameter associated with the algorithm is the spread time, which is the first time when all nodes of a network are informed with high probability1. We consider the spread time of the algorithm in any dynamic evolving network, [EQUATION], which is a sequence of n-node graphs with the same set of nodes exposed at discrete time step t = 0, 1. ... We establish upper bounds for the spread time in terms of graph conductance and diligence. For a given connected simple graph G = (V, E), the diligence of cut set [EQUATION] is defined as

We consider load balancing problem in a cache network consisting of storage-enabled servers forming a distributed content delivery scenario. Previously proposed load balancing solutions cannot perfectly balance out requests among servers, which is a critical issue in practical networks. Therefore, in this paper, we investigate a coded cache content placement where coded chunks of original files are stored in servers based on the files popularity distribution. In our scheme, upon each request arrival at the delivery phase, by dispatching enough coded chunks to the request origin from the nearest servers, the requested file can be decoded. Here, we show that if n requests arrive randomly at n servers, the proposed scheme results in the maximum load of O(1) in the network. This result is shown to be valid under various assumptions for the underlying network topology. Our results should be compared to the maximum load of two baseline schemes, namely, nearest replica and power of two choices strategies, which are O(log n) and O(log log n), respectively. This finding shows that using coding, results in a considerable load balancing performance improvement, without compromising communications cost performance. This is confirmed by performing extensive simulation results, in non-asymptotic regimes as well.

Standard randomized rumor spreading algorithms propagate a piece of information, so-called the rumor, in a given network that proceed in synchronized rounds. Starting with a single informed node, in each subsequent round, every node calls a random neighbor in order to exchange the rumor (by sending the rumor to the neighbor (push algorithm) or asking it from the neighbor (pull algorithm)). Panagiotou et al. [ISAAC'13] considered a multiple-call version of the algorithms where each node is enabled to make more than one call in each round. The number of calls of a node is independently chosen from a probability distribution R. Seeking for a more realistic model, we propose an asynchronous version of the multiple-call algorithms on fully connected networks. In our model, each node has an independent Poisson clock whose rate may differ from others. Basically, the clock rate of each node is independently drawn from a probability distribution R at the beginning of the process. The push algorithm starts with a single informed node, when the clock of an informed node rings, the node contacts a random neighbor and sends (pushes) the rumor to the neighbor. Similarly, in the push-pull, if the clock of a node rings, then the node contacts a random neighbor in order to exchange the rumor. We study the effect of R on the spreading time of the algorithms, which is the time that the algorithm needs to inform all nodes with high probability. In this work, we show that if R is a power law distribution with exponent β \in(2,3)$ and $\varepsilon\in[1/n, 1-1/n]$ be an arbitrary number. Then in expectation, after $O(1+łog(1/\varepsilon))$ time the push-pull algorithm informs at least $(1-\varepsilon)n$ nodes. Moreover, if R is an arbitrary distribution with bounded mean and variance, we show that the push algorithm spreads the rumor in a complete network with n nodes in $\fracłog n \matbbE R \pm O(łogłog n)$ time, with high probability.

We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems. In this framework, we investigate the tension between storage resources, communication cost, and load balancing performance. To this end, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. In contrast to the classical power of two choices setup, since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices. However, we prove that in certain regimes of problem parameters, our scheme results in the maximum load of order Q(loglogn) (here n is the network size). This is an exponential improvement compared to the scheme which assigns each request to the nearest available replica. Interestingly, the extra communication cost incurred by our proposed scheme, compared to the nearest replica strategy, is small. Furthermore, our extensive simulations show that the trade-off trend does not depend on the network topology and library popularity profile details.

We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems that reduces network imbalance. In this paper, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. Since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices in general. However, we prove that in certain regimes, in terms of memory limitation and proximity constraint, our scheme results in the maximum load of order Θ(log log n) (here n is the number of servers and requests), and at the same time, leads to a low communication cost. This is an exponential improvement in the maximum load compared to the scheme which assigns each request to the nearest available replica. Finally, we investigate our scheme performance by extensive simulations.

It is well known that load balancing and low delivery communication cost are two critical issues in mapping requests to servers in Content Delivery Networks (CDNs). However, the trade-off between these two performance metrics has not been yet quantitatively investigated in designing efficient request mapping schemes. In this work, we formalize this trade-off through a stochastic optimization problem. While the solutions to the problem in the extreme cases of minimum communication cost and optimum load balancing can be derived in closed form, finding the general solution is hard to derive. Thus we propose three heuristic mapping schemes and compare the trade-off performance of them through extensive simulations. Our simulation results show that at the expense of high query cost, we can achieve a good trade-off curve. Moreover, by benefiting from the power of multiple choices phenomenon, we can achieve almost the same performance with much less query cost. Finally, we can handle requests with different delay requirements at the cost of degrading network performance.