消息
	loading

A-Z
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- X
- Y
- Z
- 0-9
Classification
Publication

- Full text
- Title
- Author
- ISBN/ISSN
- Publisher
AdvancedSearch
- AdvancedSearch
- Search help

Scalable Self-Stabilization

Author： Ghosh S. He X.

Publisher： Academic Press

ISSN： 0743-7315

Source： Journal of Parallel and Distributed Computing, Vol.62, Iss.5, 2002-05, pp. : 945-960

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This paper presents a methodology for a synchronous non-reactive distributed system on a tree topology to stabilize from a k-faulty configuration in a time independent of the size n of the system. In the proposed methodology, processes first measure and compare the sizes of the faulty regions, and then use this information to schedule actions in such a way that the size of the faulty regions progressively shrink, until they completely disappear. We demonstrate that when k processes fail, the stabilization time is O(k²). Apart from its applicability to a wide class of problems, the proposed method achieves scalability with a low space complexity of O(Δ.(Δ.k+log₂ n)) per process, where Δ is the maximum degree of a node. © 2002 Elsevier Science (USA).

Related content

Self-stabilization with path algebra

By Ducourthial B. Tixeuil S.

Theoretical Computer Science, Vol. 293, Iss. 1, 2003-02 ,pp. : 219-236 (18)

Access to resources Recommend Favorite

Self-stabilization of circular arrays of automata

Theoretical Computer Science, Vol. 235, Iss. 1, 2000-03 ,pp. : 143-144 (2)

Access to resources Recommend Favorite

Self-Stabilization of Wait-Free Shared Memory Objects

By Hoepman J-H. Papatriantafilou M. Tsigas P.

Journal of Parallel and Distributed Computing, Vol. 62, Iss. 5, 2002-05 ,pp. : 818-842 (25)

Access to resources Recommend Favorite

The local detection paradigm and its applications to self-stabilization

By Afek Y. Kutten S. Yung M.

Theoretical Computer Science, Vol. 186, Iss. 1, 1997-10 ,pp. : 199-229 (31)

Access to resources Recommend Favorite

A self‐scalable load injection service

By

SOFTWARE:PRACTICE AND EXPERIENCE, Vol. 45, Iss. 5, 2015-05 ,pp. : 613-632 (20)

John Wiley & Sons Inc

Access to resources Recommend Favorite