System-Wide Termination in Distributed Betweenness Centrality Computation

Giuseppe Di Fatta; Lucia Cavallaro; Siamak Abdi

REVIEW 3 major objections 5 minor 13 references

A lightweight global termination detector lets distributed betweenness computation stop at true system-wide convergence, not at each vertex's own apparent stability.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 06:23 UTC pith:6WU2RBWQ

load-bearing objection Plausible global termination layer for distributed BC, but safety is empirically demonstrated, not proven; deserves a serious referee if the team is willing to tighten the central claim. the 3 major comments →

arxiv 2607.29474 v1 pith:6WU2RBWQ submitted 2026-07-31 cs.DC

System-Wide Termination in Distributed Betweenness Centrality Computation

Siamak Abdi , Lucia Cavallaro , Giuseppe Di Fatta This is my paper

classification cs.DC MSC 68M1468R10

keywords betweenness centralityglobal termination detectiondistributed graph algorithmsgossip aggregationlocal convergencedistance-vector algorithmsoverlay networkpremature termination

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tackles a blind spot in distributed betweenness centrality: vertices often halt as soon as their own estimate stops changing, but shortest-path dependency information may still be propagating elsewhere in the network. The authors add a parallel, lightweight termination layer in which vertices gossip a pair of counters whose ratio estimates the number of locally converged vertices, and stop only when that ratio is within a tolerance of the known network size for several consecutive phases. A custom event-driven simulator on synthetic and real graphs shows that local stopping yields non-zero final error, while the global condition stops later and keeps the final betweenness error at zero. The paper argues this gives distributed betweenness algorithms an explicit, coordinated halting condition without modifying the underlying computation.

Core claim

The paper's central claim is that safe termination of distributed betweenness centrality cannot be decided from a single vertex's local stability: a vertex whose estimate is stable may still be needed by others, or may later receive new dependency information. The proposed termination layer lets every vertex decide when the whole system has converged by running a push-pull gossip aggregation of the number of vertices that have reported local stabilisation, and only then halting. In the evaluated networks, following this global condition instead of stopping at local stability gives zero final relative L2 error, whereas local stopping gives non-zero errors on every tested graph, including a re

What carries the argument

The detector is built on a (v, w) pair maintained by every vertex: the seed starts with w=1, and in each phase a vertex halves its pair, pushes it to a random peer, pulls the peer's pair, and adds the received values. The ratio v/w aggregates toward the number of vertices that have entered LOCAL CONVERGENCE, and GLOBAL CONVERGENCE is declared when |N - v/w| / N is within epsilon for MIN consecutive phases. This machinery converts a purely local stability signal into a system-wide stopping decision using only constant-size messages and O(1) state per vertex, and it runs in parallel with the baseline distance-vector betweenness algorithm.

Load-bearing premise

The load-bearing premise is that a vertex whose betweenness estimate has changed by less than epsilon for MIN consecutive phases can be counted as converged; the paper does not prove that such a temporarily stable vertex cannot later receive new dependency information through other parts of the network.

What would settle it

On a long chain graph, run the distance-vector betweenness computation with the termination layer and freeze a vertex's estimate after its first MIN stable phases while a dependency wave is still propagating toward it from the far end; if the global condition triggers before that wave arrives and the final relative L2 error is non-zero, the detector's convergence criterion is unsound. The paper's own geometric-graph case, where the termination layer did not converge under physical-neighbour communication within the simulation budget, marks the edge of the claimed regime.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

Distributed betweenness implementations that currently stop at fixed rounds or local inactivity can be retrofitted with this termination layer, removing premature-termination error without changing the core algorithm.
The layer adds at most 2N constant-size logical messages per phase across N active vertices, a small and bounded overhead compared with running extra phases after convergence.
Under overlay communication, the detector reaches global convergence in fewer phases than under physical-neighbour diffusion on every tested graph, so overlay routing can cut stopping latency on slowly mixing or high-diameter networks.
Local stopping is unsafe across all four evaluated graph families, producing non-zero final error in every case, while global stopping yields zero final error.
A correctly detected global stop lets all vertices halt together, eliminating post-convergence message exchanges in bandwidth-limited settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same (v, w) gossip termination layer could be grafted onto other iterative distributed algorithms that expose a local-stability predicate, such as distributed PageRank or label propagation, since the mechanism is not tied to betweenness math.
The paper evaluates a single epsilon-MIN setting; sweeping these parameters would reveal a tradeoff between premature-declaration risk and stopping latency, and would test how robust the zero-error result is.
Under the overlay model, termination detection can outpace physical-neighbour propagation of betweenness messages, so a deployment using overlay gossip should model hop-level transmission cost, which the paper explicitly leaves as deployment-dependent.
The authors themselves limit the claim to stable networks with reliable delivery and fixed N; extending the detector to churn, message loss, or a changing N would require retransmission, membership updates, and dynamic adjustment of N.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Plausible global termination layer for distributed BC, but safety is empirically demonstrated, not proven; deserves a serious referee if the team is willing to tighten the central claim.

