More Web Proxy on the site http://driver.im/

research-article

Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation

Authors:

Fabian R. Wirth,

Martin Corless,

Robert ShortenAuthors Info & Claims

Journal of the ACM (JACM), Volume 66, Issue 4

Article No.: 24, Pages 1 - 37

https://doi.org/10.1145/3312741

Published: 07 June 2019 Publication History

Abstract

A stochastic algorithm is presented for a class of optimisation problems that arise when a group of agents compete to share a single constrained resource in an optimal manner. The approach uses intermittent single-bit feedback, which indicates a constraint violation and does not require inter-agent communication. The algorithm is based on a positive matrix model of AIMD, which is extended to the nonhomogeneous Markovian case. The key feature is the assignment of back-off probabilities to the individual agents as a function of the past average access to the resource. This leads to a nonhomogeneous Markov chain in an extended state space, and we show almost sure convergence of the average access to the social optimum.

References

[1]

D. Angeli and P.-A. Kountouriotis. 2012. A stochastic approach to dynamic-demand refrigerator control. IEEE Trans. Control Syst. Technol. 20, 3 (2012), 581--592.

[2]

M. F. Barnsley, S. G. Demko, J. H. Elton, and J. S. Geronimo. 1988. Invariant measures for Markov processes arising from iterated function systems with place-dependent probabilities. Annales de l’Institut Henri Poincaré (B) Probabilités et Statistiques 24, 3 (1988), 367--394.

[3]

S. Bhandarkar, A. L. N. Reddy, Y. Zhang, and D. Loguinov. 2007. Emulating AQM from end hosts. SIGCOMM Comput. Commun. Rev. 37, 4 (2007), 349--360.

Digital Library

[4]

P. Bianchi, G. Fort, and W. Hachem. 2013. Performance of a distributed stochastic approximation algorithm. IEEE Trans. Info. Theory 59, 11 (2013), 7405--7418.

Digital Library

[5]

B. Biegel, P. Andersen, T. S. Pedersen, K. M. Nielsen, J. Stoustrup, and L. H. Hansen. 2013. Smart grid dispatch strategy for ON/OFF demand-side devices. In Proceedings of the European Control Conference (ECC’13). 2541--2548.

[6]

P. Billingsley. 1995. Probability and Measure, 3rd ed. John Wiley 8 Sons, Hoboken, NJ.

[7]

V. S. Borkar. 2008. Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, Cambridge, UK.

[8]

S. Boyd and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY.

Digital Library

[9]

L. S. Brakmo, S. W. O'Malley, and L. L. Peterson. 1994. TCP Vegas: New techniques for congestion detection and avoidance. SIGCOMM Comput. Commun. Rev. 24, 4 (1994), 24--35.

Digital Library

[10]

A. Brooks, E. Lu, D. Reicher, C. Spirakis, and B. Weihl. 2010. Demand dispatch. IEEE Power Energy Mag. 8, 3 (2010), 20--29.

[11]

Ł. Budzisz, R. Stanojević, A. Schlote, F. Baker, and R. Shorten. 2011. On the fair coexistence of loss-and delay-based TCP. IEEE/ACM Trans. Netw. 19, 6 (2011), 1811--1824.

Digital Library

[12]

M. Chiang, S. Low, R. Calderbank, and J. Doyle. 2007. Layering as optimization decomposition: A mathematical theory of network architectures. Proc. IEEE 95, 1 (2007), 255--312.

[13]

K. Clement, E. Haesen, and J. Driesen. 2009. Coordinated charging of multiple plug-in hybrid electric vehicles in residential distribution grids. In Proceedings of the IEEE/PES Power Systems Conference and Exposition (PSCE’09). 1--7.

[14]

K. Clement-Nyns, E. Haesen, and J. Driesen. 2010. The impact of charging plug-in hybrid electric vehicles on a residential distribution grid. IEEE Trans. Power Syst. 25, 1 (2010), 371--380.

[15]

M. Corless, C. King, R. Shorten, and F. Wirth. 2016. AIMD Dynamics and Distributed Resource Allocation. Number 29 in Advances in Design and Control. SIAM, Philadelphia, PA.

Digital Library

[16]

E. Crisostomi, M. Liu, M. Raugi, and R. Shorten. 2014. Stochastic distributed algorithms for power generation in a microgrid. IEEE Trans. Smart Grid 5, 4 (2014), 2145--2154.

[17]

E. Crisostomi, R. Shorten, S. Stüdli, and F. Wirth. 2017. Electric and Plug-in Hybrid Vehicle Networks: Optimization and Control. CRC Press, 2017.

[18]

S. Deilami, A. S. Masoum, P. S. Moses, and M. A. S. Masoum. 2011. Real-time coordination of plug-in electric vehicle charging in smart grids to minimize power losses and improve voltage profile. IEEE Trans. Smart Grid 2, 3 (2011), 456--467.

[19]

J. Duchi, A. Agarwal, and M. Wainwright. 2012. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Automat. Control 57, 3 (2012), 592--606.

[20]

J. H. Elton. 1987. An ergodic theorem for iterated maps. Ergodic Theory Dynam. Systems 7, 4 (1987), 481--488.

[21]

P. Ferarro, E. Crisostomi, R. Shorten, and F. Milano. 2018. Stochastic frequency control of grid-connected microgrids. IEEE Trans. Power Syst. 33, 5 (2018), 5704--5713.

[22]

L. P. Fernández, T. G. San Róman, R. Cossent, C. M. Domingo, and P. Frías. 2011. Assessment of the impact of plug-in electric vehicles on distribution networks. IEEE Trans. Power Syst. 26, 1 (Feb. 2011), 206--213.

[23]

P. Finn, C. Fitzpatrick, and M. Leahy. 2009. Increased penetration of wind generated electricity using real time pricing; demand side management. In Proceedings of the IEEE International Symposium on Sustainable Systems and Technology (ISSST’09). IEEE, 1--6.

[24]

A. Fioravanti, J. Marecek, R. Shorten, M. Souza, and F. Wirth. 2017. On classical control and Smart Cities. In Proceedings of the 56th Conference on Decision and Control (CDC’17). 1412--1420.

[25]

S. Floyd. 2003. High Speed TCP for Large Congestion Windows. Technical Report. Internet draft draft-floyd-tcp-highspeed-02.txt, RFC 3649.

Digital Library

[26]

W. Griggs, R. Ordonez-Hurtado, E. Crisostomi, F. Haeusler, K. Massow, and R. Shorten. 2015. A large-scale SUMO-based emulation platform. IEEE Trans. Intell. Transport. Syst. 16, 3 (2015), 3050--3059.

Digital Library

[27]

A. Harris. 2000. Charge of the electric car {electric vehicles}. Engineer. Technol. 4, 10 (June 2000), 52--53.

[28]

D. J. Hartfiel. 2002. Nonhomogeneous Matrix Products. World Scientific, Singapore.

[29]

D. Hayes and G. Armitage. 2010. Improved coexistence and loss tolerance for delay-based TCP congestion control. In Proceedings of the IEEE Local Computer Network Conference. 24--31.

Digital Library

[30]

V. Jacobson. 1988. Congestion avoidance and control. ACM SIGCOMM Comput. Commun. Rev. 18, 4 (1988), 314--329.

Digital Library

[31]

B. Johansson, M. Rabi, and M. Johansson. 2009. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM J. Control Optimiz. 20, 3 (2009), 1157--1170.

Digital Library

[32]

K. Kar, S. Sarkar, and L. Tassiulas. 2001. A simple rate control algorithm for max total user utility. In Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’01), vol. 1. IEEE, 133--141 vol.1.

[33]

T. Kelly. 2002. On Engineering a Stable and Scalable TCP Variant. Technical Report. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.435.

[34]

S. Kumar, S.-J. Park, and S. S. Iyengar. 2010. A loss-event driven scalable fluid simulation method for high-speed networks. Comput. Netw. 54, 1 (2010), 112--132.

Digital Library

[35]

S. Kunniyur and R. Srikant. 2003a. End-to-end congestion control schemes: Utility functions, random losses and ECN marks. IEEE/ACM Trans. Netw. 11, 5 (2003), 689--702.

Digital Library

[36]

S. S. Kunniyur and R. Srikant. 2003b. Stable, scalable, fair congestion control and AQM schemes that achieve high utilisation in the internet. IEEE Trans. Automat. Control 48, 11 (2003), 2024--2029.

[37]

N. Li, L. Chen, and S. H. Low. 2011. Optimal demand response based on utility maximization in power networks. In Proceedings of the IEEE Power and Energy Society General Meeting. IEEE, 1--8.

[38]

S. Low, F. Paganini, and J. Doyle. 2002a. Internet congestion control. IEEE Control Syst. Mag. 32, 1 (2002), 28--43.

[39]

S. H. Low, L. L. Peterson, and L. Wang. 2002b. Understanding TCP Vegas: A duality model. J. ACM 49, 2 (2002), 207--235.

Digital Library

[40]

G. Mann, R. T. McDonald, M. Mohri, N. Silberman, and D. Walker. 2009. Efficient large-scale distributed training of conditional maximum entropy models. Adv. Neural Info. Process. Syst. 22 (2009), 1231--1239.

Digital Library

[41]

J. Masaki, G. G. D. Nishantha, and Y. Hayashida. 2010. Development of a high-speed transport protocol with TCP-Reno friendliness. In Proceedings of the International Conference on Advanced Communication Technology (ICACT’10), vol. 1. 174--179.

[42]

J. L. Mathieu, M. Kamgarpour, J. Lygeros, and D. S. Callaway. 2013. Energy arbitrage with thermostatically controlled loads. In Proceedings of the European Control Conference (ECC’13). IEEE, Zurich, Switzerland, 2519--2526.

[43]

S. Molnar, S. Balazs, and T. Tuan. 2009. A comprehensive TCP fairness analysis in high speed networks. Comput. Commun. 32 (2009), 1460--1484.

Digital Library

[44]

A. Nedic and A. Ozdaglar. 2009. Distributed subgradient methods for multi-agent optimization. IEEE Trans. Automat. Control 54, 1 (2009), 48--61.

[45]

G. A. Putrus, P. Suwanapingkarl, D. Johnston, E. C. Bentley, and M. Narayana. 2009. Impact of electric vehicles on power distribution networks. In Proceedings of the IEEE Vehicle Power and Propulsion Conference (VPPC’09). IEEE, 827--831.

[46]

S. S. Ram, A. Nedić, and V. V. Veeravalli. 2010. Distributed stochastic subgradient projection algorithms for convex optimization. J. Optim. Theory Appl. 147, 3 (2010), 516--545.

[47]

S. Sayeef, S. Heslop, D. Cornforth, T. Moore, S. Percy, J. K. Ward, A. Berry, and D. Rowe. 2012. Solar intermittency: Australia’s clean energy challenge. Retrieved from http://www.csiro.au/Organisation-Structure/Flagships/Energy-Flagship/Solar-Intermittency-Report.aspx.

[48]

A. Schlote, F. Häusler, T. Hecker, A. Bergmann, E. Crisostomi, I. Radusch, and R. Shorten. 2013. Cooperative regulation and trading of emissions using plug-in hybrid vehicles. IEEE Trans. Intell. Transport. Syst. 14, 4 (2013), 1572--1585.

Digital Library

[49]

S. E. Shafiei, H. Rasmussen, and J. Stoustrup. 2013. Model predictive control for a thermostatic controlled system. In Proceedings of the European Control Conference (ECC’13). IEEE, Zurich, Switzerland, 1559--1564.

[50]

R. Shorten, C. King, F. Wirth, and D. Leith. 2007. Modelling TCP congestion control dynamics in drop-tail environments. Automatica 43, 3 (2007), 441--449.

Digital Library

[51]

R. Shorten, F. Wirth, and D. Leith. 2006. A positive systems model of TCP-like congestion control: Asymptotic analysis. IEEE/ACM Trans. Netw. 14 (2006), 616--629.

Digital Library

[52]

S. Sinnot, R. Ordonez-Hurtado, G. Russo, and R. Shorten. 2016. On the design of a route parsing engine for connected vehicles with applications to congestion management systems. In Proceedings of the 19th IEEE International Conference on Intelligent Transportation. 1586--1591.

[53]

R. Srikant. 2004. Internet Congestion Control. Control Theory, vol. 14. Birkhäuser, Boston, MA.

[54]

S. Stuedli, E. Crisostomi, R. Middleton, and R. Shorten. 2012. A flexible distributed framework for realising electric and plug-in hybrid vehicle charging policies. Int. J. Control 85, 8 (2012), 1130--1145.

[55]

K. Tan, J. Song, Q. Zhang, and M. Sridharan. 2006. A compound TCP approach for high-speed and long distance networks. In Proceedings of the 25th Conference of the IEEE Computer and Communications Societies (INFOCOM’06). 1--12.

[56]

D. X. Wei, C. Jin, S. H. Low, and S. Hegde. 2006. FAST TCP: Motivation, architecture, algorithms, performance. IEEE/ACM Trans. Netw. 14, 6 (2006), 1246--1259.

Digital Library

[57]

F. Wirth, R. Stanojevic, R. Shorten, and D. Leith. 2006. Stochastic equilibria of AIMD communication networks. SIAM J. Matrix Anal. Appl. 28, 3 (2006), 703--723.

Digital Library

[58]

L. Xu, K. Harfoush, and I. Rhee. 2004. Binary increase congestion control (BIC) for fast long-distance networks. In Proceedings of the Conference of the IEEE Computer and Communications Societies (INFOCOM’04). IEEE, 2514--2524.

[59]

M. Zinkevich, M. Weimer, A. J. Smola, and L. Li. 2010. Parallelized stochastic gradient descent. Adv. Neural Info. Process. Syst. 23 (2010), 2595--2603.

Digital Library

Cited By

Corless MCoduti L(2024)Consensus With a Linear ConstraintIEEE Transactions on Automatic Control10.1109/TAC.2023.331568869:1(645-650)Online publication date: Jan-2024
https://doi.org/10.1109/TAC.2023.3315688
Alam SShukla D(2023)Existence of a Unique Invariant Measure and Ergodic Property in AIMD-based Multi-resource Allocation2023 American Control Conference (ACC)10.23919/ACC55779.2023.10155852(2592-2598)Online publication date: 31-May-2023
https://doi.org/10.23919/ACC55779.2023.10155852
Alam SShukla D(2023)Communication-Efficient Allocation of Multiple Indivisible Resources in a Federated Multi-Agent System2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10384067(5279-5285)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10384067
Show More Cited By

Index Terms

Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and Optimisation
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
  2. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Uniformization for nonhomogeneous Markov chains

The discrete Poissonian representation for transition probabilities of homogeneous continuous-time Markov chains, known as uniformization or randomization, is extended to time-inhomogeneous chains. For computational purposes a discrete-time ...
Deterministic and stochastic convergence properties of AIMD algorithms with nonlinear back-off functions

In this paper we establish basic stability results for a class of nonlinear AIMD (additive-increase multiplicative-decrease) algorithms. We consider networks in which the nonlinearity enters through the multiplicative-decrease mechanism. In particular, ...
Sensitivity to the Service-Time Distribution in the Nonstationary Erlang Loss Model

The stationary Erlang loss model is a classic example of an insensitive queueing system: the steady-state distribution of the number of busy servers depends on the service-time distribution only through its mean. However, when the arrival process is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 66, Issue 4

Networking, Computational Complexity, Design and Analysis of Algorithms, Real Computation, Algorithms, Online Algorithms and Computer-aided Verification

August 2019

299 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3338848

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 June 2019

Accepted: 01 January 2019

Revised: 01 January 2019

Received: 01 March 2016

Published in JACM Volume 66, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)4

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Corless MCoduti L(2024)Consensus With a Linear ConstraintIEEE Transactions on Automatic Control10.1109/TAC.2023.331568869:1(645-650)Online publication date: Jan-2024
https://doi.org/10.1109/TAC.2023.3315688
Alam SShukla D(2023)Existence of a Unique Invariant Measure and Ergodic Property in AIMD-based Multi-resource Allocation2023 American Control Conference (ACC)10.23919/ACC55779.2023.10155852(2592-2598)Online publication date: 31-May-2023
https://doi.org/10.23919/ACC55779.2023.10155852
Alam SShukla D(2023)Communication-Efficient Allocation of Multiple Indivisible Resources in a Federated Multi-Agent System2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10384067(5279-5285)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10384067
Alam SShukla D(2023)Communication-efficient Preference-based Federated Multi-resource Allocation2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton)10.1109/Allerton58177.2023.10313434(1-4)Online publication date: 26-Sep-2023
https://doi.org/10.1109/Allerton58177.2023.10313434
Alam SShukla DRao S(2023)A Communication-Efficient Local Differentially Private Algorithm in Federated OptimizationIEEE Access10.1109/ACCESS.2023.328350311(58254-58268)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3283503
Ferraro PYu JGhosh RAlam SMarecek JWirth FShorten R(2023)On unique ergodicity of coupled AIMD flowsInternational Journal of Control10.1080/00207179.2023.225901697:9(2151-2161)Online publication date: 3-Oct-2023
https://doi.org/10.1080/00207179.2023.2259016
Moschella MMurad MCrisostomi EMilano F(2021)Decentralized Charging of Plug-In Electric Vehicles and Impact on Transmission System DynamicsIEEE Transactions on Smart Grid10.1109/TSG.2020.303452812:2(1772-1781)Online publication date: Mar-2021
https://doi.org/10.1109/TSG.2020.3034528
Fan XCrisostomi EThomopulos DZhang BShorten RYang S(2021)An Optimized Decentralized Power Sharing Strategy for Wind Farm De-LoadingIEEE Transactions on Power Systems10.1109/TPWRS.2020.300825836:1(136-146)Online publication date: Jan-2021
https://doi.org/10.1109/TPWRS.2020.3008258
Alam SShorten RWirth FYu J(2020)Distributed Algorithms for Internet-of-Things-Enabled Prosumer Markets: A Control Theoretic PerspectiveAnalytics for the Sharing Economy: Mathematics, Engineering and Business Perspectives10.1007/978-3-030-35032-1_9(125-149)Online publication date: 12-Mar-2020
https://doi.org/10.1007/978-3-030-35032-1_9

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents