Distributed six-cycle detection

Six computers connected in a ring A–B–C–D–E–F–A form a six-cycle: a closed route using six different computers. Adding a link A–D does not remove it. How quickly can computers discover whether a large network contains such a ring when no one starts with the whole map and each link carries only a short message per step?

The computers can calculate freely, but finding the ring requires exchanging information. One computer noticing a present ring is enough; there must be no false alarm on a network without one. A triangle walked twice revisits its three computers, so it is not the required six-cycle.[1]

Can a distributed network detect a six-computer ring with substantially fewer communication rounds than the known guarantee, or do some networks force that many? A ring on A through F remains a six-cycle after adding chord A–D; revisiting a triangle twice does not qualify. These examples fix what is detected, not its worst-case communication cost.

Let $T_6(n)$ be the smallest worst-case round bound for six-cycle detection in connected simple n-node classical CONGEST networks. Nodes initially know their own polynomial-range unique identifier and n; each edge carries $O(\log n)$ bits per synchronous round and local computation is unrestricted. Randomized algorithms may err with probability at most one-third on each graph. The known deterministic $O(n^{2/3})$ guarantee is the k=3 instance of the cited even-cycle theorem; optimality in this ordinary model remains the question.[1]

An algorithm can solve this in about n to the power two-thirds communication rounds for a network of n computers. We do not know whether a better classical algorithm is possible or whether some networks inherently require that many rounds.[1]

The remaining question is whether classical bounded-error CONGEST requires n^(2/3) rounds up to polylogarithmic factors, or permits a polynomial improvement. Detection is weaker than listing every cycle, and ordinary CONGEST is more permissive than broadcast CONGEST. Quantum communication and centralized graph algorithms change the model and cannot supply the requested classical bound.[1]

The loop is small, but evidence about it may be scattered across a large network. This gives a concrete way to study how limited communication restricts distributed computation, even when each computer can perform as much local calculation as it wants.[1]

The algorithm distinguishes sparse local neighborhoods from situations where accumulated density certifies a cycle, while filtering path information to limit congestion. Optimality requires showing whether that volume of information is unavoidable. This connects graph structure with communication lower bounds rather than with the processor time needed to examine a centrally stored graph.[1]