Mesin Turing Terdistribusi?

10

Saya seorang mahasiswa master yang berfokus pada sistem terdistribusi tetapi juga tertarik pada ilmu komputer teoretis. Saya bertanya-tanya apakah ada representasi formal dari sistem terdistribusi di atas mesin turing? Artinya, apakah mungkin untuk memperluas (membuat varian) konsep mesin turing untuk mengambil keuntungan dari komputasi terdistribusi?

Satu ide, adalah membuat rekaman bersama (sesuatu yang mirip dengan Tuple Space ) antara TM.

turing-machines dc.distributed-comp Marcos Roriz Junior
sumber
8
Mungkin terkait: cstheory.stackexchange.com/questions/426/…
Jukka Suomela
3
pertanyaan yang ditautkan Jukka mungkin tidak menjawab pertanyaan Anda sepenuhnya. Jika demikian, mungkin Anda bisa menutup yang ini, dan jika tidak, mungkin Anda bisa menjelaskan apa yang berbeda?
Suresh Venkat
@ Suresh Venkat, saya pikir pertanyaan yang dihubungkan Jukka jelas tentang topik, tetapi tanyakan pertanyaan yang lebih besar: "mengapa tidak ada model standar / dapat diterima untuk komputasi terdistribusi?". Pertanyaan saya pasti ada hubungannya dengan yang satu itu, tetapi saya termotivasi untuk mencari tentang / representasi formal komputasi terdistribusi.
Marcos Roriz Junior
baik. itu terdengar masuk akal.
Suresh Venkat
2
Omong-omong, pendekatan "shared tape" Anda terdengar lebih seperti model komputasi paralel daripada komputasi terdistribusi . Oleh karena itu mungkin juga masuk akal untuk melihat model yang digunakan dalam bidang komputasi paralel (misalnya, model PRAM).
Jukka Suomela

Jawaban:

10

[Apakah ada] representasi formal dari sistem terdistribusi di atas mesin turing?

Mengenai hal ini, diskusi (lihat tautan yang diposting oleh Jukka pada komentar) adalah cara untuk melihatnya. Caranya, saya melihatnya, bagaimana Anda akan secara formal mewakili sistem terdistribusi sangat tergantung pada bagaimana Anda melihatnya, dan itu tergantung pada "asumsi sistem favorit Anda" (yaitu, asumsi pada sinkronisasi (yaitu, waktu relatif tindakan dalam distribusi) sistem), tentang komunikasi (menyampaikan pesan vs memori bersama), pada kesalahan (dari proses dan / atau tautan, jinak atau Bizantium, dll.) Karena masyarakat tidak menyetujui hal ini, juga tidak ada kesepakatan mengenai formalisme dasar .

[Apakah] mungkin untuk memperluas (membuat varian) konsep mesin turing untuk memanfaatkan komputasi terdistribusi?

Saya kira itu sepenuhnya mungkin, tetapi tidak seorang pun (yang saya tahu) telah memeriksanya. Yang saya tahu adalah ini:

  1. IO Automata berjangka waktu juga digunakan dalam buku Komputasi Terdistribusi Lynch
  2. Mengkomunikasikan Proses Berurutan
  3. Logika temporal dari tindakan
  4. Pi-Calculus (juga sudah disebutkan oleh Alex)
  5. Dan banyak lagi (telah dan akan disebutkan di sini) ...
Martin B.
sumber
Terima kasih atas penjelasannya. Poin yang Anda buat tentang perselisihan tentang bagaimana model seharusnya (sinkronisasi, async, dll) pasti berdampak pada pembuatan model standar. Tautan bagus, dan terima kasih telah menjawab :-).
Marcos Roriz Junior
6

Anda mungkin ingin melihat Pi-Calculus.

http://en.wikipedia.org/wiki/%CE%A0-calculus

Merupakan kalkulus berbasis diproses yang dirancang untuk alasan tentang sistem terdistribusi.

Alex Gonopolskiy
sumber
Model yang sangat menarik :-). Saya akan membacanya akhir pekan ini.
Marcos Roriz Junior
5

Saya terkejut bahwa Petri Nets belum disebutkan! Ekstensi Jaring Petri seperti Jaring Petri Berwarna atau Jaring Petri dengan busur penghambat sudah selesai-Turing.

Dai Le
sumber
Petri nets adalah formalisme penting dalam konkurensi, tetapi karena motivasi mereka datang dari mencoba memodelkan proses fisik tertentu, mereka tidak benar-benar sebanding dengan TM.
Charles Stewart
Hanya Petri sendiri yang bersikeras menerapkannya pada sistem fisik. Mereka sebagian besar digunakan untuk menggambarkan perangkat lunak berkomunikasi, proses bisnis, dan sebagainya.
reinierpost
5

( Peringatan: pandangan yang agak bias, penyederhanaan berlebihan, dan generalisasi terang-terangan di depan. )

Seringkali perbedaan antara komputasi terdistribusi dan komputasi paralel dapat diringkas sebagai berikut:

  • Dalam komputasi terdistribusi , ukuran kompleksitas utama terkait dengan arus komunikasi dan informasi : berapa banyak putaran komunikasi ("waktu"); berapa banyak bit yang dikirimkan.
  • Dalam komputasi paralel , langkah-langkah kompleksitas utama terkait dengan perhitungan dan pemrosesan informasi : berapa banyak langkah dasar ("waktu"); berapa banyak bit yang disimpan.

Jika Anda mengambil perspektif ini, maka sering kali ternyata untuk memodelkan sistem terdistribusi, tidak terlalu penting bahwa kekuatan komputasi seperti apa yang dimiliki node Anda (atau prosesor atau komputer).

O(n)

XX

TT

Oleh karena itu menggunakan mesin Turing sebagai titik awal untuk memodelkan sistem terdistribusi terdengar agak tidak alami bagi saya: jika ini merupakan aspek yang tidak relevan, mengapa membangun semuanya di atasnya? Di sisi lain, dalam komputasi paralel hal ini wajar (kecuali bahwa modelnya biasanya mirip dengan PRAM dan bukan mesin Turing).

Jukka Suomela
sumber
3

Beberapa berpendapat bahwa tergantung pada pandangan Anda, Anda bisa menganggap sistem terdistribusi sebagai sesuatu yang lebih kuat daripada Mesin Turing, karena interpretasi yang berbeda dari batasan non-determinisme dan keadilan. Tautan ini memiliki diskusi menarik tentang topik tersebut. Herlihy / Shavit dalam buku mereka "Seni pemrograman multiprosesor" berpendapat bahwa Turing komputabilitas secara inheren mengacu pada gagasan tentang algoritma (berurutan), dan dalam beberapa hal tidak sesuai untuk alasan tentang komputasi terdistribusi. Saya harus menyebutkan bahwa ini bisa diperdebatkan dan kontroversial jadi saya harap tidak ada yang melempari saya dengan batu karena saya mengatakan ini.

Giovanni Funchal
sumber
1
Saya pikir perbandingannya tidak terlalu tepat. Sederhananya, dalam konteks mesin Turing, non-determinisme adalah sumber daya: ini mengacu pada kemampuan mesin untuk mengikuti beberapa jalur eksekusi secara bersamaan, karena itu pada dasarnya merupakan bentuk paralelisme. Dalam konteks sistem terdistribusi, sebaliknya, non-determinisme biasanya lebih merupakan penghalang: ia digunakan untuk memodelkan berbagai sifat yang tidak dapat diprediksi dari sistem terdistribusi dunia nyata, seperti kurangnya sinkronisasi dan kegagalan.
Antonio Valerio Miceli-Barone