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
Masalah set bebas maksimum (MIS) adalah salah satu masalah paling asas dalam bidang pengkomputeran teragih. Kertas kerja ini memberi tumpuan kepada masalah MIS dengan komunikasi yang tidak boleh dipercayai antara proses dalam sistem. Kami mencadangkan tanggapan santai MIS, dinamakan hampir MIS (ALMIS), dan menunjukkan bahawa algoritma penstabilan longgar yang dicadangkan dalam kerja kami sebelum ini boleh mencapai masa penahanan yang lama secara eksponen dengan masa penumpuan logaritma dan kerumitan ruang berkenaan ALMIS, yang tidak boleh dicapai pada masa yang sama mengenai MIS dalam kerja kami sebelum ini.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -