EXPERIMENTAL EVALUATION OF DISTRIBUTED ALGORITHMS IN ACTIVELY DYNAMIC NETWORK

Abstract

An increasing number of distributed algorithms in a dynamic network is the result of many im- provements in this complex network. The study and operation of a dynamic system involves using a number of models and algorithms to deal with a specific problem. A recent study by Michail et al. (2020) looked at a dynamic network in which the communication of distributed algorithms is exploited to reconfigure the network structure for certain purposes. In that study, three main algorithms were proposed: GraphToStar, GraphToWreath and GraphToThinWreath. It is important to explore the pattern of a model and investigate the rules of the entities (nodes) used to configure nodes’ connections to the target form of the network. It is also important to examine algorithms to get an overview of the parameters used to calculate the efficiency of those algorithms and to analyse the evolution of the measures used. Thus, this work is an ex- ploratory investigation to assess and verify the guaranteed theoretical maximum boundaries of algorithms. This paper presents an experimental evaluation of the GraphToStar and GraphToWreath algo- rithms and compares them in terms of performance measures, such as running time and com- plexity. To do this, three different experiments were completed using the GraphToStar and GraphToWreath algorithms in three networks—line, ring and random networks—each with be- tween 1000 to 100,000 nodes. The findings of these experiments confirm the asymptotic nota- tion of the theoretical bounds of algorithm measurements. Also, certain assumptions about the hidden constants required for each specific experiment in regard to the complexity measure- ments are discussed.