Studies of interconnection networks with applications in broadcasting
Bibliographic record
Abstract
The exponential growth of interconnection networks transformed the communication primitives into an important area of research. One of these primitives is the one-to-all communication, i.e. broadcasting. Its presence in areas such as static and mobile networks, Internet messaging, supercomputing, multimedia, epidemic algorithms, replicated databases, rumors and virus spreading, to mention only a few, shows the relevance of this primitive. In this thesis we focus on the study of interconnection networks from the perspective of two main problems in broadcasting: the minimum broadcast time problem and the minimum broadcast graph problem. Both problems are discussed under the 1-port constant model, which assumes that each node of the network can communicate with only one other node at a time and the transmitting time is constant, regardless of the size of the message. In the first part we introduce the minimum broadcast time function and we present two new properties of this function. One of the properties yields an iterative heuristic for the minimum broadcast time problem, which is the first iterative approach in approximating the broadcast time of an arbitrary graph. In the second part we give exact upper and lower bounds for the number of broadcast schemes in graphs. We also propose an algorithm for enumerating all the broadcast schemes and a random algorithm for broadcasting. In the third part we present a study of the spectra of Knödel graph and their applications. This study is motivated by the fact that, among the three known infinite families of minimum broadcast graphs, namely the hypercube, the recursive circulant, and the Knödel graph, the last one has the smallest diameter. In the last part we introduce a new measure for the fault tolerance of an interconnection network, which we name the global fault tolerance. Based on this measure, we make a comparative study for the above mentioned classes of minimum broadcast graphs, along with other classes of graphs with good communication properties.
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.001 | 0.001 |
| Meta-epidemiology (broad) | 0.000 | 0.001 |
| Bibliometrics | 0.001 | 0.003 |
| Science and technology studies | 0.001 | 0.002 |
| Scholarly communication | 0.002 | 0.003 |
| Open science | 0.001 | 0.001 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.004 | 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".