𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A self-stabilizing algorithm for the shortest path problem in a distributed system

✍ Scribed by Tetz C. Huang; Ji-Cherng Lin

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
352 KB
Volume
43
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded function technique.

πŸ“œ SIMILAR VOLUMES

A self-stabilizing algorithm for the sho
A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
✍ Tetz C. Huang πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 1015 KB

Shortest path finding has a variety of applications in transportation and communication. In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The prevlotm works on this topic had two assumptions that can be relaxed in this paper.

A self-stabilizing distributed algorithm
A self-stabilizing distributed algorithm for minimal spanning tree problem in a symmetric graph
✍ G. Antonoiu; P.K. Srimani πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 640 KB

Minimal Spanning Tree (MST) problem in an arbitrary undirected graph is an important problem in graph theory and has extensive applications. Numerous algorithms are available to compute an MST. Our purpose here is to propose a self-stabilizing distributed algorithm for the MST problem and to prove i

A fully dynamic algorithm for distribute
A fully dynamic algorithm for distributed shortest paths
✍ Serafino Cicerone; Gabriele Di Stefano; Daniele Frigioni; Umberto Nanni πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 297 KB

We propose a fully dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If is the number of pairs of nodes changing the distance after a single edge modiΓΏcation (insert, delete, weight decrease, or weight increase) then the messa

An Incremental Algorithm for a Generaliz
An Incremental Algorithm for a Generalization of the Shortest-Path Problem
✍ G. Ramalingam; Thomas Reps πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 363 KB

The grammar problem, a generalization of the single-source shortest-path prob-Ž Ž . Ž . . lem introduced by D. E. Knuth Inform. Process. Lett. 6 1 1977 , 1᎐5 is to compute the minimum-cost derivation of a terminal string from each nonterminal of a given context-free grammar, with the cost of a deriv