Snap Stabilization in Message Passing Systems
Snap-stabilization is a self-stabilization technique that allows algorithms to operate correctly from any initial state without requiring shared registers. In message passing systems, nodes communicate through bidirectional asynchronous channels, with limitations imposed on channel capacity to enable snap-stabilization. The Propagation of Information with Feedback (PIF) algorithm facilitates broadcasting messages and receiving feedback to ensure correct operations. By combining algorithms and node identifiers, mutual exclusion with a designated leader can be achieved, controlling access to critical sections.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Snap-stabilization in message-passing systems By Sylvie Dela t, St phane Devismes, Mikhail Nesterenko, S bastien Tixeuil
Idea Snap-stabilization is a self stabilization technique where from any arbitrary initial state the algorithm immediately operates correctly Previous algorithms utilized shared registers which is a strict communication requirement, instead this paper considers a standard message passing system
Communication Nodes communicate through n 1 FIFO bidirectional asynchronous channels (fully connected network) The authors prove that if the channels have unbounded capacity snap-stabilization is impossible as there could be an unbounded number of arbitrary messages in the channels Therefore, a limit is put on channel size and any additional messages pushed to the channel are lost It is assumed channel capacity is 1 however the algorithm can be extended if the capacity is bounded and known
PIF The algorithm presented in this paper performs Propagation of Information with Feedback (PIF) which is a standard snap-stabilization technique The algorithm is designed so that some node p can broadcast a message and receive feedback about the message from everyone which it may use to continue operations
Algorithm Step 1 assume node p wants to broadcast a message, it will wait until the previous broadcast is done even if caused by a fault Step 2 p will set a tracking variable for the State of every process q to State[q] = 0 Step 3 repeatedly send its message with a flag = State[q] to every q Step 4 q upon receipt of a message q will set its Nstate = flag and if flag < 4 reply to p with a similar message Step 5 p upon receipt of a message with a flag < 4 increment State[q] and return to step 3 Termination when State[q] == 4 for all q the PIF is done
Extension to Mutual Exclusion Combining the previously designed algorithms and node identifiers to designate a leader mutual exclusion can be achieved The leader controls who may be in the critical section by performing PIFs, which will notify the nodes who may be in the critical section and when it is again empty so someone else can request access
