Komputasi di Jaringan Dinamis Anonim dengan Komunikasi Satu Bit

Makalah ini mempelajari komputasi deterministik di **jaringan dinamis anonim** di bawah model komunikasi ekstrem: pada setiap putaran, setiap agen menyiarkan tepat **satu bit**, dan hanya menerima **jumlah tetangga** yang menyiarkan setiap nilai bit (0 atau 1). Agen tidak memiliki pengenal, dan graf komunikasi berubah seiring waktu. Pertanyaan utamanya adalah apakah komputasi global yang kaya—seperti menghitung setiap fungsi terhitung dari multiset masukan—mungkin dilakukan di bawah batasan bandwidth dan anonimitas yang ketat tersebut.

Penulis menjawab secara afirmatif. Dengan satu pemimpin unik dan batas atas $U$ yang diketahui pada ukuran jaringan $n$, mereka memberikan algoritma yang berhenti yang menghitung setiap fungsi terhitung dari multiset masukan dalam $O(n^3{\log }^{2}n+U)$ putaran, untuk masukan yang diambil dari semesta berukuran $N=2^{O(n\log n)}$. Tanpa pengetahuan awal tentang $n$, mereka merancang algoritma yang menstabilkan untuk tugas yang sama yang berjalan dalam $O(n^3{\log }^{2}n)$ putaran. Batas-batas ini pada dasarnya menyamai state of the art untuk model congested, di mana pesan membawa $O(\log n)$ bit dan komputasi umum memerlukan $O(n^3)$ putaran. Hasil yang

Hasil utama diringkas sebagai berikut:

- **Batas atas $U$ yang diketahui pada $n$:** Algoritma yang berhenti menghitung setiap fungsi terhitung dari multiset masukan dalam $O(n^3{\log }^{2}n+U)$ putaran, untuk masukan dari semesta berukuran $N=2^{O(n\log n)}$.
- **$n$ tidak diketahui:** Algoritma yang menstabilkan untuk tugas yang sama berjalan dalam $O(n^3{\log }^{2}n)$ putaran.
- **Jaringan tanpa pemimpin dan multi-pemimpin:** Hasil yang sebanding diperoleh.
- **Batas bawah:** Batas bawah yang hampir menyamai sebesar

Batas-batas ini pada dasarnya menyamai state of the art untuk model congested, di mana pesan membawa $O(\log n)$ bit dan komputasi umum memerlukan $O(n^3)$ putaran. Dengan demikian, daya komputasi jaringan dinamis anonim yang congested pada dasarnya tetap terjaga bahkan ketika setiap pesan dikompresi menjadi satu bit.