The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
MIS(Maximal Independent Set) 문제는 분산 컴퓨팅 분야의 가장 근본적인 문제 중 하나입니다. 본 논문은 시스템 내 프로세스 간 통신이 불안정하여 발생하는 MIS 문제에 중점을 두고 있습니다. 우리는 거의 MIS(ALMIS)라고 명명된 완화된 MIS 개념을 제안하고, 이전 연구에서 제안된 느슨하게 안정화된 알고리즘이 ALMIS에 대한 대수 수렴 시간 및 공간 복잡도로 인해 기하급수적으로 긴 유지 시간을 달성할 수 있음을 보여줍니다. 이전 작업에서 MIS에 대해서도 마찬가지입니다.
Rongcheng DONG
Osaka University
Taisuke IZUMI
Osaka University
Naoki KITAMURA
Osaka University
Yuichi SUDO
Hosei University
Toshimitsu MASUZAWA
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Rongcheng DONG, Taisuke IZUMI, Naoki KITAMURA, Yuichi SUDO, Toshimitsu MASUZAWA, "Loosely-Stabilizing Algorithm on Almost Maximal Independent Set" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 11, pp. 1762-1771, November 2023, doi: 10.1587/transinf.2023EDP7075.
Abstract: The maximal independent set (MIS) problem is one of the most fundamental problems in the field of distributed computing. This paper focuses on the MIS problem with unreliable communication between processes in the system. We propose a relaxed notion of MIS, named almost MIS (ALMIS), and show that the loosely-stabilizing algorithm proposed in our previous work can achieve exponentially long holding time with logarithmic convergence time and space complexity regarding ALMIS, which cannot be achieved at the same time regarding MIS in our previous work.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023EDP7075/_p
부
@ARTICLE{e106-d_11_1762,
author={Rongcheng DONG, Taisuke IZUMI, Naoki KITAMURA, Yuichi SUDO, Toshimitsu MASUZAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Loosely-Stabilizing Algorithm on Almost Maximal Independent Set},
year={2023},
volume={E106-D},
number={11},
pages={1762-1771},
abstract={The maximal independent set (MIS) problem is one of the most fundamental problems in the field of distributed computing. This paper focuses on the MIS problem with unreliable communication between processes in the system. We propose a relaxed notion of MIS, named almost MIS (ALMIS), and show that the loosely-stabilizing algorithm proposed in our previous work can achieve exponentially long holding time with logarithmic convergence time and space complexity regarding ALMIS, which cannot be achieved at the same time regarding MIS in our previous work.},
keywords={},
doi={10.1587/transinf.2023EDP7075},
ISSN={1745-1361},
month={November},}
부
TY - JOUR
TI - Loosely-Stabilizing Algorithm on Almost Maximal Independent Set
T2 - IEICE TRANSACTIONS on Information
SP - 1762
EP - 1771
AU - Rongcheng DONG
AU - Taisuke IZUMI
AU - Naoki KITAMURA
AU - Yuichi SUDO
AU - Toshimitsu MASUZAWA
PY - 2023
DO - 10.1587/transinf.2023EDP7075
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2023
AB - The maximal independent set (MIS) problem is one of the most fundamental problems in the field of distributed computing. This paper focuses on the MIS problem with unreliable communication between processes in the system. We propose a relaxed notion of MIS, named almost MIS (ALMIS), and show that the loosely-stabilizing algorithm proposed in our previous work can achieve exponentially long holding time with logarithmic convergence time and space complexity regarding ALMIS, which cannot be achieved at the same time regarding MIS in our previous work.
ER -