This paper investigates the scalability of a variant of the well-known Ant Colony Optimization (ACO) algorithm for search operations in a distributed knowledge graph, with a focus on the algorithm's performance under increasing query loads. The data is represented as RDF triples, and the underlying network topology models a typical edge-fog-cloud architecture, reflecting scenarios relevant to the edge-cloud domain. Assuming nodes with infinite processing capacity, we show that the hit rate, the primary performance metric, initially increases with query frequency and eventually saturates. In contrast, when node processing capacity is finite, the hit rate exhibits a critical threshold after which performance declines. We analyze the behavior of the system under diferent query regimes, focusing on network utilization and pheromone-level dynamics. Finally, we discuss the feasibility of implementing such a system in practice and its potential implications for real-world applications.
The Edge-Fog-Cloud continuum represents a transformative paradigm in distributed computing, driven
by the increase of complexity in IoT (Internet of Things) devices, its number in a running system,
and data-intesive applications to be processed. Traditional cloud-centric models face key limitations,
such as latency, privacy concerns, and energy ineficiency. Distributed computation paradigms are
closer to the data sources in the edge and fog layers, thus enhancing overall system performance
and responsiveness [
Robustness in such distributed environments is essential due to the dynamic and often unpredictable
nature of edge-fog-cloud networks. Systems must withstand challenges posed by malicious agents that
can disrupt data integrity or routing, nodes that fail unexpectedly, intermittent link breaks, and the
continuous addition or removal of nodes reflecting network mobility and scaling. These factors create a
volatile environment where search and data management operations must adapt to maintain eficiency
and accuracy. Testing for node movement and network changes is thus critical to evaluate the resilience
of algorithms and protocols designed for this continuum. The search in dynamic environments of
distributed knowledge graphs requires scalable, robust, and eficient solutions capable of handling such
uncertainties [
Ant Colony Optimization (ACO), inspired by the foraging behavior of ants, ofers a promising approach to
address these challenges. By leveraging decentralized, self-organizing mechanisms based on pheromone
trails, ACO algorithms can dynamically adapt to network changes, optimize routing paths, and maintain
high search performance even under varying loads and network conditions [
The paper is organized as follows: Section 2 gives a general description of the problem and a detailed system model of the DKG in the edge-fog-cloud continuum. Section 3 summarizes the related work for RDF (Resource Description Framework), ACO and scalability analyses in swarms. Section 4 presents the main principles for the ACO-related pheromone search in the network. The evaluation of the hit rate and network utilization is described in Section 5 forming the base for the actual scalability analysis in Section 6. The paper is concluded in Section 7.
We study search and data movement on a distributed knowledge graph (DKG) using the ACO algorithm. The architecture of our knowledge graph is reflecting an example of the edge-fog-cloud continuum. We assess the complex system properties, such as scalability, fault tolerance and robustness, and adaptability. Our approach is compared with other known search algorithms with respect to their eficiency.
The edge-fog-cloud continuum is modeled as a hierarchical network that dynamically maps diferent
slices of the DKG across the edge, fog, and cloud layers. An example of a hierarchical network is
shown in Figure 1, where the proportion of edge-fog-cloud nodes is 5 : 4 : 1. The DKG is a novel
approach to knowledge representation and data management [
Each query maps to a keyword derived from its predicate and object , typically via string concatenation or hashing. This keyword uniquely identifies a pheromone in the ACO system.
Each node maintains: a list of direct neighbors ℵ; a record of forward ants ℱ, tracking which =1 (), storing pheromone values for each keyword ants have visited; a pheromone table = ⋃︀|ℵ| toward neighbor ; a link cost table ℒ = ⋃︀|ℵ| , listing the costs to each neighbor. =1 cloud fog edge
Processing large-scale RDF datasets [
Ant optimization is a robust model introduced in seminal works [
The properties of complex systems, such as scalability, robustness, or fault tolerance, require precise
formulations and measurements [
The ACO-based search algorithm operates through two primary mechanisms: trail following and trail laying.
Trail following When a query reaches a node , it generates a forward ant that follows one of two strategies: exploration or exploitation. The ant randomly selects between these strategies with probability . In the exploration strategy, the ant probabilistically selects its next node ∈ ℵ based on local pheromone levels () and link costs , as defined by:
() =
() ·
() ∑︀|ℵ| =1 ·
, () ≥
1 ∑|ℵ︁| |ℵ| =1 () , where controls how strongly the pheromone level influences the decision. In this study, we set = 1 and the link costs to 1. Future extensions could dynamically adjust these costs based on experience, e.g., increasing the cost for links with high latency or low computational performance. The probability in Eq. (1) is calculated across all neighbors of , meaning that the forward ant can split and send clones to multiple neighbors simultaneously. In the exploitation strategy, the ant selects all neighbors satisfying: thus focusing only on the best-performing options. In this study, the probability of choosing either strategy is set to 0.5. When a forward ant arrives at node , it checks the forward ant record of the node (ℱ ) and terminates if a clone of the same ant has already visited that node, preventing redundant exploration.
Trail laying As the query traverses the network, a backward ant is launched to retrace the route and update pheromone levels, reinforcing successful paths. The pheromone value at node is updated as: () ← () + , where = 0 + (1 − ) · 2·0 . Here, is the weighting factor (with = 0.5 in this study), is the number of matching triples, 0 = 10 and 0 = 3 are constants, and is the query response time. This ensures that the amount of pheromones is proportional to both the quality of the resources found and the eficiency of the path. Pheromone trails evaporate over time with an evaporation factor ∈ [0, 1), gradually removing less optimal paths: ( + 1) = ()(1 − ).
Hit Rate The global hit rate is a key performance metric as it reflects the proportion of matching nodes found on average. Long-time behavior shows that time-dependent hit rate reaches a steady state, ℎ := lim→∞⟨ℎ()⟩, where ⟨. . . ⟩ stands for the average over diferent simulation runs. In Figure 2 we report ℎ for two diferent matching node numbers: = 15 and = 60, with a total number of nodes = 150. For each of them we consider the curves ℎ( ) for selected values of evaporation coeficient : we consider three small values, = 0.009, 0.05, 0.1, one intermediate, = 0.5, and one large, = 0.9. For small values of , we see high hit rates, which increase only very slightly with and decrease steadily with . The behavior at intermediate values of is notable: it begins with low hit rates at (1) (2) small , but increases rapidly as the query frequency increases. At the largest , it exhibits quite large hit rates, comparable to low values. Then, as increases, the hit rate quickly drops. Further increase of leads to a steady growth of the hit rate, again associated with the crossing of a critical threshold. This drastic diference in ℎ( ) behavior can be explained if we refer to the characteristic time, = 1/, after which a significant quantity of the pheromone evaporates. For ≤ 0.1, it is ≥ 10 ticks, which is enough to traverse the largest distance in the network, = 5, twice. This ensures a stable pheromone network and good performance reflected in hit rate even for low query frequencies. However, for = 0.5, the characteristic time is = 2, which is small, but might be enough for the pheromones to stay on the short paths with the situation improving when the query frequency increases. For = 0.9 the characteristic time ≈ 1.11. This leads to a very quick pheromone evaporation. Higher frequencies are beneficial for the pheromone routes as they allow pheromone tables to be updated many times per time step to resist evaporation.
Forward Ants We measure the average number of forward ants () present in the system at each time step. This quantity serves as a proxy for network utilization, as each ant can be interpreted as a message sent between nodes. To make things comparable, we introduce relative number of forward ants, () := () , we normalize the number of forward ants () by the number of nodes and by query frequency . We measure the long-term average values of () and show them for diferent parameter values in Figure 3. The curves for small ≤ 0.1 values all follow each other at the value of ≈ 0.2 for = 15 and the value of ≈ 0.45 for = 60. This can be compared with a baseline value of / . For a small number of matching nodes, = 15, we see that the actual values of the forward ants are twice higher. For large = 60, the value of is much closer to the baseline. The intermediate value, = 0.5, shows a consistently small number of forward ants, which grows with . For the case of = 15, the ( ) values are still higher than the baseline. The behavior of the curve ( ) for the highest value of the evaporation coeficient, = 0.9, is the most peculiar. At first, we see a large number of forward ants, especially when is relatively small. Thus, one can speculate that the relatively higher hit rate for = 0.9 at low is connected to the fact that many forward ants are created, while it is relatively low for = 0.5, so there are very few forward ants. At low query frequency and large evaporation coeficient, we might see the behavior of the algorithm where it produces too many forward ants.
We follow [
/
Scalability, exhibits a diferent behavior for diferent sets of parameters (see Figure 4). We know that for low values, there is almost no dependence of ℎ on , so scalability stays around zero in p0.009 0.05 0.1 0.5 0.9
S iil,t y b a l a c S
S iil,t y b a l a c S this case. Since the system already performs well at low values of , increasing the query frequency does not produce significant performance gains. Furthermore, because nodes are assumed to have infinite processing capacity, higher values of do not lead to any performance degradation. For the intermediate value of = 0.5 we see that scalability goes above zero and in some cases even above one as increases highlighting the emergence of the pheromone routes which facilitate the search. For the highest value of the evaporation coeficient = 0.9, the picture is even more interesting. As we know, for very little values a large number of forward ants is present, resulting in relatively high values of ℎ and overall performance of the search algorithm. Thus, increasing marks a transition from many to few forward ants, while the routes are not stable enough to guide the ants. Then, with increasing , stable pheromone routes start to appear, and the scalability not only becomes positive but also > 1, indicating super-critical growth. For even higher values of , the scalability steadily approaches zero, which means that the system is reaching its peak performance.
In this work, we applied the Ant Colony Optimization (ACO) algorithm to the problem of searching in distributed knowledge graphs (DKGs) structured according to an edge–fog–cloud continuum. We demonstrated that in systems with infinite processing capacity, increasing the query frequency leads to more eficient pheromone trails and improved hit rates. In particular, in settings with a high evaporation coeficient, we observed an emergent scalability efect, where higher query frequency reinforced pheromone-based routing.
Future work will examine this hypothesis, along with the model’s robustness and fault tolerance, such as resilience to node or link failures or to errors in pheromone signal interpretation. Another key direction is the practical implementation of this search mechanism in real-world edge–cloud infrastructures. Our ongoing work focuses on implementing ACO using forward and backward ants as messages exchanged between nodes, dynamically updating local pheromone tables.
Funded by the European Union, project GLACIATION, by grant No. 101070141. Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union. Neither the European Union nor the granting authority can be held responsible for them.
The authors used ChatGPT for grammar and spelling checks. All content was subsequently reviewed and edited by the authors, who take full responsibility for the final publication.