Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.02683 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908687618015232 |
|---|---|
| author | Rodrigues, Luiz A. Duarte Jr., Elias P. Arantes, Luciana |
| author_facet | Rodrigues, Luiz A. Duarte Jr., Elias P. Arantes, Luciana |
| contents | The most common strategy for enabling a process in a distributed system to broadcast a message is one-to-all communication. However, this approach is not scalable, as it places a heavy load on the sender. This work presents an autonomic algorithm that enables the $n$ processes in a distributed system to build and maintain a spanning tree connecting themselves. In this context, processes are the vertices of the spanning tree. By definition, a spanning tree connects all processes without forming cycles. The proposed algorithm ensures that every vertex in the spanning tree has both an in-degree and the tree depth of at most $log_2 n$. When all processes are correct, the degree of each process is exactly $log_2 n$. A spanning tree is dynamically created from any source process and is transparently reconstructed as processes fail or recover. Up to $n-1$ processes can fail, and the correct processes remain connected through a scalable, functioning spanning tree. To build and maintain the tree, processes use the VCube virtual topology, which also serves as a failure detector. Two broadcast algorithms based on the autonomic spanning tree algorithm are presented: one for best-effort broadcast and one for reliable broadcast. Simulation results are provided, including comparisons with other alternatives. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02683 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed and Autonomic Minimum Spanning Trees Rodrigues, Luiz A. Duarte Jr., Elias P. Arantes, Luciana Distributed, Parallel, and Cluster Computing The most common strategy for enabling a process in a distributed system to broadcast a message is one-to-all communication. However, this approach is not scalable, as it places a heavy load on the sender. This work presents an autonomic algorithm that enables the $n$ processes in a distributed system to build and maintain a spanning tree connecting themselves. In this context, processes are the vertices of the spanning tree. By definition, a spanning tree connects all processes without forming cycles. The proposed algorithm ensures that every vertex in the spanning tree has both an in-degree and the tree depth of at most $log_2 n$. When all processes are correct, the degree of each process is exactly $log_2 n$. A spanning tree is dynamically created from any source process and is transparently reconstructed as processes fail or recover. Up to $n-1$ processes can fail, and the correct processes remain connected through a scalable, functioning spanning tree. To build and maintain the tree, processes use the VCube virtual topology, which also serves as a failure detector. Two broadcast algorithms based on the autonomic spanning tree algorithm are presented: one for best-effort broadcast and one for reliable broadcast. Simulation results are provided, including comparisons with other alternatives. |
| title | Distributed and Autonomic Minimum Spanning Trees |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2512.02683 |