Mengapa kita tidak dapat mengembangkan teori kompleksitas komputasi terdistribusi yang disatukan?

Bidang komputasi terdistribusi telah gagal dalam mengembangkan teori matematika tunggal untuk menggambarkan algoritma terdistribusi. Ada beberapa 'model' dan kerangka kerja komputasi terdistribusi yang sama sekali tidak kompatibel satu sama lain. Ledakan semata-mata dari berbagai sifat temporal (asinkron, sinkron, sinkron parsial), berbagai komunikasi primitif (passing pesan vs memori bersama, siaran vs. unicast), beberapa model kesalahan (gagal berhenti, kerusakan pulih, kirim kelalaian, Bizantium, dan sebagainya) pada) telah meninggalkan kita dengan sejumlah model sistem, kerangka kerja, dan metodologi sistem yang tidak dapat dipecahkan, yang membandingkan hasil solvabilitas relatif dan batas yang lebih rendah di seluruh model dan kerangka kerja ini telah menjadi sulit, sulit dipraktekkan, dan kadang-kadang, tidak mungkin.

Pertanyaan saya sangat sederhana, mengapa begitu? Apa yang secara mendasar berbeda tentang komputasi terdistribusi (dari mitra sekuensialnya) sehingga kami belum dapat menyusun penelitian menjadi teori terpadu komputasi terdistribusi? Dengan komputasi berurutan, Mesin Turing, Fungsi Rekursif, dan Kalkulus Lambda semuanya dipotong setara. Apakah ini hanya keberuntungan, atau apakah kita benar-benar melakukan pekerjaan yang baik dalam meng-enkapsulasi komputasi sekuensial dengan cara yang belum dapat dicapai dengan komputasi terdistribusi?

Dengan kata lain, apakah komputasi terdistribusi secara inheren tidak mau menyerah pada teori yang elegan (dan jika ya, bagaimana dan mengapa?), Atau kita tidak cukup pintar untuk menemukan teori seperti itu?

Satu-satunya referensi yang dapat saya temukan yang membahas masalah ini adalah: " Menilai dua dekade penelitian teori komputasi terdistribusi " oleh Fischer dan Merritt DOI: 10.1007 / s00446-003-0096-6

Referensi atau paparan apa pun akan sangat membantu.

Menurut saya, model komputasi mesin Turing yang termotivasi secara abstrak merupakan pendekatan teknologi yang baik hingga saat ini, sedangkan model komputasi terdistribusi, sejak awal, telah dimotivasi oleh dunia nyata, yang selalu lebih berantakan daripada abstraksi.

Dari, katakanlah, 1940-1995, ukuran contoh masalah, "relatif tidak penting" paralelisme dan konkurensi, dan skala makro perangkat komputasi, semua "bersekongkol" untuk menjaga mesin Turing sebagai perkiraan yang sangat baik dari komputer dunia nyata. Namun, begitu Anda mulai berurusan dengan dataset besar, kebutuhan di mana-mana untuk konkurensi, biologi melalui lensa algoritmik, dll., Akan jauh lebih tidak jelas jika ada model komputasi "intuitif". Mungkin masalah yang sulit dalam satu model tidak sulit - komputasional kurang kompleks - di lain. Jadi saya percaya bahwa kompleksitas komputasi mainstream akhirnya mengejar (!) Dengan komputasi terdistribusi, dengan mulai mempertimbangkan beberapa model komputasi dan struktur data, dimotivasi oleh pertimbangan dunia nyata.

Saya akan menjawab ini dari perspektif masalah grafik klasik (atau masalah input / output): kami memiliki jaringan, setiap node mendapatkan sesuatu sebagai input dan setiap node harus menghasilkan sesuatu sebagai output. Saya kira ini paling dekat dengan dunia kompleksitas komputasi tradisional.

Saya pasti bias, tapi saya berpikir bahwa dalam pengaturan ini, ada adalah sederhana dan model yang cukup umum digunakan dari komputasi terdistribusi: algoritma didistribusikan sinkron , dengan definisi yang berjalan waktu = jumlah putaran sinkron . Dalam terminologi Peleg, ini adalah model LOCAL .

Model ini bagus karena memiliki sangat sedikit "komponen bergerak", tidak ada parameter, dll. Namun demikian, ini sangat konkret: masuk akal untuk mengatakan bahwa waktu berjalan suatu algoritma tepat 15 dalam model ini. Dan Anda dapat membuktikan batas bawah tanpa syarat, teori informasi: dari perspektif ini, kompleksitas yang terdistribusi dari banyak masalah grafik (misalnya, pewarnaan grafik) cukup dipahami dengan baik.

Model ini juga menyediakan pendekatan terpadu untuk banyak aspek komputasi terdistribusi:

• Pesan-lewat vs memori bersama, disiarkan vs unicast: Tidak relevan dalam model ini.
• $\alpha$
• Anda ingin memiliki algoritme untuk jaringan dinamis, atau Anda ingin pulih dari kegagalan? Nah, jika algoritma sinkron Anda bersifat deterministik, maka Anda dapat menggunakannya untuk membuat algoritme stabilisasi diri . Sekali lagi, kompleksitas waktu pada dasarnya tidak terpengaruh.

Sekarang semua ini baik-baik saja selama Anda mempelajari masalah yang "benar-benar didistribusikan" dalam arti bahwa waktu berjalan algoritma Anda lebih kecil dari diameter grafik , yaitu, tidak ada simpul yang perlu memiliki informasi lengkap tentang struktur grafik. Namun, ada juga banyak masalah yang inheren global: algoritma tercepat dalam model ini memiliki waktu berjalan yang linier dalam diameter grafik. Dalam mempelajari masalah-masalah itu, model di atas tidak lagi masuk akal, dan kemudian kita perlu menggunakan sesuatu yang lain. Biasanya, seseorang mulai memperhatikan jumlah total pesan atau bit yang dikomunikasikan dalam jaringan. Itulah salah satu alasan mengapa kami mendapatkan beberapa model berbeda.

Maka tentu saja kita memiliki masalah bahwa komunitas komputasi terdistribusi sebenarnya adalah dua komunitas yang berbeda, dengan mengejutkan beberapa kesamaan . Jika Anda menyatukan semua model dari dua komunitas, tentu akan terlihat sedikit membingungkan ... Jawaban saya di atas hanya terkait dengan setengah dari komunitas; Saya percaya orang lain akan mengisi tentang setengah lainnya.

Satu ide romantis untuk menangkap berbagai model komputasi terdistribusi adalah melalui topologi aljabar. Gagasan intinya adalah membangun kompleks sederhana dengan membiarkan titik menjadi status proses, masing-masing dilabeli dengan id proses. Ini adalah primer pada topik. Jawaban terdekat untuk pertanyaan Anda mungkin telah disentuh oleh Eli Gafni dalam makalahnya - Terdistribusi komputasi - Secercah teori. Dalam makalahnya, ia menunjukkan simulasi bagaimana memulai dengan memori bersama async untuk dua-tiga prosesor (untuk kegagalan berhenti dan Bizantium) -dia menunjukkan bagaimana bisa menerapkan ini pada model pesan yang lewat. Penting untuk memahami simulasinya adalah gagasan melihat komputasi terdistribusi secara topologis

Saya pikir situasinya terlihat sangat berbeda jika dilihat dalam konteks: mulai dari karya awal dan hasil ketidakmungkinan pada perjanjian Bizantium ( PSL80 LSP82 FLP85), segera jelas bahwa masalah mendasar dalam komputasi terdistribusi hanya dapat diselesaikan sama sekali dengan asumsi sinkronisasi yang ketat dan tingkat redundansi yang tinggi. Karena batas bawah sumber daya teoretis tanpa syarat ini dianggap tidak layak untuk tujuan praktis apa pun, penelitian difokuskan pada pengembangan model yang lebih halus yang memungkinkan pengorbanan yang lebih baik dari asumsi (misalnya pada penjaminan waktu atau mode kegagalan) vs. jaminan (yaitu jumlah kesalahan serentak dari jenis apa pada jenis komponen apa yang ditoleransi, mis. prosesor, tautan) untuk memberikan alat perancang sistem alat untuk menemukan pertukaran yang tepat untuk sistem yang ada.