Locating a black hole in a dynamic ring
Bibliographic record
Abstract
In networked environments supporting mobile agents , a pressing problem is the presence of network sites harmful for the agents. In this paper we consider the danger posed by a node that destroys any incoming agent without leaving any trace. Such a dangerous node is known in the literature as a black hole ( Bh ). The problem of a team of system agents determining its location, known as black hole search ( Bhs ), has been extensively studied in the literature under a variety of assumptions, both in synchronous and asynchronous settings. The main complexity parameter of Bhs is the number of system agents (called size ) needed to solve the problem; other parameters are the number of moves (called cost ) performed by the agents, and the time until termination. In the existing literature, with only a couple of exceptions, all results are based on a common assumption that the network is static , i.e. its topology does not change in time. We consider instead the Bhs when the network is dynamic : the link structure of the graph changes over time. While time-varying graphs have been the focus of intense research in the last two decades, very little is known on the problem of locating the Bh in such networks. In this paper, we contribute to fill this research gap by studying Bhs in dynamic ring networks, focusing on the 1-interval connectivity adversarial dynamics. Feasibility and complexity of the problem depend on many factors, specifically on the size n of the ring, whether or not n is known, and the type of inter-agent communication (whiteboards, tokens, face-to-face, visual). In this paper, we provide a complete feasibility characterization presenting size optimal algorithms. Furthermore, we establish lower bounds on the cost and time of size-optimal solutions and show that our algorithms achieve those bounds.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.007 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.000 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.001 | 0.004 |
| Open science | 0.001 | 0.003 |
| Research integrity | 0.002 | 0.001 |
| Insufficient payload (model declined to judge) | 0.003 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".