Multi-resource allocation for federated settings: A non-homogeneous Markov chain model

In a federated setting, agents coordinate with a central agent or a server to solve an optimization problem in which agents do not share their information with each other. Wirth and his co-authors, in a recent paper, describe how the basic additive-increase multiplicative-decrease (AIMD) algorithm can be modified in a straightforward manner to solve a class of optimization problems for federated settings for a single shared resource with no inter-agent communication. The AIMD algorithm is one of the most successful distributed resource allocation algorithms currently deployed in practice. It is best known as the backbone of the Internet and is also widely explored in other application areas. We extend the single-resource algorithm to multiple heterogeneous shared resources that emerge in smart cities, sharing economy, and many other applications. Our main results show the convergence of the average allocations to the optimal values. We model the system as a non-homogeneous Markov chain with place-dependent probabilities. Furthermore, simulation results are presented to demonstrate the efficacy of the algorithms and to highlight the main features of our analysis.

Communication-efficient Distributed Multi-resource Allocation

In several smart city applications, multiple resources must be allocated among competing agents that are coupled through such shared resources and are constrained --- either through limitations of communication infrastructure or privacy considerations. We propose a distributed algorithm to solve such distributed multi-resource allocation problems with no direct inter-agent communication. We do so by extending a recently introduced additive-increase multiplicative-decrease (AIMD) algorithm, which only uses very little communication between the system and agents. Namely, a control unit broadcasts a one-bit signal to agents whenever one of the allocated resources exceeds capacity. Agents then respond to this signal in a probabilistic manner. In the proposed algorithm, each agent makes decision of its resource demand locally and an agent is unaware of the resource allocation of other agents. In empirical results, we observe that the average allocations converge over time to optimal allocations.

On the Control of Agents Coupled through Shared Unit-demand Resources

We consider a control problem involving several agents coupled through multiple unit-demand resources. Such resources are indivisible, and each agents consumption is modeled as a Bernoulli random variable. Controlling the number of such agents in a probabilistic manner, subject to capacity constraints, is ubiquitous in smart cities. For instance, such agents can be humans in a feedback loop---who respond to a price signal, or automated decision-support systems that strive toward system-level goals. In this paper, we consider both single feedback loop corresponding to a single resource and multiple coupled feedback loops corresponding to multiple resources consumed by the same population of agents. For example, when a network of devices allocates resources to deliver several services, these services are coupled through capacity constraints on the resources. We propose a new algorithm with fundamental guarantees of convergence and optimality, as well as present an example illustrating its performance.

Distributed Multi-resource Allocation with Little Communication Overhead

We propose a distributed algorithm to solve a special distributed multi-resource allocation problem with no direct inter-agent communication. We do so by extending a recently introduced additive-increase multiplicative-decrease (AIMD) algorithm, which only uses very little communication between the system and agents. Namely, a control unit broadcasts a one-bit signal to agents whenever one of the allocated resources exceeds capacity. Agents then respond to this signal in a probabilistic manner. In the proposed algorithm, each agent is unaware of the resource allocation of other agents. We also propose a version of the AIMD algorithm for multiple binary resources (e.g., parking spaces). Binary resources are indivisible unit-demand resources, and each agent either allocated one unit of the resource or none. In empirical results, we observe that in both cases, the average allocations converge over time to optimal allocations.