kompleksitas gosip acak

Masalah gosip dalam sistem terdistribusi adalah sebagai berikut. Kami memiliki grafik dengan simpul. Setiap simpul memiliki pesan yang harus kirim ke semua node. $G$ $n$ $v$ $m_v$

Sekarang, pertanyaan saya adalah dalam konteks model jaringan ad-hoc (kami berasumsi bahwa sebuah node tidak memiliki pengetahuan sebelumnya tentang topologi jaringan, derajat masuk dan keluarnya, dan himpunan tetangganya. hanya pengetahuan dari masing-masing node adalah pengidentifikasi sendiri dan jumlah total node).

Saya juga berasumsi bahwa semua node memiliki akses ke jam global dan bekerja secara serentak dalam langkah waktu diskrit yang disebut putaran.

Kompleksitas suatu algoritma dalam konteks ini adalah jumlah putaran yang dibutuhkan untuk penyelesaian.

Saya ingat bahwa ada algoritma yang memecahkan masalah gosip di putaran dengan probabilitas tinggi. Tetapi saya tidak dapat menemukan referensi lagi, dan saya bertanya-tanya apakah ada hasil yang lebih baru dalam hal ini. $O(n \log ^2 n)$

sunting mengikuti komentar yang bijaksana: pada setiap putaran sebuah node dapat mengirimkan pesan ke semua tetangganya dan dapat menerima pesan dari mereka. Suatu simpul akan menerima pesan pada putaran tertentu jika dan hanya jika persis salah satu tetangganya mentransmisikan pada putaran itu. Kalau tidak tabrakan terjadi dan tidak ada pesan yang diterima oleh node.

reference-request dc.distributed-comp Sylvain Peyronnet
sumber

Saya kira Anda mengasumsikan bahwa dalam setiap putaran setiap node dapat mengirim pesan ke hanya satu tetangga? Kalau tidak, masalahnya sepele untuk dipecahkan dalam putaran

...

O (n)

$O(n)$

Jukka Suomela

Oups, lupa menyebutkan tentang itu, saya mengeditnya.

Sylvain Peyronnet

Jika simpul

telah menerima pesan

dan

kaleng itu mengirimkan

v

$v$

m_{u}

$m_u$

m_{w}

$m_w$

dalam satu putaran atau ditransmisikan pesan terbatas pada ukuran satu payload saja?

{m_{v}, m_{u}, m_{w}}

$\{m_v,m_u,m_w\}$

Warren Schudy

Bisakah node mengetahui perbedaan antara tabrakan dan tidak ada yang mentransmisikan?

Warren Schudy

Apakah grafik koneksi adalah grafik terarah terhubung sangat sewenang-wenang?

Warren Schudy

kompleksitas gosip acak

Jawaban: