1
$\begingroup$

Self-stabilizing algorithms are extremely useful in distributed systems, but can the algorithm be applied concurrently to each computational node?

My instinct is to say yes, but I can't help but imagine a 'Game Of Life' scenario where the state of the graph toggles between two states. What keeps the question alive in my mind is the possibility that both such states would be considered 'correct', but then if the state were correct, wouldn't the graph stabilize?

If they are not guaranteed to work in parallel, can you provide an example where absolute convergence doesn't exist?


A self-stabilizing algorithm is an algorithm (in all my experience, applied to arbitrary graphs and graph structures exclusively) that, upon repeated applications, guarantees convergence onto a correct state—one that meets a set of requirements. Consider a simple example:

You maintain a network of hospitals and data centers. Each hospital must be connected to exactly one data center, and each data center must be connected to exactly two other data centers. (You can imagine also attempting to minimize latency.) When you set up the network, it is in a correct state—all requirements are met.

Weeks pass, and a giant storm takes out one of your data centers. Being the forth-dimensional thinker you are, you planned for situations like this by putting into place a self-stabilizing algorithm that will automatically reconfigure the network to get back to a correct state. You set up a daemon to oversee the operation. It picks arbitrary nodes in your network and asks them if they are in a correct state. If not, the daemon corrects that part of the network.

All is well and you can stay asleep in bed (because everything catastrophic happens at 3am).

The trick is, the daemon isn't a necessary part of this system—it's just easier to think about it like this. In reality, each node is its own computational unit—constantly evaluating its own state and taking steps to correct itself if necessary.

The introductory paragraphs of the Wikipedia article on the subject give a very good technical overview:

Self-stabilization is a concept of fault-tolerance in distributed computing. A distributed system that is self-stabilizing will end up in a correct state no matter what state it is initialized with. That correct state is reached after a finite number of execution steps.

Just as a piece of requested information that doesn't fit in well above:

When the graph is stable, no node has any faults with it. Since no predicates apply to it, no actions are taken, and the graph remains stable.

$\endgroup$
  • $\begingroup$ I don't know what a "self-stabilizing" algorithm is. I would guess that you'll have more luck getting an answer if you define what a self-stabilizing algorithm is, what the graph is, what the states are, and what it means to stabilize. $\endgroup$ – Wandering Logic Dec 24 '13 at 15:28
  • $\begingroup$ @WanderingLogic see edit $\endgroup$ – Sean Allred Dec 24 '13 at 19:46
  • $\begingroup$ What have you read about self-stabilizing systems? I think you haven't done enough research, e.g., reading textbooks and spending some time in the library. Asking on StackExchange is not a substitute for some time spent reading up on the subject. $\endgroup$ – D.W. Dec 24 '13 at 21:39
  • $\begingroup$ @D.W. Oh course it isn't; I'm doing undergraduate research in it, so I have been reading (on and off, admittedly) since August, and in each I've seen that a certain node is given privilege to act; to me, this seems against the idea of concurrency. $\endgroup$ – Sean Allred Dec 24 '13 at 22:16
  • $\begingroup$ @vermiculus, I think you might be misinterpreting the "privilege". My recollection is that in Dijkstra's algorithm, each node is evaluating, in parallel, concurrently, at each time step, whether it "has the privilege" and deciding whether to act based on that. Thus each node is running in parallel, concurrently (part of the code that it is running is the code that tests whether it thinks it has the privilege to act). I could be wrong, so check this against a careful description of the algorithm, but I think it's something like that. $\endgroup$ – D.W. Dec 24 '13 at 22:33
3
$\begingroup$

I suggest you look for a textbook that provides an introduction to self-stabilizing algorithms (with some definitions, examples, etc.), and work through that textbook. I think that will provide you a much better understanding, and you'll be able to answer this kind of question yourself. Trying to learn a subject by reading Wikipedia and asking questions on StackExchange sites is not the way to go.

For instance, I think you'll find that, yes, of course each distributed node is working concurrently (in parallel); that's what it means for a system to be a distributed system. And yes, for a self-stabilizing algorithm to be correct, one must show that it will never enter an infinite loop of the sort you describe; this is the convergence property.

Designing an algorithm with these properties is non-trivial, but in general, designing self-stabilizing systems is not easy. No one ever promised this stuff would be easy.

$\endgroup$
0
$\begingroup$

I think self-stabilizing algorithms guaranteed to work in parallel environment also. but you should go through book also, here i am mentioning some good books for self stabilization from my experience:

References: 1: Self-Stabilization by Shlomi Dolev

2: Distributed Systems: An Algorithmic Approach bye Sukumar Ghosh Chapter 17.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.