|
Minimum collisions assignment in interdependent networked systems via defective colorings
|
Authors: Maria Diamanti, Nikolaos Fryganiotis, Symeon Papavassiliou, Christos Pelekis, Eirini Eleni Tsiropoulou
Status:
Date of publication: 1 March 2024
Published in: ITU Journal on Future and Evolving Technologies, Volume 5 (2024), Issue 1, Pages 1-12
Article DOI : https://doi.org/10.52953/JNDY5511
|
Abstract:
In conjunction with the traffic overload of next-generation wireless communication and computer networks, their resource-constrained nature calls for effective methods to deal with the fundamental resource allocation problem. In this context, the Minimum Collisions Assignment (MCA) problem in an interdependent networked system refers to the assignment of a finite set of resources over the nodes of the network, such that the number of collisions, i.e., the number of interdependent nodes receiving the same resource, is minimized. Given the interdependent networked system's organization in the form of a graph, there already exists a randomized algorithm that converges with high probability to an assignment of resources having zero collisions when the number of resources is larger than the maximum degree of the underlying graph. In this article, differing from the prevailing literature, we investigate the case of a resource-constrained networked system, where the number of resources is less than or equal to the maximum degree of the underlying graph. We introduce two distributed, randomized algorithms that converge in a logarithmic number of rounds to an assignment of resources over the network for which every node has at most a certain number of collisions. The proposed algorithms apply to settings where the available resources at each node are equal to three and two, respectively, while they are executed in a fully-distributed manner without requiring information exchange between the networked nodes. |
Keywords: Defective coloring, games on graphs, graph coloring, resource allocation
Rights: © International Telecommunication Union, available under the CC BY-NC-ND 3.0 IGO license.
|
|
| ITEM DETAIL | ARTICLE | PRICE | |
|---|
ENGLISH 
Full article (PDF) |
|
| 0
| Free of charge | DOWNLOAD |
|
|
| |
