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

arXiv: https://arxiv.org/abs/2104.12828 · HTML: https://mlsanity.com/paper/2104.12828/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 51 references that are in the map.
- First posted on arXiv 26 Apr 2021.

## Builds on (most cited first, 12 of 12)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Communication-efficient Distributed Multi-resource Allocation](https://mlsanity.com/paper/1807.10860/) (2018)
- [On the Design of Campus Parking Systems with QoS guarantees](https://mlsanity.com/paper/1506.02818/) (2015)
- [Derandomized Distributed Multi-resource Allocation with Little Communication Overhead](https://mlsanity.com/paper/1812.09404/) (2018)
- [The Convergence of Finite-Averaging of AIMD for Distributed Heterogeneous Resource Allocations](https://mlsanity.com/paper/2001.08083/) (2020)

## Abstract (arXiv)

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.