Designing Self-Stabilizing Systems Using Game Theory

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2016-09

期刊名稱

ACM TRANSACTIONS ON AUTONOMOUS AND ADAPTIVE SYSTEMS

卷期與頁次

第 11 卷第 3 期

ISSN

1556-4665

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Yen, L.-H., Huang, J.-Y., & Turau, V. (2016). Designing Self-Stabilizing Systems Using Game Theory. ACM TRANSACTIONS ON AUTONOMOUS AND ADAPTIVE SYSTEMS, 11(3). https://doi.org/10.1145/2957760

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/134245