read the letter

The paper adds a gossip-based global termination detector to Crescenzi et al.'s distance-vector betweenness centrality algorithm. That is actually new relative to the cited literature, and the empirical comparison against local stopping is a useful, honest contribution: it shows that local convergence on heterogeneous graphs leaves real residual error, while the global rule keeps zero error on the four tested networks. The problem is well motivated, the overhead analysis is straightforward, and the code is public. Credit where it's due: this is a modest but sensible piece of engineering.

The soft spot is load-bearing. The safety of the stopping rule rests on two assertions that the paper does not prove. First, that a vertex whose BC estimate stays within epsilon for MIN phases will not change later. In a distance-vector computation, dependency updates propagate in a second wave from leaves upward, and a plateau of five phases can easily be transient. Second, the global trigger only requires v/w to be within epsilon of N, so with epsilon=0.05 it can fire while up to 5% of vertices have not even reported local convergence. If those vertices still need messages from vertices that have already stopped, the premature-termination error the paper claims to prevent can reappear. Section IV-B's statement that transient delays only postpone termination is not generally true for that reason. The zero-error result is an observation on four small graphs with hand-picked thresholds, not a consequence of the proposed condition.

That said, this is not a fatal flaw in the sense of the paper being incoherent. It is an unproven central claim, and the evaluation lacks repeated runs, confidence intervals, or sensitivity analysis. A referee should ask for either a formal correctness argument for the stopping condition under the stated model, or a much more thorough empirical study (multiple seeds, varying epsilon and MIN, larger and more varied graphs, message delays) with error statistics. The paper is preliminary but points at a real failure mode, and the approach is plausible. I would send it to peer review, but I would not accept it as is.

This is a paper for people working on distributed graph algorithms and termination detection. It won't reshape the field, but it is a legitimate contribution if the authors can back up the safety claim. I would bring it to a reading group only for the discussion of what counts as a proof of convergence in this setting. I would not cite it in my own work yet. The code availability and the clear problem statement make it worth engaging with, and the serious thinker flag is deserved: the authors are honestly identifying a gap, even if their solution is not yet fully justified.

Recommendation: engage with it, but demand rigor on the termination condition before believing the headline.

Referee Report

3 major / 5 minor

Summary. The paper proposes a lightweight, fully distributed global termination detection layer for distance-vector-based distributed betweenness centrality computation. Each vertex monitors whether its own betweenness estimate has been stable for MIN consecutive phases, and a peer-sampling aggregation (v/w) is used to estimate the number of locally converged vertices. When this aggregate is within epsilon of the known network size N for MIN consecutive phases, vertices declare global convergence and stop. The authors evaluate this global stopping rule against a local stopping rule using a custom Python simulator on four graphs (ER, Geometric, Email, Road), reporting zero final relative L2 error under global termination and nonzero error under local termination. The paper argues that local convergence is unsafe and that the proposed global condition provides an explicit, safe system-wide stopping point.

Significance. If the safety claim were established, the contribution would be practically useful: it adds a constant-size-message termination layer on top of an existing distributed betweenness algorithm, without modifying the core computation, and it gives vertices an explicit stopping signal rather than relying on fixed round bounds or local inactivity. The paper also provides a reproducible simulator and uses an external ground-truth source (NetworkX), which is a strength. However, the central claim that the detected condition guarantees exact betweenness is not proven; it is supported only by a correctness intuition and an empirical evaluation on four small graphs with hand-picked thresholds. The gap between what is asserted ('explicit globally safe stopping condition') and what is demonstrated (zero error in the evaluated simulations) is load-bearing, because the safety of the stopping rule is the entire contribution.

major comments (3)

[Section IV-B and Algorithm 1 (lines 17-19, 23)] The safety of the global termination rule is not proven. The algorithm declares local convergence when a vertex's betweenness estimate has changed by less than epsilon for MIN phases, and global convergence when |N - v/w|/N <= epsilon for MIN phases. The paper states in Section IV-B that transient delays 'only postpone the dissemination of convergence information,' but this is not generally true: in a distance-vector betweenness computation, dependency contributions from distant targets propagate in a second wave from the leaves of the shortest-path DAG. A vertex can sit on a plateau for several phases while that wave is still in transit and then receive a delayed dependency update that changes its estimate. A local-stability plateau is therefore at best a heuristic, not a finality certificate. Since the paper's central claim is that the detector lets vertices 'stop safely,' the missing
[Section V, Table I and Eq. (4)] The empirical support for safety is limited. The experiments use a single hand-picked epsilon=0.05 and MIN=5, with no repeated runs, no confidence intervals, and only four graphs. Because the termination condition is |N-v/w|/N <= 0.05, the detector can fire when up to roughly 5% of vertices have not even reported local convergence, and delayed dependency messages can pass the detection point in exactly the scenario the paper aims to prevent. The zero final errors in Table I are observations on these four instances, not consequences of a proved invariant. To support the safety claim, the authors should either prove an invariant relating the termination condition to actual convergence of the betweenness estimates, or provide a systematic sensitivity analysis and repeated trials showing the zero-error behavior is robust across threshold choices and graph families.
[Section IV-A and references [11]-[13]] The termination layer's aggregation behaviour is taken on faith from prior self-cited works [11]-[13] without stating the conditions under which v/w converges to the number of locally converged vertices. The algorithm halves and adds (v,w) on random peer interactions under asynchronous message delays; no correctness proof is given for this gossip process in the present setting, and no formal relationship is established between the aggregate ratio v/w and the true count of converged vertices. If the aggregation can underestimate or overestimate the converged count at the moment of detection, the global condition in Algorithm 1 is not reliable. This is closely related to the safety gap above and should be addressed as part of the formal analysis.

minor comments (5)

[Abstract] The name 'Erd ˝os–R´enyi' contains a corrupted character ('˝o' instead of 'ő').
[Algorithm 1] The Require line mentions STABLE_i but the procedure does not define how STABLE_i is computed; the experimental section states that stability means a change of less than epsilon for MIN consecutive phases, but this definition should appear in the algorithm or in Section IV-A, not only in Section V.
[Section IV-B] The text says that when v/w matches N, global convergence is declared, but Algorithm 1 and the experiments use the tolerance |N-v/w|/N <= epsilon. This discrepancy should be stated explicitly in the prose.
[Section V] Figures 1-4 are referenced but not shown in the text provided; the authors should ensure the figure captions and axes clearly distinguish local and global scenarios, and report the evolution of v/w as well as the error.
[Section IV-A] The statement 'In the proposed approach, whenever a vertex reaches a local convergence, it increments v by 1 in Algorithm 1' conflicts with Algorithm 1, where v is incremented by 1 only in the 'LOCAL CONVERGENCE' branch after the state transition; clarify the exact update rule.

Circularity Check

0 steps flagged

No significant circularity: the central zero-error claim is an empirical result validated against external NetworkX ground truth, not a reduction to fitted inputs, definitional identities, or a self-citation chain.

full rationale

The paper's central claim is that a gossip-based global termination detector stops the distributed betweenness computation with zero final error on the evaluated graphs. The error is measured against ground truth from NetworkX, an independent external benchmark, and no parameter is fitted to the data and then renamed as a prediction. The thresholds epsilon=0.05 and MIN=5 are fixed experimental settings, not fitted values. The termination condition v/w ≈ N is an aggregation of local-stability flags, and the paper presents an intuitive correctness argument but does not derive safety from a self-citation. The cited previous works [11]-[13] are used as inspiration for the epidemic aggregation mechanism, not as a load-bearing proof that local stability implies final correctness. The genuine weakness—that local stability for MIN phases is not proven to imply terminal convergence—is a correctness/validation gap, not a circular reduction: the global condition is not defined in terms of the final betweenness estimate, nor is the claimed zero error built into the algorithm's equations. Persistent message loss and the slow physical-neighbour diffusion on the Geometric graph are acknowledged limitations but do not indicate circularity. Therefore the derivation is self-contained with respect to circularity concerns.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 0 invented entities

The central result rests on a small number of hand-chosen tolerances and on inherited assumptions about gossip convergence and the semantics of local stability. No new physical or formal entities are introduced; the termination layer is a software component.

free parameters (4)

epsilon = 0.05
Tolerance for both local stability and the global convergence condition; set by hand with no sensitivity analysis, directly determines when vertices are declared converged.
MIN = 5
Number of consecutive stable phases required to declare local/global convergence; set by hand; affects stopping phase and final error.
phase_period = 1 s
Simulator phase duration; chosen for the experiments; affects phase counts but not the core algorithmic logic.
message_delay = 100 ms
Per-message delay in the event-driven simulator; chosen, and no sensitivity analysis is reported.

