=. Que-p, If p remains in the tree, then Que p remains equal to Q until p executes QR-action. After executing QR-action, Que p = R and we arrive at the previous case

. Proof, We first prove Property [P IF 1] of Specification 4.1, which is, every process receives any message m sent by r exactly once

@. Assume, S. , =. C. If-que-p, ?. {w, and A. , Que q ) will stay equal to (B,Q) until p executes QR-action. p eventually executes QR-action: Que p := R. Now, since S p = C and p never receives m, we can deduce that p is in an abnormal tree and Que p remains not equal to A until p leaves the tree by Lemma 4, 10. So, until p leaves the tree, q cannot execute F -action (q does not satisfy AnswerOK(q))

. Cournier, . Datta, V. Petit, and . Villain, Enabling snap-stabilization, 23rd International Conference on Distributed Computing Systems, 2003. Proceedings., pp.12-19, 2003.
DOI : 10.1109/ICDCS.2003.1203447

A. Cournier, V. Devismes, and . Villain, Snap-stabilizing PIF and useless computations, 12th International Conference on Parallel and Distributed Systems, (ICPADS'06), pp.39-46, 2006.
DOI : 10.1109/ICPADS.2006.100

E. Dijkstra, Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery, pp.643-644, 1974.

S. Ghosh, A. Gupta, T. Herman, and S. V. Pemmaraju, Fault-containing self-stabilizing distributed protocols, Distributed Computing, vol.25, issue.59, pp.53-73, 2007.
DOI : 10.1007/s00446-007-0032-2

S. Dolev and T. Herman, SuperStabilizing protocols for dynamic distributed systems, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing , PODC '95, 1997.
DOI : 10.1145/224964.224993

A. Bui, . Datta, V. Petit, and . Villain, State-optimal snap-stabilizing PIF in tree networks, Proceedings 19th IEEE International Conference on Distributed Computing Systems, pp.78-85, 1999.
DOI : 10.1109/SLFSTB.1999.777490

A. Bui, . Datta, V. Petit, and . Villain, Snap-stabilizing PIF algorithm in tree networks without sense of direction, SIROCCO'99, The 6th International Colloquium On Structural Information and Communication Complexity Proceedings, pp.32-46, 1999.

A. Cournier, A. Kumar-datta, F. Petit, and V. Villain, Optimal snap-stabilizing PIF algorithms in un-oriented trees, High Speed Networks, pp.185-200, 2005.

A. Cournier, . Datta, V. Petit, and . Villain, Snap-stabilizing PIF algorithm in arbitrary rooted networks, 22st International Conference on Distributed Computing Systems (ICDCS-22), pp.199-206, 2002.

L. Blin, V. Cournier, and . Villain, An Improved Snap-Stabilizing PIF Algorithm, DSN SSS'03 Workshop: Sixth Symposium on Self-Stabilizing Systems (SSS'03), pp.199-214, 2003.
DOI : 10.1007/3-540-45032-7_15
URL : https://hal.archives-ouvertes.fr/hal-01310823

A. Cournier, S. Devismes, and V. Villain, Light enabling snap-stabilization of fundamental protocols, ACM Transactions on Autonomous and Adaptive Systems, vol.4, issue.1, 2009.
DOI : 10.1145/1462187.1462193

F. Petit and V. Villain, Optimal snap-stabilizing depth-first token circulation in tree networks, Journal of Parallel and Distributed Computing, vol.67, issue.1, pp.1-12, 2007.
DOI : 10.1016/j.jpdc.2006.08.008

