Self-Stabilizing Alliances with Safe Convergence

self stabilizing f g alliances with safe n.w
1 / 59
Embed
Share

Explore the concept of self-stabilizing (f,g)-alliances with safe convergence presented by Fabienne Carrier, Ajoy K. Datta, Stéphane Devismes, Lawrence L. Larmore, and Yvan Rivierre. Delve into the benefits and challenges of self-stabilization, the (f,g)-alliance problem, contributions, algorithms, and future perspectives discussed at SSS 2013, Osaka.

  • Self-Stabilization
  • Alliances
  • Safe Convergence
  • SSS 2013
  • Osaka
rayaanacharya
noan_7 Follow

Uploaded on | 0 Views

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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download 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.

E N D

Presentation Transcript

  1. Self-stabilizing (f,g)-Alliances with Safe Convergence Fabienne Carrier Ajoy K. Datta St phane Devismes Lawrence L. Larmore Yvan Rivierre

  2. Co-Autors Ajoy K. Datta & Lawrence L. Larmore Fabienne Carrier & Yvan Rivierre 14/11/13 SSS 2013, Osaka

  3. Roadmap 1. Safe convergence 2. The (f,g)-alliance problem 3. Contribution 4. Algorithm 5. Perspectives 14/11/13 SSS 2013, Osaka

  4. Safe convergence 14/11/13 SSS 2013, Osaka

  5. Pros and Cons of Self-Stabilization Tolerate only transient faults Tolerate any finite number of transient faults No initialization Large-scale network Self-organization in sensor network Dynamicity Topological change Transient fault Eventual safety No stabilization detection 14/11/13 SSS 2013, Osaka

  6. Pros and Cons of Self-Stabilization Tolerate only transient faults Tolerate any finite number of transient faults No initialization Large-scale network Self-organization in sensor network Dynamicity Topological change Transient fault Eventual safety No stabilization detection 14/11/13 SSS 2013, Osaka

  7. Related Work Enhancing safety: Fault-containment [Ghosh et al, PODC 96] Superstabilization [Dolev & Herman, CJTCS 97] Time-adaptive Self-stabilization [Kutten & Patt-Shamir, PODC 97] Self-Stab + safe convergence [Kakugawa & Masuzawa, IPDPS 06] Etc. 14/11/13 SSS 2013, Osaka

  8. Back to self-stabilization 14/11/13 SSS 2013, Osaka

  9. Back to self-stabilization No safety guarantee 14/11/13 SSS 2013, Osaka

  10. Back to self-stabilization (D) 14/11/13 SSS 2013, Osaka

  11. Back to self-stabilization Are all illegitimate configurations identically bad ? 14/11/13 SSS 2013, Osaka

  12. Back to self-stabilization Are all illegitimate configurations identically bad ? Of course, NO ! 14/11/13 SSS 2013, Osaka

  13. Self-stabilization + Safe Convergence Really bad Not so bad good 14/11/13 SSS 2013, Osaka

  14. Self-stabilization + Safe Convergence Quick convergence time 14/11/13 SSS 2013, Osaka

  15. Self-stabilization + Safe Convergence Optimal LC feasable LC Set of feasable LC: CLOSED Set of optimal LC: CLOSED Quick convergence to a feasable LC (O(1) expected) Convergence to an optimal LC 14/11/13 SSS 2013, Osaka

  16. Self-stabilization + Safe Convergence: example [Kakugawa & Masuzawa, IPDPS 06] Construction of a minimal dominating set 1-round convergence to a dominating set (not necessarily a minimal one) Then, O(D)-rounds convergence to a MINIMAL dominating set During this phase, all configurations contain a dominating set 14/11/13 SSS 2013, Osaka

  17. The problem: (f,g)-Alliance [Dourado et al, SSS 11] Alliance: subset of nodes f, g: 2 functions mapping nodes to natural integers For every process p: p Alliance at least f(p) neighbors Alliance p Alliance at least g(p) neighbors Alliance 14/11/13 SSS 2013, Osaka

  18. Example: (f,g)-Alliance Red nodes form a (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  19. Example: (f,g)-Alliance Red nodes DO NOT form a (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  20. (f,g)-Alliance: generalization of several problems Dominating sets K-domination sets K-tuple domination sets Global defensive alliance Global offensive alliance E.g., Dominating set = (1,0)-alliance 14/11/13 SSS 2013, Osaka

  21. Minimality & 1-Minimality Let A be a set of nodes A is a minimal (f,g)-Alliance iff every proper subset of A is not an (f,g)-Alliance A is a 1-minimal (f,g)-Alliance iff p A, A-{p} is not an (f,g)-Alliance 14/11/13 SSS 2013, Osaka

  22. Example: (0,1)-Alliance Red nodes form a (0,1)-Alliance, but NEITHER a minimal NOR a 1-minimal (0,1)-Alliance 14/11/13 SSS 2013, Osaka

  23. Example: (0,1)-Alliance Red nodes form a 1-minimal (0,1)-Alliance but not a minimal one 14/11/13 SSS 2013, Osaka

  24. Example: (0,1)-Alliance Red nodes (empty set) both form a minimal AND a 1-minimal (0,1)-Alliance 14/11/13 SSS 2013, Osaka

  25. Property [Dourado et al, SSS 11] Every minimal (f,g)-Alliance is a 1-minimal (f,g)-Alliance If for every node p, f(p) g(p), then A is a minimal (f,g)-Alliance iff A is a 1-minimal (f,g)-Alliance 14/11/13 SSS 2013, Osaka

  26. Contribution Self-Stabilizing Safe Converging Algorithm for computing: a minimal (f,g)-Alliance in identified networks Safe Convergence Stabilization in 4 rounds to a configuration, where an (f,g)-Alliance is defined Stabilization in 4n+4 additional rounds to a configuration, where minimal (f,g)-Alliance is defined Assumptions: If for every node p, f(p) g(p) and (p) g(p) Locally shared memory model, unfair daemon Other complexities Memory requirement: O(log n) bits per process Step complexity: O( 3n) 14/11/13 SSS 2013, Osaka

  27. Algorithms main ideas 14/11/13 SSS 2013, Osaka

  28. ``Nave Idea One Boolean Red: A Green: A Two actions: Join Leave 14/11/13 SSS 2013, Osaka

  29. ``Nave Idea To obtain safe convergence, it should be harder to leave than to join One boolean Red: A Green: A Two actions: Join Leave 14/11/13 SSS 2013, Osaka

  30. Leave the alliance p can leave if : 1. At least f(p) neighbors A after p leaves AND 2. Each neighbor q still have enough neighbors A after p leaves i.e., g(q) or f(q) depending whether q belongs or not to A 14/11/13 SSS 2013, Osaka

  31. At least f(p) neighbors A after p leaves Leaving should be locally sequential Example: (2,1)-Alliance p 14/11/13 SSS 2013, Osaka

  32. At least f(p) neighbors A after p leaves Leaving should be locally sequential Example: (2,1)-Alliance p p 14/11/13 SSS 2013, Osaka

  33. At least f(p) neighbors A after p leaves Leaving should be locally sequential Example: (2,1)-Alliance p 14/11/13 SSS 2013, Osaka

  34. At least f(p) neighbors A after p leaves Leaving should be locally sequential Example: (2,1)-Alliance p p 14/11/13 SSS 2013, Osaka

  35. Pointer: authorization to leave p Nil Nil 14/11/13 SSS 2013, Osaka

  36. Pointer: authorization to leave p Nil Nil 14/11/13 SSS 2013, Osaka

  37. Each neighbor still have enough neighbor A after p leaves A neighbor q gives an authorization only if q still have enough neighbors A without p p (1,0)-Alliance q 14/11/13 SSS 2013, Osaka

  38. Each neighbor still have enough neighbor A after p leaves A neighbor q gives an authorization only if q still have enough neighbors A without p p (1,0)-Alliance If q has several choices ID breaks ties q 14/11/13 SSS 2013, Osaka

  39. Deadlock problems Nil Nil (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  40. Deadlock problems Busy! Nil Nil (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  41. Deadlock problems Busy! Nil Nil (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  42. Deadlock problems Busy! Nil Nil Tie break! (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  43. Deadlock problems Busy! Nil Nil Tie break! Nil (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  44. Deadlock problems Busy! Nil Nil Tie break! Nil (1,0)-Alliance 14/11/13 SSS 2013, Osaka

  45. How to evaluate Busy? NP A < f(p) Busy! p (2,0)-Alliance 14/11/13 SSS 2013, Osaka

  46. How to evaluate Busy? NP A < f(p) A neighbor q of p needs that p stays in the alliance Busy! p q (2,0)-Alliance 14/11/13 SSS 2013, Osaka

  47. How to evaluate Busy? NP A < f(p) A neighbor q of p needs that p stays in the alliance 0 2 2 1 Busy! p q 2 3 2 (2,0)-Alliance 1 Nb 14/11/13 SSS 2013, Osaka

  48. Last problem (1,0)-Alliance Nil Nil Nil 14/11/13 SSS 2013, Osaka

  49. Last problem (1,0)-Alliance Nil Nil Nil Nil Nil Nil 14/11/13 SSS 2013, Osaka

  50. Last problem (1,0)-Alliance Nil Nil Nil Nil Nil Nil Nil Nil Nil 14/11/13 SSS 2013, Osaka

Related


No related presentations.

More Related Content