axioms (5)

domain assumption Reliable message delivery, no persistent message loss, and no node churn
Stated in Section IV-B as required for the aggregated estimate to remain accurate; these conditions are not handled by the algorithm.
domain assumption Each vertex knows the network size N
Used in the global condition |N - v/w| / N <= epsilon; stated in Section IV-A.
domain assumption The push-pull gossip protocol converges to the number of locally-converged vertices
Inherited from the authors' earlier epidemic aggregation results [11]-[13]; no proof is given in this paper for this specific setting.
ad hoc to paper Local stability for MIN phases implies the betweenness estimate is final
Algorithm 1 increments v when this condition holds; if it is false, the global detector could declare convergence while some estimates are still changing.
domain assumption The baseline distributed BC algorithm by Crescenzi et al. computes exact betweenness when run to convergence
The paper builds on this algorithm without re-deriving its correctness, treating it as a sound substrate.

pith-pipeline@v1.3.0-daily-deepseek · 8447 in / 9532 out tokens · 102746 ms · 2026-08-03T06:23:16.582447+00:00 · methodology

0 comments

read the original abstract

Computing betweenness centrality on large networks is inherently expensive, as it requires aggregating shortest-path dependencies across all pairs of vertices and becomes increasingly difficult to scale as network size grows. Scalable distributed algorithms can facilitate such computations, particularly when centralised processing is not feasible, and message exchanges must be carefully controlled, for example, in bandwidth-limited or very large-scale networks. However, existing distributed betweenness centrality implementations do not integrate a lightweight, system-wide termination detector. As a consequence, this can lead to extra messaging after local convergence or, if misconfigured, premature stops. In this work, a lightweight, system-wide global termination detection algorithm for this task is presented. The proposed method enables vertices to decide locally when the overall system has converged. The method is evaluated against a local stopping strategy in which vertices terminate individually once their own estimates stabilise. To compare these two approaches, namely global termination detection and local stopping, a custom Python simulator is implemented, and both approaches are tested on synthetic (Erdos-Renyi and geometric) and real (Email and Road) network topologies. Our results show that system-wide termination detection lets vertices stop safely after detecting global convergence, as indicated by zero final error in the evaluated networks, rather than stopping independently based only on local convergence. The local stopping approach, on the other hand, results in premature termination and some errors on heterogeneous networks. This work emphasises the need for coordinated halting in distributed centrality computation.

Figures

Figures reproduced from arXiv: 2607.29474 by Giuseppe Di Fatta, Lucia Cavallaro, Siamak Abdi.

**Figure 2.** Figure 2: Comparison of global betweenness centrality error between local and global scenarios for [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Comparison of global betweenness centrality error between local and global scenarios for the [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 4.** Figure 4: Comparison of global betweenness centrality error between local and global scenarios for the [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 2 linked inside Pith

[1]

A faster algorithm for betweenness centrality,

U. Brandes, “A faster algorithm for betweenness centrality,”Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163–177, 2001

2001
[2]

Centrality measures in complex networks: A survey,

A. Saxena, S. Iyengaret al., “Centrality measures in complex networks: A survey,”arXiv:2011.07190, 2020

Pith/arXiv arXiv 2011
[3]

Simple and fast distributed computation of betweenness centrality,

P. Crescenzi, P. Fraigniaud, and A. Paz, “Simple and fast distributed computation of betweenness centrality,” inIEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 337–346

2020
[4]

K. A. Lehmann and M. Kaufmann,Decentralized algorithms for evaluating centrality in complex networks. Universit ¨atsbibliothek T¨ubingen T ¨ubingen, Germany, 2003

2003
[5]

Nearly optimal distributed algorithm for computing betweenness centrality,

Q.-S. Hua, H. Fan, M. Ai, L. Qian, Y . Li, X. Shi, and H. Jin, “Nearly optimal distributed algorithm for computing betweenness centrality,” in 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2016, pp. 271–280

2016
[6]

Distributed algorithms for directed betweenness centrality and all pairs shortest paths,

M. Pontecorvi and V . Ramachandran, “Distributed algorithms for directed betweenness centrality and all pairs shortest paths,”arXiv preprint arXiv:1805.08124, 2018

Pith/arXiv arXiv 2018
[7]

Termination detection for diffusing computations,

E. W. Dijkstra and C. S. Scholten, “Termination detection for diffusing computations,”Information Processing Letters, vol. 11, no. 1, pp. 1–4, 1980

1980
[8]

Algorithms for distributed termination detection,

F. Mattern, “Algorithms for distributed termination detection,” Distributed computing, vol. 2, no. 3, pp. 161–175, 1987

1987
[9]

On a routing problem,

R. Bellman, “On a routing problem,”Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87–90, 1958

1958
[10]

D. P. Bertsekas and R. G. Gallager,Data Networks, 2nd ed. Prentice Hall, 1992, see §5.2.4: Distributed Asynchronous Bellman–Ford Algorithm

1992
[11]

Agreement in epidemic information dissemination,

M. Ayiad, A. Katti, and G. Di Fatta, “Agreement in epidemic information dissemination,” inInternet and Distributed Computing Systems: 9th International Conference, IDCS 2016, Wuhan, China, September 28-30, 2016, Proceedings 9. Springer, 2016, pp. 95–106

2016
[12]

Blockchain epidemic consensus for large-scale networks,

S. Abdi, G. Di Fatta, A. Badii, and G. Fortino, “Blockchain epidemic consensus for large-scale networks,” in2025 7th International Conference on Blockchain Computing and Applications (BCCA). IEEE, 2025, pp. 562–569

2025
[13]

Fully decentralised consensus for extreme-scale blockchain,

S. Abdi, G. Di Fatta, A. Badii, and G. Fortino, “Fully decentralised consensus for extreme-scale blockchain,” in2025 IEEE Global Blockchain Conference (GBC). IEEE, 2025, pp. 1–8

2025

[1] [1]

A faster algorithm for betweenness centrality,

U. Brandes, “A faster algorithm for betweenness centrality,”Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163–177, 2001

2001

[2] [2]

Centrality measures in complex networks: A survey,

A. Saxena, S. Iyengaret al., “Centrality measures in complex networks: A survey,”arXiv:2011.07190, 2020

Pith/arXiv arXiv 2011

[3] [3]

Simple and fast distributed computation of betweenness centrality,

P. Crescenzi, P. Fraigniaud, and A. Paz, “Simple and fast distributed computation of betweenness centrality,” inIEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 337–346

2020

[4] [4]

K. A. Lehmann and M. Kaufmann,Decentralized algorithms for evaluating centrality in complex networks. Universit ¨atsbibliothek T¨ubingen T ¨ubingen, Germany, 2003

2003

[5] [5]

Nearly optimal distributed algorithm for computing betweenness centrality,

Q.-S. Hua, H. Fan, M. Ai, L. Qian, Y . Li, X. Shi, and H. Jin, “Nearly optimal distributed algorithm for computing betweenness centrality,” in 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2016, pp. 271–280

2016

[6] [6]

Distributed algorithms for directed betweenness centrality and all pairs shortest paths,

M. Pontecorvi and V . Ramachandran, “Distributed algorithms for directed betweenness centrality and all pairs shortest paths,”arXiv preprint arXiv:1805.08124, 2018

Pith/arXiv arXiv 2018

[7] [7]

Termination detection for diffusing computations,

E. W. Dijkstra and C. S. Scholten, “Termination detection for diffusing computations,”Information Processing Letters, vol. 11, no. 1, pp. 1–4, 1980

1980

[8] [8]

Algorithms for distributed termination detection,

F. Mattern, “Algorithms for distributed termination detection,” Distributed computing, vol. 2, no. 3, pp. 161–175, 1987

1987

[9] [9]

On a routing problem,

R. Bellman, “On a routing problem,”Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87–90, 1958

1958

[10] [10]

D. P. Bertsekas and R. G. Gallager,Data Networks, 2nd ed. Prentice Hall, 1992, see §5.2.4: Distributed Asynchronous Bellman–Ford Algorithm

1992

[11] [11]

Agreement in epidemic information dissemination,

M. Ayiad, A. Katti, and G. Di Fatta, “Agreement in epidemic information dissemination,” inInternet and Distributed Computing Systems: 9th International Conference, IDCS 2016, Wuhan, China, September 28-30, 2016, Proceedings 9. Springer, 2016, pp. 95–106

2016

[12] [12]

Blockchain epidemic consensus for large-scale networks,

S. Abdi, G. Di Fatta, A. Badii, and G. Fortino, “Blockchain epidemic consensus for large-scale networks,” in2025 7th International Conference on Blockchain Computing and Applications (BCCA). IEEE, 2025, pp. 562–569

2025

[13] [13]

Fully decentralised consensus for extreme-scale blockchain,

S. Abdi, G. Di Fatta, A. Badii, and G. Fortino, “Fully decentralised consensus for extreme-scale blockchain,” in2025 IEEE Global Blockchain Conference (GBC). IEEE, 2025, pp. 1–8

2025