Four Shades of Deterministic Leader Election in Anonymous Networks
Bibliographic record
Abstract
Leader election is one of the fundamental problems in distributed computing: a single node, called the leader, must be specified. This task can be formulated either in a weak way, where one node outputs 'leader' and all other nodes output 'non-leader', or in a strong way, where all nodes must also learn which node is the leader. If the nodes have distinct identifiers, then such an agreement means that all nodes have to output the identifier of the elected leader. For anonymous networks, the strong version of leader election requires that all nodes must be able to find a path to the leader, as this is the only way to identify it. In this paper, we study variants of deterministic leader election in arbitrary anonymous networks. Leader election is impossible in some anonymous networks, regardless of the allocated amount of time, even if nodes know the entire map of the network. This is due to possible symmetries in the network. However, even in networks in which it is possible to elect a leader knowing the map, the task may be still impossible without any initial knowledge, regardless of the allocated time. On the other hand, for any network in which leader election (weak or strong) is possible knowing the map, there is a minimum time, called the 'election index', in which this can be done. We consider four formulations of leader election discussed in the literature in the context of anonymous networks : one is the weak formulation, and the three others specify three different ways of finding the path to the leader in the strong formulation. Our aim is to compare the amount of initial information needed to accomplish each of these "four shades" of leader election in minimum time. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire network. The length of this string is called the size of advice. We show that the size of advice required to accomplish leader election in the weak formulation in minimum time is exponentially smaller than that needed for any of the strong formulations. Thus, if the required amount of advice is used as a measure of the difficulty of the task, the weakest version of leader election in minimum time is drastically easier than any version of the strong formulation in minimum time.
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.004 | 0.011 |
| Meta-epidemiology (narrow) | 0.001 | 0.000 |
| Meta-epidemiology (broad) | 0.001 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.002 | 0.005 |
| Scholarly communication | 0.003 | 0.007 |
| Open science | 0.002 | 0.003 |
| Research integrity | 0.002 | 0.003 |
| Insufficient payload (model declined to judge) | 0.003 | 0.001 |
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".