TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Designing self-stabilizing systems using game theory
 
Options

Designing self-stabilizing systems using game theory

Publikationstyp
Journal Article
Date Issued
2016-09-01
Sprache
English
Author(s)
Yen, Li-Hsing  
Huang, Jean-Yao  
Turau, Volker  
Institut
Telematik E-17  
TORE-URI
http://hdl.handle.net/11420/5254
Journal
ACM transactions on autonomous and adaptive systems  
Volume
11
Issue
3
Start Page
1
End Page
27
Article Number
18
Citation
ACM Transactions on Autonomous and Adaptive Systems 3 (11): 18 1-27 (2016-09-01)
Publisher DOI
10.1145/2957760
Scopus ID
2-s2.0-84989195958
Publisher
ACM
Self-stabilizing systems tolerate transient faults by always returning to a legitimate system state within a finite time. This goal is challenged by several system features such as arbitrary system states after faults, various process execution models, and constrained process communication means. This work designs selfstabilizing distributed algorithms from the perspective of game theory, achieving an intended system goal through private goals of processes.We propose a generic game design for identifying a maximal independent set (MIS) or a maximal weighted independent set (MWIS) among all processes in a distributed system. From the generic game several specific games can be defined which differ in whether and how neighboring players influence each other. Turning the game designs into self-stabilizing algorithms, we obtain the first algorithms for the MWIS problem and also the first self-stabilizingMIS algorithm that considers node degree (including an analysis of its performance ratio). We also show how to handle simultaneous moves of processes in some process execution models. Simulation results indicate that, for various representative network topologies, the new algorithm outperforms existing methods in terms of MIS size and convergence rate. For the MWIS problem, the new algorithms performed only slightly worse than centralized greedy counterparts.
Subjects
Distributed algorithms
Game theory
Independent set
Self-stabilization
DDC Class
004: Informatik
380: Handel, Kommunikation, Verkehr
More Funding Information
Supported by the Ministry of Science and Technology, Taiwan.
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback