Apakah ada daftar masalah kanonik dalam sistem terdistribusi?

Minggu lalu, saya membaca lagi trasncript Leslie Lamport tahun 1982 tentang konferensi yang dia berikan tentang Soal-soal yang Terselesaikan, Masalah yang Tidak Terselesaikan , dan Non-Masalah dalam Concurrency . Makalah ini mudah dibaca, tetapi salah satu hal yang membuat saya berpikir adalah pernyataan berikut:

Bisakah masalah dianggap sebagai masalah pengecualian bersama atau masalah produsen-konsumen, atau kombinasi keduanya?

Saya ingin tahu apakah pertanyaan ini telah dijawab untuk kasus sistem terdistribusi.

Apakah ada satu set masalah sistem terdistribusi kanonik dari mana semua kemungkinan masalah sistem terdistribusi dapat dikurangi menjadi? Apa daftar kanonik ini?

Jika tidak ada daftar kanonik apa daftar masalah saat ini dan pengurangan apa yang ada?

Sebagai contoh, saya akan mengatakan dengan sangat naif bahwa masalah pemilihan pemimpin dan saling pengecualian dapat dikurangi menjadi masalah konsensus. Saya juga akan mengatakan bahwa snapshot yang didistribusikan dapat dikurangi menjadi jam yang didistribusikan. Apakah benar atau salah?

Jika memungkinkan, saya lebih suka bahwa jawabannya memberikan referensi ke makalah / buku yang diterbitkan yang mendukung klaimnya :)

Apakah ada satu set masalah sistem terdistribusi kanonik dari mana semua kemungkinan masalah sistem terdistribusi dapat dikurangi menjadi?

Saya tidak mengetahui daftar masalah yang dipublikasikan.

Perlu diingat bahwa ada banyak model yang berbeda (dan agak tak tertandingi) dalam komputasi terdistribusi, mulai dari model sinkron (bebas-kesalahan) yang "jinak" di mana node dieksekusi dalam putaran langkah-kunci dan semua pesan disampaikan secara andal di setiap putaran, hingga model asinkron di mana tidak ada batasan pada kecepatan pemrosesan dan penundaan pesan dan node itu sendiri mungkin crash atau mengirim pesan yang rusak. Untuk lebih menambah variasi ini, ada persyaratan dan asumsi lain yang ortogonal terhadap sinkronisasi dan kesalahan: pengetahuan awal node (ukuran jaringan, diameter jaringan, derajat node maksimum, dll.), Kemampuan untuk meminta detektor kegagalan , apakah node memiliki pengidentifikasi unik, atomicity langkah-langkah kirim & terima, ukuran maksimum satu pesan, dan banyak lagi.

$2$

Ketika melihat kegagalan di sisi lain, pertanyaannya lebih terkait dengan masalah solvabilitas seperti "Apakah konsensus dapat dipecahkan dalam model ini?" atau "Bisakah kita menerapkan detektor kegagalan mewah ini di bawah asumsi ini?"

Jika tidak ada daftar kanonik apa daftar masalah saat ini dan pengurangan apa yang ada?

Ada banyak contoh pengurangan seperti itu dalam model komputasi terdistribusi tertentu, saya akan membatasi jawaban saya untuk 2 berikut:

Perhitungan lokal dalam model sinkron (bebas kesalahan)

$\Omega(\sqrt{\log n} + \log\Delta)$$n$$\Delta$$2$$A$$A$

Model Asinkron dengan Kegagalan Kerusakan

Di sini masalah yang paling banyak dipelajari adalah konsensus yang toleran terhadap kesalahan dan banyak variasinya, karena menerapkan primitif dasar seperti siaran atom dan atau sinkronisasi sendiri membutuhkan konsensus.

$S$ $P$$T$$P$$S$

$P$$Q$$P$$Q$$k$

Sebagai contoh, saya akan mengatakan dengan sangat naif bahwa masalah pemilihan pemimpin dan saling pengecualian dapat dikurangi menjadi masalah konsensus.

Tentu, jika Anda dapat menyelesaikan konsensus, Anda segera memiliki algoritma untuk pemilihan pemimpin: Cukup gunakan ID dari setiap node sebagai input untuk algoritma konsensus. Cara sebaliknya hanya berlaku pada model di mana dijamin bahwa pemimpin akhirnya diketahui semua orang.

[1] Pierre Fraigniaud: Kompleksitas komputasi terdistribusi: apakah Anda kecanduan volvo atau terobsesi dengan nascar? PODC 2010. http://doi.acm.org/10.1145/1835698.1835700

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Komputasi Lokal: Batas Bawah dan Batas Atas. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

[3] Tushar Deepak Chandra, Sam Toueg: Detektor Kegagalan yang Tidak Dapat Diandalkan untuk Sistem Terdistribusi yang Andal. J. ACM 43 (2): 225-267 (1996). http://doi.acm.org/10.1145/226643.226647

[4] Prasad Jayanti, Sam Toueg: Setiap masalah memiliki detektor kegagalan yang paling lemah. PODC 2008: 75-84. http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: Detektor Kegagalan Terlemah untuk Memecahkan Konsensus. J. ACM 43 (4): 685-722 (1996) http://doi.acm.org/10.1145/234533.234549

[6] Michel Raynal: Detektor Kegagalan Memecahkan Perjanjian k-Set Asynchronous: Sekilas Hasil Terbaru. Buletin EATCS 103: 74-95 (2011) http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61