# Derandomized Distributed Multi-resource Allocation with Little Communication Overhead

@article{Alam2018DerandomizedDM, title={Derandomized Distributed Multi-resource Allocation with Little Communication Overhead}, author={Syed Eqbal Alam and R. Shorten and Fabian R. Wirth and Jia Yuan Yu}, journal={2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)}, year={2018}, pages={84-91} }

We study a class of distributed optimization problems for multiple shared resource allocation in Internet-connected devices. We propose a derandomized version of an existing stochastic additive-increase and multiplicative-decrease (AIMD) algorithm. The proposed solution uses one bit feedback signal for each resource between the system and the Internet-connected devices and does not require inter-device communication. Additionally, the Internet-connected devices do not compromise their privacy… Expand

#### Figures, Tables, and Topics from this paper

#### 3 Citations

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

- Mathematics, Computer Science
- ArXiv
- 2021

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. Expand

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

- Computer Science
- 2018

This paper proposes a new algorithm with fundamental guarantees of convergence and optimality, as well as present an example illustrating its performance. Expand

On the control of agents coupled through shared resources

- Computer Science, Mathematics
- ArXiv
- 2018

A new algorithm is presented with basic guarantees of convergence and optimality, as well as an example illustrating its performance, for a control problem involving a number of agents coupled through multiple unit-demand resources. Expand

#### References

SHOWING 1-10 OF 41 REFERENCES

Asynchronous Broadcast-Based Convex Optimization Over a Network

- Computer Science
- IEEE Transactions on Automatic Control
- 2011

An asynchronous broadcast-based algorithm where the communications over the network are subject to random link failures and the convergence properties of the algorithm for a diminishing (random) stepsize and a constant stepsize are investigated. Expand

Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication

- Mathematics, Computer Science
- Autom.
- 2015

The exponential convergence of the proposed algorithm under strongly connected and weight-balanced digraph topologies when the local costs are strongly convex with globally Lipschitz gradients is established, and an upper bound on the stepsize is provided that guarantees exponential convergence over connected graphs for implementations with periodic communication. Expand

Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

- Mathematics, Computer Science
- IEEE Transactions on Automatic Control
- 2012

This work develops and analyze distributed algorithms based on dual subgradient averaging and provides sharp bounds on their convergence rates as a function of the network size and topology, and shows that the number of iterations required by the algorithm scales inversely in the spectral gap of thenetwork. Expand

Differentially Private Distributed Constrained Optimization

- Computer Science, Mathematics
- IEEE Transactions on Automatic Control
- 2017

This paper presents a distributed optimization algorithm that preserves differential privacy, which is a strong notion that guarantees user privacy regardless of any auxiliary information an adversary may have. Expand

Nonhomogeneous Place-Dependent Markov Chains, Unsynchronised AIMD, and Network Utility Maximization

- Mathematics
- 2014

We present a solution of a class of network utility maximization (NUM) problems using minimal communication. The constraints of the problem are inspired less by TCP-like congestion control but by… Expand

AIMD Dynamics and Distributed Resource Allocation

- Computer Science
- 2016

Basic and fundamental properties of the AIMD algorithm are described, examples are used to illustrate the richness of the resulting dynamical systems, and applications are provided to show how the algorithm can be used in the context of smart cities, intelligent transportation system, and the smart grid. Expand

Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method

- Computer Science, Mathematics
- IEEE Transactions on Automatic Control
- 2014

This paper proves that the proposed PDP algorithm converges to an optimal primal-dual solution of the original problem, under standard problem and network assumptions, and presents numerical results illustrating the performance of the proposed algorithm for a distributed demand response control problem in smart grid. Expand

AIMD in a discrete time implementation or with a non-constant shared resource

- Computer Science
- 2015 5th Australian Control Conference (AUCC)
- 2015

A disturbed AIMD model is developed based on the model introduced by Shorten et al. that includes discrete time implementation and time varying resource availability and bound the influence of these disturbances, caused by either a discrete implementation or small variations in the available resource. Expand

Distributed Subgradient Methods for Multi-Agent Optimization

- Computer Science
- IEEE Transactions on Automatic Control
- 2009

The authors' convergence rate results explicitly characterize the tradeoff between a desired accuracy of the generated approximate optimal solutions and the number of iterations needed to achieve the accuracy. Expand

Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks

- Computer Science
- Comput. Networks
- 1989

It is shown that a simple additive increase and multiplicative decrease algorithm satisfies the sufficient conditions for con- vergence to an efficient and fair state regardless of the starting state of the network. Expand