Cargando…
A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks
The purpose of the paper is to present the first self-stabilizing algorithm for finding [Formula: see text] one-to-many node-disjoint paths in message passing model. Two paths in a network are said to be node disjoint if they do not share any nodes except for the endpoints. Our proposed algorithm wo...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7276262/ http://dx.doi.org/10.1007/978-3-030-50323-9_12 |
_version_ | 1783542925344374784 |
---|---|
author | Hadid, Rachid Villain, Vincent |
author_facet | Hadid, Rachid Villain, Vincent |
author_sort | Hadid, Rachid |
collection | PubMed |
description | The purpose of the paper is to present the first self-stabilizing algorithm for finding [Formula: see text] one-to-many node-disjoint paths in message passing model. Two paths in a network are said to be node disjoint if they do not share any nodes except for the endpoints. Our proposed algorithm works on n-dimensional star networks [Formula: see text]. Given a source node s and a set of [Formula: see text] of [Formula: see text] destination nodes in the n-dimensional star network, our algorithm constructs [Formula: see text] node-disjoints paths [Formula: see text], where [Formula: see text] is a path from s to [Formula: see text], [Formula: see text]. Since the proposed solution is self-stabilizing [7], it does not require initialization and withstands transient faults. The stabilization time of our algorithm is [Formula: see text] rounds. |
format | Online Article Text |
id | pubmed-7276262 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
record_format | MEDLINE/PubMed |
spelling | pubmed-72762622020-06-08 A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks Hadid, Rachid Villain, Vincent Distributed Applications and Interoperable Systems Article The purpose of the paper is to present the first self-stabilizing algorithm for finding [Formula: see text] one-to-many node-disjoint paths in message passing model. Two paths in a network are said to be node disjoint if they do not share any nodes except for the endpoints. Our proposed algorithm works on n-dimensional star networks [Formula: see text]. Given a source node s and a set of [Formula: see text] of [Formula: see text] destination nodes in the n-dimensional star network, our algorithm constructs [Formula: see text] node-disjoints paths [Formula: see text], where [Formula: see text] is a path from s to [Formula: see text], [Formula: see text]. Since the proposed solution is self-stabilizing [7], it does not require initialization and withstands transient faults. The stabilization time of our algorithm is [Formula: see text] rounds. 2020-05-15 /pmc/articles/PMC7276262/ http://dx.doi.org/10.1007/978-3-030-50323-9_12 Text en © IFIP International Federation for Information Processing 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic. |
spellingShingle | Article Hadid, Rachid Villain, Vincent A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks |
title | A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks |
title_full | A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks |
title_fullStr | A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks |
title_full_unstemmed | A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks |
title_short | A Self-stabilizing One-To-Many Node Disjoint Paths Routing Algorithm in Star Networks |
title_sort | self-stabilizing one-to-many node disjoint paths routing algorithm in star networks |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7276262/ http://dx.doi.org/10.1007/978-3-030-50323-9_12 |
work_keys_str_mv | AT hadidrachid aselfstabilizingonetomanynodedisjointpathsroutingalgorithminstarnetworks AT villainvincent aselfstabilizingonetomanynodedisjointpathsroutingalgorithminstarnetworks AT hadidrachid selfstabilizingonetomanynodedisjointpathsroutingalgorithminstarnetworks AT villainvincent selfstabilizingonetomanynodedisjointpathsroutingalgorithminstarnetworks |