Loading...

Game theoretic analysis of self-stabilizing systems on arrays

Shoja, E ; Sharif University of Technology | 2021

375 Viewed
  1. Type of Document: Article
  2. DOI: 10.1134/S1064230721020131
  3. Publisher: Pleiades journals , 2021
  4. Abstract:
  5. Abstract: In 1973 E.W. Dijkstra introduced the notion of self-stabilization in the context of mutual exclusion. Considering the same problem on an array, we present a game theoretic analysis of self-stabilizing systems with three- or four-state machines. We give a formalized definition of the problem as a game where each player’s strategy represents the state of its corresponding machine. For the three-state case, we prove the impossibility of any infinite self-stabilizing systems on an array. For the four-state case we consider two algorithms. For Ghosh’s solution [1] we prove the upper bound of (n – 1)(n – 3) steps and that this bound is tight. Also we present another four-state self-stabilizing system, and prove that at most n2– 5n + 7 steps are required for the system to reach self-stabilization. © 2021, Pleiades Publishing, Ltd
  6. Keywords:
  7. Stabilization ; Dijkstra ; Game theoretic analysis ; Mutual exclusions ; Self stabilization ; Self-stabilizing systems ; State machine ; Upper Bound ; Game theory
  8. Source: Journal of Computer and Systems Sciences International ; Volume 60, Issue 2 , 2021 , Pages 227-238 ; 10642307 (ISSN)
  9. URL: https://link.springer.com/article/10.1134/S1064230721020131?noAccess=true