A. Cournier, V. Devismes, and . Villain, A Snap-Stabilizing DFS with a Lower Space Requirement, Seventh International Symposium on Self-Stabilizing Systems (SSS'05), pp.33-47, 2005.
DOI : 10.1007/11577327_3

A. Cournier, . Devismes, V. Petit, and . Villain, Snap-Stabilizing Depth-First Search on Arbitrary Networks, The Computer Journal, vol.49, issue.3, pp.268-280, 2006.
DOI : 10.1093/comjnl/bxh154

D. Bein, V. Datta, and . Villain, Snap-Stabilizing Optimal Binary Search Tree, Seventh International Symposium on Self-Stabilizing Systems (SSS'05), pp.1-17, 2005.
DOI : 10.1007/11577327_1

A. Cournier, V. Devismes, and . Villain, Snap-Stabilizing Detection of Cutsets, HIPC 2005, 12th Annual IEEE Conference on High Performance Computing, pp.488-497, 2005.
DOI : 10.1007/11602569_50

C. Johnen, L. Alima, A. K. Datta, and S. Tixeuil, OPTIMAL SNAP-STABILIZING NEIGHBORHOOD SYNCHRONIZER IN TREE NETWORKS, Parallel Processing Letters, vol.12, issue.03n04, pp.3-4327, 2002.
DOI : 10.1142/S0129626402001026

F. Nolot, Stabilisation des horloges de phases dans les systèmes distribués, 2002.

B. Bonakdarpour, S. Devismes, and F. Petit, Snap-stabilizing committee coordination, 25th IEEE International Symposium on Parallel and Distributed Processing, pp.16-20, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01286781

E. Caron, F. Desprez, F. Petit, and C. Tedeschi, SNAP-STABILIZING PREFIX TREE FOR PEER-TO-PEER SYSTEMS, Parallel Processing Letters, vol.20, issue.01, pp.15-30, 2010.
DOI : 10.1142/S012962641000003X
URL : https://hal.archives-ouvertes.fr/hal-01429571

A. Cournier, S. Dubois, and V. Villain, A snap-stabilizing point-to-point communication protocol in message-switched networks, 2009 IEEE International Symposium on Parallel & Distributed Processing, pp.1-11, 2009.
DOI : 10.1109/IPDPS.2009.5160997
URL : https://hal.archives-ouvertes.fr/inria-00628083

A. Cournier, S. Dubois, A. Lamani, F. Petit, and V. Villain, Snap-Stabilizing Linear Message Forwarding, Stabilization, Safety, and Security of Distributed Systems -12th International Symposium, SSS 2010, pp.546-559, 2010.
DOI : 10.1007/978-3-642-16023-3_42
URL : https://hal.archives-ouvertes.fr/hal-01009446

A. Cournier, S. Dubois, A. Lamani, F. Petit, and V. Villain, The snap-stabilizing message forwarding algorithm on tree topologies, Theoretical Computer Science, vol.496, pp.89-112, 2013.
DOI : 10.1016/j.tcs.2013.04.012
URL : https://hal.archives-ouvertes.fr/hal-01009451

S. Dolev and N. Tzachar, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, Theor. Comput. Sci, vol.410, pp.6-7514, 2009.

S. Delaët, S. Devismes, M. Nesterenko, and S. Tixeuil, Snap-stabilization in message-passing systems, Journal of Parallel and Distributed Computing, vol.70, issue.12, pp.1220-1230, 2010.
DOI : 10.1016/j.jpdc.2010.04.002

K. Mohamed, F. Levé, and V. Villain, Snap-stabilizing PIF on non-oriented trees and message passing model, 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp.299-313, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01323758

S. Katz and K. Perry, Self-stabilizing extensions for message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing , PODC '90, pp.17-26, 1993.
DOI : 10.1145/93385.93405

B. Awerbuch, Y. Kutten, . Mansour, G. Patt-shamir, and . Varghese, Time optimal self-stabilizing synchronization, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , STOC '93, pp.652-661, 1993.
DOI : 10.1145/167088.167256

N. Lynch, Distributed algorithms, 1996.

T. Deepak, C. , and S. Toueg, Unreliable failure detectors for reliable distributed systems, J. ACM, vol.43, issue.2, pp.225-267, 1996.

S. Dolev, S. Israeli, and . Moran, Uniform dynamic self-stabilizing leader election, IEEE Transactions on Parallel and Distributed Systems, vol.8, issue.4, pp.424-440, 1997.
DOI : 10.1109/71.588622

E. Chang, Echo Algorithms: Depth Parallel Operations on General Graphs, IEEE Transactions on Software Engineering, vol.8, issue.4, pp.391-401, 1982.
DOI : 10.1109/TSE.1982.235573

A. Segall, Distributed network protocols, IEEE Transactions on Information Theory, vol.29, issue.1, pp.23-35, 1983.
DOI : 10.1109/TIT.1983.1056620

B. Awerbuch and R. Ostrovsky, Memory-efficient and self-stabilizing network reset, PODC94 Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pp.254-263, 1994.

K. Chandy and L. Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems, vol.3, issue.1, pp.63-75, 1985.
DOI : 10.1145/214451.214456

J. Beauquier, M. Gradinariu, and C. Johnen, Cross-Over Composition - Enforcement of Fairness under Unfair Adversary, Self-Stabilizing Systems, 5th International Workshop Proceedings, volume 2194 of Lecture Notes in Computer Science, pp.19-34, 2001.
DOI : 10.1007/3-540-45438-1_2

J. Beauquier, M. Gradinariu, and C. Johnen, Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings, Distributed Computing, pp.75-93, 2007.
DOI : 10.1007/s00446-007-0034-0
URL : https://hal.archives-ouvertes.fr/hal-00334311