Selfish Self-Stabilizing Approach to Maximal Independent Sets

Li-Hsing Yen, Jean Yao Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given an undirected graph G = (V, E), a subset S of V is an independent set if no two nodes in S are adjacent to each other. S is a maximal independent set (MIS) if no proper superset of S is also an independent set. We model the problem of finding an MIS in a distributed system as a noncooperative graphical game and propose an algorithmic mechanism design for the problem. We show Nash equilibrium, correctness, and Pareto optimality of the design and then turn the design into a self-stabilizing algorithm running under a synchronous daemon. The convergence property and time complexity of the algorithm is shown. Simulation results indicate that the proposed protocol performs better than previous work in terms of MIS size under various representative types of network topologies.

Original languageEnglish
Title of host publicationProceedings - 13th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages9-16
Number of pages8
ISBN (Electronic)9781467379519
DOIs
StatePublished - 2 Dec 2015
Event14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015 - Helsinki, Finland
Duration: 20 Aug 201522 Aug 2015

Publication series

NameProceedings - 14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015
Volume3

Conference

Conference14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015
CountryFinland
CityHelsinki
Period20/08/1522/08/15

Keywords

  • distributed algorithms
  • game theory
  • independent set
  • self-stabilization

Fingerprint Dive into the research topics of 'Selfish Self-Stabilizing Approach to Maximal Independent Sets'. Together they form a unique fingerprint.

Cite this