Apa keuntungan merancang algoritma terdistribusi deterministik?

10

Algoritma terdistribusi yang tahan terhadap kegagalan dapat bersifat deterministik atau probabilistik. Ambil contoh masalah konsensus.

  • Paxos adalah deterministik dalam arti bahwa mengingat asumsi yang dibuatnya, ia selalu berhasil.

  • Dalam konstrast, konsensus acak bekerja dengan probabilitas yang diberikan.

Apa keuntungan merancang dan menggunakan algoritma deterministik?

Asumsi yang diandalkan oleh algoritma deterministik juga memiliki kemungkinan untuk bertahan dalam kenyataan (apa yang disebut cakupan asumsi mereka ). Oleh karena itu, selalu ada kemungkinan bahwa algoritma deterministik tidak berfungsi dalam kenyataan.

randomized-algorithms dc.distributed-comp fault-tolerance danyhow
sumber
Paxos / wikipedia, keluarga protokol
vzn
1
Bisakah Anda sedikit lebih spesifik dengan komentar Anda?
danyhow
1
Adalah baik untuk dicatat bahwa pengacakan digunakan secara khusus untuk sifat hidup bukan sifat keamanan. Sifat-sifat keselamatan selalu berlaku, namun ada kemungkinan algoritma tidak berakhir (yang biasanya berkurang seiring waktu).
Kaveh

Jawaban:

10

Saya akan menjawab ini dari perspektif algoritma grafik terdistribusi (algoritma terdistribusi yang memecahkan masalah grafik yang berkaitan dengan struktur jaringan komunikasi).

Berikut adalah beberapa alasan yang tidak jelas untuk merancang algoritma terdistribusi deterministik dalam pengaturan ini:

  • Subrutin dalam algoritma acak . Pada p. 12–13 dari slide ini , Elkin menguraikan teknik desain algoritma di mana Anda dapat menggunakan algoritma terdistribusi deterministik cepat sebagai subrutin untuk membangun algoritma terdistribusi acak cepat . Menariknya, tidak mungkin untuk menggunakan algoritma acak khas sebagai subrutin dalam konteks yang sama (probabilitas kesalahan akan terlalu tinggi).

  • Toleransi kesalahan . Ada terjemahan mekanis yang memungkinkan Anda untuk mengubah algoritma terdistribusi deterministik cepat menjadi algoritma terdistribusi mandiri cepat (lihat misalnya Bagian 2.4 dari survei ini ). Konversi serupa tidak dikenal untuk algoritma acak (dan saya pikir itu tidak mungkin ada dalam kasus umum).

Jukka Suomela
sumber