Konsensus dengan Siaran Stokastik

Memperluas konsensus biner yang meminimalkan galat dari dua proses ke n > 2 dalam model siaran stokastik

Pierre Fraigniaud; Boaz Patt-Shamir; Sergio Rajsbaum· 2026· DOI 10.48550/arXiv.2608.27336

Masalah inti

Makalah ini menyelidiki konsensus biner dalam **model siaran stokastik**, yaitu pengaturan komunikasi sinkron dengan n \geq 2 proses. Pada setiap putaran, setiap proses menyiarkan pesan ke semua proses lain. Setiap siaran berhasil secara independen dengan probabilitas p \in [0, 1] . Jika suatu siaran berhasil, semua proses menerima pesan tersebut; jika gagal, tidak ada proses yang menerimanya. Yang krusial, pengirim tidak mengetahui apakah siarannya berhasil atau gagal. Di bawah asumsi ini, konsensus deterministik **tidak dapat diselesaikan**: ketidakpastian yang ditimbulkan oleh kegagalan siaran yang senyap mencegah proses menjamin kesepakatan. Para penulis karena itu merumuskan ulang masalahnya sebagai tugas optimisasi: untuk jumlah putaran tetap r, rancang algoritma konsensus yang berhenti tepat dalam r putaran sambil meminimalkan probabilitas galat ketidaksepakatan. Karya sebelumnya [DISC 2025] mempelajari masalah ini secara mendalam untuk kasus khusus n = 2 proses. Makalah ini memperluas kajian tersebut ke kasus umum n > 2 .

Hasil utama makalah ini diperkirakan mencakup: - **Pencirian probabilitas galat optimal**: Untuk setiap n > 2, p \in [0, 1], dan anggaran putaran r, para penulis memberikan probabilitas ketidaksepakatan minimum yang dapat dicapai, mungkin sebagai ekspresi bentuk tertutup atau rekurens yang dapat dihitung. - **Konstruksi algoritma**: Algoritma konsensus r -putaran eksplisit yang mencapai probabilitas galat optimal, menggeneralisasi solusi dua proses dari DISC 2025. - **Batas bawah**: Bukti bahwa tidak ada algoritma r -putaran yang dapat mencapai probabilitas galat lebih kecil, sehingga menetapkan optimalitas. - **Ketergantungan pada n dan p **: Analisis tentang bagaimana galat optimal berskala dengan jumlah proses dan probabilitas keberhasilan siaran, termasuk kasus tepi p = 0, p = 1, dan p \to 0 . Meskipun abstrak tidak mencantumkan hasil numerik spesifik, kontribusinya adalah perluasan rigor teori konsensus di bawah siaran stokastik ke jumlah proses yang arbitrer.

Makalah ini menyelidiki konsensus biner dalam **model siaran stokastik**, yaitu pengaturan komunikasi sinkron dengan n \geq 2 proses. Pada setiap putaran, setiap proses menyiarkan pesan ke semua proses lain. Setiap siaran berhasil secara independen dengan probabilitas p \in [0, 1] . Jika suatu siaran berhasil, semua proses menerima pesan tersebut; jika gagal, tidak ada proses yang menerimanya. Yang krusial, pengirim tidak mengetahui apakah siarannya berhasil atau gagal.

Di bawah asumsi ini, konsensus deterministik **tidak dapat diselesaikan**: ketidakpastian yang ditimbulkan oleh kegagalan siaran yang senyap mencegah proses menjamin kesepakatan. Para penulis karena itu merumuskan ulang masalahnya sebagai tugas optimisasi: untuk jumlah putaran tetap r, rancang algoritma konsensus yang berhenti tepat dalam r putaran sambil meminimalkan probabilitas galat ketidaksepakatan. Karya sebelumnya [DISC 2025] mempelajari masalah ini secara mendalam untuk kasus khusus n = 2 proses. Makalah ini memperluas kajian tersebut ke kasus umum n > 2 .

Model siaran stokastik menangkap skenario realistis dalam jaringan nirkabel dan rawan gangguan ketika kehilangan pesan bersifat senyap dan berkorelasi antar penerima. Ketidakterpecahan konsensus eksak memotivasi pendekatan minimisasi galat, yang sangat relevan untuk sistem dengan tenggat waktu keras (r tetap). Perluasan ke n > 2 tidak trivial karena ruang keadaan tumbuh secara eksponensial dan simetri antar proses runtuh ketika beberapa siaran gagal. Hasil para penulis kemungkinan mengungkap ambang batas pada p dan r ketika kesepakatan menjadi hampir pasti, dan mereka mungkin menunjukkan bahwa strategi optimal melibatkan penyeimbangan pengaruh masukan lokal setiap proses secara cermat. Arsitektur konseptual model dapat direpresentasikan sebagai berikut: Diagram ini menggambarkan bahwa setiap siaran berhasil secara independen dengan probabilitas p, dan semua proses menerima himpunan pesan berhasil yang sama. Ketiadaan umpan balik bagi pengirim merupakan kendala yang kritis. Karya mendatang dapat membahas varian asinkron, kegagalan Bizantium, atau konsensus bernilai banyak. Temuan makalah ini berkontribusi pada fondasi teoretis komputasi terdistribusi yang toleran terhadap kesalahan di bawah komunikasi stokastik.

Praktisi dan peneliti ilmu komputer

Membuka konten member…