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.
翻译:在联合环境下,代理商与中央代理商或服务器协调,以解决代理商不相互交流信息的最优化问题。Wirth及其共同作者在最近的一篇论文中描述了如何以直截了当的方式修改基本的添加式增加多复制性减少(AIMD)算法,以解决一个单一共享资源(没有代理商间通信)的组合式设置的最优化问题。AIMD算法是目前实际中部署的最成功的资源分配分配算法之一,最著名的是互联网的主干线,在其他应用领域也广泛探索。我们将单一资源算法推广到智能城市、共享经济和许多其他应用中出现的多种多样性共享资源。我们的主要结果显示平均分配与最佳价值的趋同。我们把这个系统建模成一个非异质的马尔可夫链,具有依赖地点的概率。此外,模拟结果还展示了这些算法的功效并突出我们分析的主要特征。