The search functionality is under construction.

Author Search Result

[Author] Rongcheng DONG(1hit)

1-1hit
  • Loosely-Stabilizing Algorithm on Almost Maximal Independent Set

    Rongcheng DONG  Taisuke IZUMI  Naoki KITAMURA  Yuichi SUDO  Toshimitsu MASUZAWA  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2023/08/07
      Vol:
    E106-D No:11
      Page(s):
    1762-1771

    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.