Jangan Takut Mati: Pencarian Lubang Hitam pada Graf Dinamis dengan Agen Lebih Sedikit

Masalah pencarian lubang hitam adalah tantangan mendasar dalam komputasi terdistribusi pada jaringan. Sekelompok agen bergerak sinkron beroperasi dalam jaringan berlabel port di mana satu simpul, lubang hitam, secara permanen menghancurkan setiap agen yang mengunjunginya. Tujuannya adalah agar setidaknya satu agen bertahan, berhenti di simpul yang berdekatan dengan lubang hitam, dan mengeluarkan nomor port yang menuju ke lubang hitam. Penelitian sebelumnya oleh Kaur dkk. (SSS 2025) menetapkan bahwa $2{\delta }_{BH}+17$ agen cukup untuk tugas ini pada graf dinamis terhubung 1-interval 1-bounded, di mana ${\delta }_{BH}$ adalah derajat lubang hitam. Batas bawah sebesar $2{\delta }_{BH}+1$ juga ditunjukkan oleh Kaur dkk. (ICDCN 2025). Makalah ini mempersempit celah tersebut dengan membuktikan bahwa $2{\delta }_{BH}+3$ agen sudah cukup, sehingga batas atas mendekati batas bawah.

Penulis mempertimbangkan sekelompok agen bergerak sinkron dalam jaringan berlabel port yang dimodelkan sebagai graf dinamis terhubung 1-interval 1-bounded. Pada graf semacam itu, topologi dapat berubah pada setiap langkah waktu, tetapi graf tetap terhubung pada setiap interval, dan jumlah perubahannya terbatas. Agen-agen awalnya tersebar di seluruh jaringan. Algoritma yang dirancang penulis mengoordinasikan pergerakan agen untuk menjelajahi jaringan sambil menghindari lubang hitam. Kunci pendekatan ini adalah strategi yang menggunakan lebih sedikit agen dengan mengelola eksplorasi secara hati-hati dan memastikan setidaknya satu agen bertahan untuk melaporkan lokasi lubang hitam. Algoritma dianalisis untuk menunjukkan bahwa dengan $2{\delta }_{BH}+3$ agen, tugas tersebut dapat diselesaikan. Metodologi ini melibatkan analisis kasus secara rinci dan konstruksi lintasan agen yang menjamin terminasi dan kebenaran.