Self-Stabilization in Spite of Distributed Control

Self-Stabilization in Spite of Distributed Control. Dijkstra, E. W. In Selected Writings on Computing: A Personal Perspective, of Texts and Monographs in Computer Science, pages 41–46. Springer New York.

Paper doi abstract bibtex

A systematic way for finding the algorithm ensuring some desired form of co-operation between a set of loosely coupled sequential processes can in general terms be described as follows: the relation ” the system is in a legitimate state” is kept invariant. As a consequence, each intended individual process step that could possibly cause violation of that invariant relation has to be preceded by a test that it won't do so, and depending on the outcome of that test the critical process step is either caused to take place or it – and with it the process of which it is a part – is delayed until a more favourable system state has been reached. With a suitable choice of the set of legitimate states one can indeed introduce the rule that a critical process step will be delayed only as long as its execution would lead to violation of the corresponding invariant relation. [Excerpt] We consider a connected graph in which the majority of the possible edges are missing and a finite state machine is placed at each node; machines placed in directly connected nodes are called each other's neighbors. For each machine one or more so-called "privileges" are defined, i.e. boolean functions of its own state and the states of its neighbors; when such a boolean function is true, we say that the privilege is "present." In order to model the undefined speed ratios of the various machines, we introduce a central daemon–its replacement by a distributed daemon falls outside the scope of this article–that can "select" one of the privileges present. The machine enjoying the selected privilege will then make its "move"; i.e. it is brought into a new state that is a function of its old state and the states of its neighbors. If for such a machine more than one privilege is present, the new state may also depend on the privilege selected. After completion of the move, the daemon will select a new privilege. [\n] Furthermore there is a global criterion, telling whether the system as a whole is in a "legitimate" state. We require that: (I) in each legitimate state one or more privileges will be present; (2) in each legitimate state each possible move will bring the system again in a legitimate state; (3) each privilege must be present in at least one legitimate state; and (4) for any pair of legitimate states there exists a sequence of moves transferring the system from the one into the other. [\n] We call the system "self-stabilizing" if and only if, regardless of the initial state and regardless of the privilege selected each time for the next move, at least one privilege will always be present and the system is guaranteed to find itself in a legitimate state after a finite number of moves.

@incollection{dijkstraSelfstabilizationSpiteDistributed1982,
  title = {Self-Stabilization in Spite of Distributed Control},
  booktitle = {Selected {{Writings}} on {{Computing}}: {{A}} Personal {{Perspective}}},
  author = {Dijkstra, Edsger W.},
  date = {1982},
  pages = {41--46},
  publisher = {{Springer New York}},
  doi = {10.1007/978-1-4612-5695-3\\_7},
  url = {https://doi.org/10.1007/978-1-4612-5695-3_7},
  abstract = {A systematic way for finding the algorithm ensuring some desired form of co-operation between a set of loosely coupled sequential processes can in general terms be described as follows: the relation ” the system is in a legitimate state” is kept invariant. As a consequence, each intended individual process step that could possibly cause violation of that invariant relation has to be preceded by a test that it won't do so, and depending on the outcome of that test the critical process step is either caused to take place or it -- and with it the process of which it is a part -- is delayed until a more favourable system state has been reached. With a suitable choice of the set of legitimate states one can indeed introduce the rule that a critical process step will be delayed only as long as its execution would lead to violation of the corresponding invariant relation.

[Excerpt] We consider a connected graph in which the majority of the possible edges are missing and a finite state machine is placed at each node; machines placed in directly connected nodes are called each other's neighbors. For each machine one or more so-called "privileges" are defined, i.e. boolean functions of its own state and the states of its neighbors; when such a boolean function is true, we say that the privilege is "present." In order to model the undefined speed ratios of the various machines, we introduce a central daemon--its replacement by a distributed daemon falls outside the scope of this article--that can "select" one of the privileges present. The machine enjoying the selected privilege will then make its "move"; i.e. it is brought into a new state that is a function of its old state and the states of its neighbors. If for such a machine more than one privilege is present, the new state may also depend on the privilege selected. After completion of the move, the daemon will select a new privilege.

[\textbackslash n] Furthermore there is a global criterion, telling whether the system as a whole is in a "legitimate" state. We require that: (I) in each legitimate state one or more privileges will be present; (2) in each legitimate state each possible move will bring the system again in a legitimate state; (3) each privilege must be present in at least one legitimate state; and (4) for any pair of legitimate states there exists a sequence of moves transferring the system from the one into the other.

[\textbackslash n] We call the system "self-stabilizing" if and only if, regardless of the initial state and regardless of the privilege selected each time for the next move, at least one privilege will always be present and the system is guaranteed to find itself in a legitimate state after a finite number of moves.},
  keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-13529446,array-of-agents,high-impact-publication,multiplicity,precursor-research,self-adaptive-systems,self-healing,self-stabilisation,software-uncertainty,system-of-systems},
  series = {Texts and {{Monographs}} in {{Computer Science}}}
}

