So we're using this book by Shlomi Dolev on self-stabilization in class. Not being from a theretical CS background, I think the book is rather terse. Most of it is fine but there's this section on "recomputation of floating output" that I just couldn't get and I would like to know if anyone could help explain the concept in a bit more depth. There's probably a more commonly accepted term for it in the field of distributed systems, so if anyone recognizes the concept, the common name for it would be very helpful as well.

As I understand it, the gist of it is that you take a non-stabilizing, finite algorithm A and run it forever. With some care regarding tracking arguments and outputs of each iteration, you can turn algorithm A into a self-stabilizing algorithm. But that's about the limit of my understanding and again, the book doesn't do an amazing job explaining it...

  • 1
    $\begingroup$ It is basically the same thing as what we describe in Section 2 of this survey: users.ics.aalto.fi/suomela/local-self-stab (in particular, see Section 2.4, which tries to explain it with the help of some illustrations). $\endgroup$ Oct 10 '15 at 21:12
  • $\begingroup$ That looks like a fantastic survey, perfect for me. Thanks $\endgroup$ Oct 11 '15 at 14:53

Your Answer

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

Browse other questions tagged or ask your own question.