Gathering in graphs

Checked against the full text of Dieudonné et al. 2014. Dieudonné, Pelc and Peleg note that \(f+2\) is a new threshold for tolerating \(f\) Byzantine entities, next to \(f+1\) for communication through a cut and \(2f+1\) processors for consensus in a complete network.

Hirose, Eguchi and Sudo Hirose et al. 2025 show that the algorithms of Dieudonné et al. 2014 need what they know: with none of \(n\), \(k\), \(f\) and the length of the largest label of a good agent known, no number of good agents can gather and stop (Theorem 3.1). Their agents are those of Dieudonné et al. 2014: unique labels, no marks on nodes, agents at the same node read each other's state and a Byzantine agent shows the same state to all of them, and the adversary wakes agents at different times. They also study self-stabilizing gathering, where every agent starts in an arbitrary, possibly corrupted, memory state: it is impossible when \(k \le 2f\), even with \(n\), \(k\), \(f\) and the length of the largest label of a good agent known (Theorem 3.2). For the relaxed goal of perpetual gathering, in which from some round on all good agents are always at the same node (they may keep moving together and never stop), they give a self-stabilizing algorithm for every \(k\) and \(f\) that knows upper bounds on \(n\) (namely \(N\)), \(k\) and \(f\) and the length of the largest label of a good agent; its time is proportional to the product of the bounds on \(k\) and \(f\) times the time of the rendezvous algorithm of Ta-Shma and Zwick Ta-Shma & Zwick 2014 for labels of that length, that is \(\tilde O(N^5)\) times that length (Theorem 4.1; Section 5 removes the simultaneous start). Without self-stabilization, perpetual gathering needs no knowledge: removing termination from the algorithm of Dieudonné et al. 2014 suffices, as observed in Hirose et al. 2025. Checked against the full text of Hirose et al. 2025 (arXiv v1).