Tarry’s Algorithm and Consistency in Tree-like DistributedSystems

Анотація

In distributed systems, efficient and predictable network traversal is critical for coor-
dination, broadcasting, and maintaining data consistency between nodes. This paper
examines the behavior of Tarry’s traversal algorithm in tree-like undirected networks
under varying workloads, with a specific focus on consistency. Using simulated environ-
ments with 10, 100, and 1000 nodes, we initiated multiple transaction waves (T = 2,
5, 10) to evaluate the algorithm’s ability to support consistent data propagation. Our
results show that while Tarry’s algorithm, due to its cycle-free and deterministic nature,
ensures that all nodes are visited without duplication or omission, it alone is insuffi-
cient to guarantee data consistency. Although it provides a reliable traversal foundation,
maintaining complete consistency in tree-like distributed systems requires additional syn-
chronization or coordination mechanisms to ensure consistency. These findings highlight
the strengths and limitations of the algorithm in supporting consistent state propagation
in distributed environments.