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, 2015 at 21:12
  • $\begingroup$ That looks like a fantastic survey, perfect for me. Thanks $\endgroup$ Oct 11, 2015 at 14:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.