Downloads: 0

{"_id":"QkPhYTeKsefndHTBs","bibbaseid":"dijkstra-selfstabilizationinspiteofdistributedcontrol","authorIDs":[],"author_short":["Dijkstra, E. W."],"bibdata":{"bibtype":"incollection","type":"incollection","title":"Self-Stabilization in Spite of Distributed Control","booktitle":"Selected Writings on Computing: A Personal Perspective","author":[{"propositions":[],"lastnames":["Dijkstra"],"firstnames":["Edsger","W."],"suffixes":[]}],"date":"1982","pages":"41–46","publisher":"Springer New York","doi":"10.1007/978-1-4612-5695-3\\_7","url":"https://doi.org/10.1007/978-1-4612-5695-3_7","abstract":"A systematic way for finding the algorithm ensuring some desired form of co-operation between a set of loosely coupled sequential processes can in general terms be described as follows: the relation ” the system is in a legitimate state” is kept invariant. As a consequence, each intended individual process step that could possibly cause violation of that invariant relation has to be preceded by a test that it won't do so, and depending on the outcome of that test the critical process step is either caused to take place or it – and with it the process of which it is a part – is delayed until a more favourable system state has been reached. With a suitable choice of the set of legitimate states one can indeed introduce the rule that a critical process step will be delayed only as long as its execution would lead to violation of the corresponding invariant relation. [Excerpt] We consider a connected graph in which the majority of the possible edges are missing and a finite state machine is placed at each node; machines placed in directly connected nodes are called each other's neighbors. For each machine one or more so-called \"privileges\" are defined, i.e. boolean functions of its own state and the states of its neighbors; when such a boolean function is true, we say that the privilege is \"present.\" In order to model the undefined speed ratios of the various machines, we introduce a central daemon–its replacement by a distributed daemon falls outside the scope of this article–that can \"select\" one of the privileges present. The machine enjoying the selected privilege will then make its \"move\"; i.e. it is brought into a new state that is a function of its old state and the states of its neighbors. If for such a machine more than one privilege is present, the new state may also depend on the privilege selected. After completion of the move, the daemon will select a new privilege. [\\n] Furthermore there is a global criterion, telling whether the system as a whole is in a \"legitimate\" state. We require that: (I) in each legitimate state one or more privileges will be present; (2) in each legitimate state each possible move will bring the system again in a legitimate state; (3) each privilege must be present in at least one legitimate state; and (4) for any pair of legitimate states there exists a sequence of moves transferring the system from the one into the other. [\\n] We call the system \"self-stabilizing\" if and only if, regardless of the initial state and regardless of the privilege selected each time for the next move, at least one privilege will always be present and the system is guaranteed to find itself in a legitimate state after a finite number of moves.","keywords":"*imported-from-citeulike-INRMM,~INRMM-MiD:c-13529446,array-of-agents,high-impact-publication,multiplicity,precursor-research,self-adaptive-systems,self-healing,self-stabilisation,software-uncertainty,system-of-systems","series":"Texts and Monographs in Computer Science","bibtex":"@incollection{dijkstraSelfstabilizationSpiteDistributed1982,\n title = {Self-Stabilization in Spite of Distributed Control},\n booktitle = {Selected {{Writings}} on {{Computing}}: {{A}} Personal {{Perspective}}},\n author = {Dijkstra, Edsger W.},\n date = {1982},\n pages = {41--46},\n publisher = {{Springer New York}},\n doi = {10.1007/978-1-4612-5695-3\\\\_7},\n url = {https://doi.org/10.1007/978-1-4612-5695-3_7},\n abstract = {A systematic way for finding the algorithm ensuring some desired form of co-operation between a set of loosely coupled sequential processes can in general terms be described as follows: the relation ” the system is in a legitimate state” is kept invariant. As a consequence, each intended individual process step that could possibly cause violation of that invariant relation has to be preceded by a test that it won't do so, and depending on the outcome of that test the critical process step is either caused to take place or it -- and with it the process of which it is a part -- is delayed until a more favourable system state has been reached. With a suitable choice of the set of legitimate states one can indeed introduce the rule that a critical process step will be delayed only as long as its execution would lead to violation of the corresponding invariant relation.\n\n[Excerpt] We consider a connected graph in which the majority of the possible edges are missing and a finite state machine is placed at each node; machines placed in directly connected nodes are called each other's neighbors. For each machine one or more so-called \"privileges\" are defined, i.e. boolean functions of its own state and the states of its neighbors; when such a boolean function is true, we say that the privilege is \"present.\" In order to model the undefined speed ratios of the various machines, we introduce a central daemon--its replacement by a distributed daemon falls outside the scope of this article--that can \"select\" one of the privileges present. The machine enjoying the selected privilege will then make its \"move\"; i.e. it is brought into a new state that is a function of its old state and the states of its neighbors. If for such a machine more than one privilege is present, the new state may also depend on the privilege selected. After completion of the move, the daemon will select a new privilege.\n\n[\\textbackslash n] Furthermore there is a global criterion, telling whether the system as a whole is in a \"legitimate\" state. We require that: (I) in each legitimate state one or more privileges will be present; (2) in each legitimate state each possible move will bring the system again in a legitimate state; (3) each privilege must be present in at least one legitimate state; and (4) for any pair of legitimate states there exists a sequence of moves transferring the system from the one into the other.\n\n[\\textbackslash n] We call the system \"self-stabilizing\" if and only if, regardless of the initial state and regardless of the privilege selected each time for the next move, at least one privilege will always be present and the system is guaranteed to find itself in a legitimate state after a finite number of moves.},\n keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-13529446,array-of-agents,high-impact-publication,multiplicity,precursor-research,self-adaptive-systems,self-healing,self-stabilisation,software-uncertainty,system-of-systems},\n series = {Texts and {{Monographs}} in {{Computer Science}}}\n}\n\n","author_short":["Dijkstra, E. W."],"key":"dijkstraSelfstabilizationSpiteDistributed1982","id":"dijkstraSelfstabilizationSpiteDistributed1982","bibbaseid":"dijkstra-selfstabilizationinspiteofdistributedcontrol","role":"author","urls":{"Paper":"https://doi.org/10.1007/978-1-4612-5695-3_7"},"keyword":["*imported-from-citeulike-INRMM","~INRMM-MiD:c-13529446","array-of-agents","high-impact-publication","multiplicity","precursor-research","self-adaptive-systems","self-healing","self-stabilisation","software-uncertainty","system-of-systems"],"downloads":0},"bibtype":"incollection","biburl":"https://tmpfiles.org/dl/58794/INRMM.bib","creationDate":"2020-07-02T22:41:05.389Z","downloads":0,"keywords":["*imported-from-citeulike-inrmm","~inrmm-mid:c-13529446","array-of-agents","high-impact-publication","multiplicity","precursor-research","self-adaptive-systems","self-healing","self-stabilisation","software-uncertainty","system-of-systems"],"search_terms":["self","stabilization","spite","distributed","control","dijkstra"],"title":"Self-Stabilization in Spite of Distributed Control","year":null,"dataSources":["DXuKbcZTirdigFKPF"]}