Ketika suatu proses memunculkan proses lain

Latar belakang saya adalah teori / logika kompleksitas (di mana hanya ada satu proses sebagian besar waktu), dan dalam komputasi terdistribusi (di mana ada proses, dan satu atau lebih mungkin gagal dari waktu ke waktu). Namun, saya sekarang ingin dapat mengatakan sesuatu tentang proses pemijahan / membuat / memintal proses lain. Apakah ada kekakuan dalam komputasi paralel, sistem operasi, dll., Yang menyebabkan ini? $n$

Motivasi:

Saya mencoba membuat model yang abstrak fitur tertentu dari interaksi molekuler. Saya ingin mengatakan bahwa rangkaian reaksi kimia adalah proses independen, dan bahwa pada langkah waktu tertentu , ia menumbuhkan proses independen lain . Secara intuitif, hal-hal ini terasa seperti proses independen, karena mereka tidak memiliki kontak satu sama lain setelah waktu - atau sangat sedikit kontak, hanya saling bertukar "pesan." $S$ $t$ $S'$ $t$

Lebih formal:

(1) Apakah ada definisi CS yang sudah ada sebelumnya yang menangkap gagasan dari satu proses melahirkan proses independen lain? Saya terutama tertarik untuk dapat membatasi di mana $S$ berhenti dan $S'$ dimulai, dan mengapa itu "masuk akal" untuk dilakukan.

(2) Jika ada lebih dari satu jawaban untuk (1), apa yang Anda anggap pro dan kontra terhadap berbagai definisi?

(Catatan: Saya tidak tahu cara memberi tag ini dengan tepat, dan berencana untuk memberi tag ulang tergantung pada jawabannya.)

dc.parallel-comp process-algebra Aaron Sterling
sumber

Saya selalu menemukan forksystem call dalam sistem operasi mirip Unix secara konsep sangat elegan. Anda dapat melihatnya sebagai operasi atom yang menduplikasi proses saat ini. Sebelum bercabang, hanya ada satu proses , sedangkan setelah bercabang, ada dua proses dan . Jika kita menyederhanakan hal-hal, dan adalah identik dalam semua aspek lainnya, kecuali bahwa ada indikator satu-bit yang memungkinkan tahu bahwa itu adalah 'baru' proses sementara tahu bahwa itu adalah 'asli' proses. Setelah itu dan dapat berlanjut secara terpisah, dan mereka bahkan bisa

S

$S$

S

$S$

S^{'}

$S'$

S

$S$

S^{'}

$S'$

S^{'}

$S'$

S

$S$

S

$S$

S^{'}

$S'$ modifikasi sendiri .

Jukka Suomela

@Jukka: Terima kasih :-) Akan lebih baik jika ada cara untuk menghubungkan apa yang saya lakukan ke primitif Unix.

Aaron Sterling

Jawaban:

Tentu saja ada banyak sistem untuk proses pemodelan. Ini termasuk dalam kategori proses aljabar . Contoh kuncinya adalah -calculus , CCS , ACP dan CSP . $\pi$

Kalkulator proses memiliki mekanisme dasar untuk menentukan perilaku proses termasuk: mengirim dan menerima pesan (sinkron atau asinkron), menciptakan proses paralel, pilihan nondeterministik antara perilaku, dan replikasi proses. Meskipun kalkulus kecil dalam hal jumlah konstruksi, mereka sangat ekspresif dan sejumlah besar penelitian telah dilakukan untuk mempelajari sifat mereka.

The kalkulus berbeda dari yang lain dalam bahwa hal itu memungkinkan, pada dasarnya, proses yang akan dilalui sebagai nilai-nilai kelas. Ini sebenarnya memungkinkan nama saluran untuk diedarkan sebagai nilai kelas pertama, memungkinkan perubahan dalam topologi dinamis. Ini mungkin kalkulus yang Anda inginkan karena ia menawarkan dinamika terbesar. $\pi$

CSP (mengkomunikasikan proses sekuensial) sedikit aneh, jika dilihat dari perspektif pemodelan molekul. Itu memang memiliki banyak dukungan teori dan alat pendukung. (Diciptakan oleh CAR Hoare.)

CCS dan ACP memiliki dinamika kurang dari kalkulus, tetapi mereka jauh lebih mudah untuk dianalisis dan disimulasikan. Toolset padat yang disebut CRL (dan CRL2) tersedia untuk ACP. Alat serupa pasti ada untuk CCS. $\pi$ $\mu$ $\mu$

Saya akan mulai memeriksa pekerjaan terkait (lihat di bawah) dan kemudian menemukan formalisme pemodelan mana yang sesuai dengan apa yang Anda cari.

Sebenarnya ada cukup banyak pemodelan kerja reaksi kimia dan proses biologis menggunakan proses aljabar. Mungkin tempat terbaik untuk melihat adalah daftar publikasi Luca Cardelli . Seluruh lini penelitiannya tentang BioComputing mungkin memiliki 30 makalah tentang topik ini. Pembicaraan ini memberikan gambaran tentang banyak pekerjaannya. Ini salah satu sedikit lebih formal, meskipun membaca koran benar-benar satu-satunya cara untuk melihat rincian.

Salah satu pendekatan yang secara langsung memodelkan proses kimia adalah CHAM (mesin abstrak kimia). Bahan utama di sini adalah solusi dari molekul dan membran. Ada aturan pemanasan dan pendinginan untuk mengatur ulang molekul dan untuk menghilangkan sampah. Aturan-aturan ini dapat dibalik. Akhirnya ada reaksi yang menentukan model reaksi. Berbeda dengan proses aljabar, model CHAM tidak begitu khawatir tentang sintaksis proses, sehingga Anda dapat menemukan representasi molekul Anda sendiri.

Tulis ulang logika seperti yang direalisasikan dalam toolset Maude menawarkan pendekatan lain yang kurang lebih langsung untuk menentukan reaksi seperti itu. Orang hanya perlu menentukan aturan penulisan ulang, penyerahan "sup" otomatis. Toolset akan memungkinkan simulasi dan analisis reaksi kimia (bertubuh kecil). Varian probabilistik Maude juga ada.

Dave Clarke
sumber

Bisakah petri-nets juga dipertimbangkan di antara kemungkinan? forking dapat dimodelkan dengan memiliki tempat dengan dua transisi keluar.

M. Alaggan

Secara lebih umum, interaksi gaya petri-net dapat dimodelkan dalam logika linier (misalnya, meskipun bukan satu-satunya, lihat "Kerangka kerja logis bersamaan: Fragmen proposisional" oleh Watkins et al, TYPES 2003)

Rob Simmons

Terima kasih, Dave. Dengan lucu, mungkin, salah satu proyek saya adalah memperluas pekerjaan yang dilakukan Cardelli di beberapa makalah pada halaman yang Anda tautkan. Pengetahuan saya tentang aljabar proses terbatas, jadi saya berusaha menghindari formalisasi hal-hal seperti itu, jika mungkin. Cardelli memang mendefinisikan bio-versi dari -calculus, tapi saya tidak memahaminya dengan baik. Pasti membantu Anda berpikir bahwa mungkin itulah arah terbaik untuk pergi. Lebih banyak alasan bagi saya untuk mempelajari formalisme baru paling tidak.

π

$\pi$

Aaron Sterling

@ M. Alaggan: Di permukaan, kelihatannya jaring Petri bisa melakukan pekerjaan itu. Setiap tempat dapat dianggap sebagai kumpulan bahan kimia. Setiap transisi dapat dianggap sebagai reaksi. Jadi jika kita memiliki tempat yang disebut H dan O dan H2O, transisi dapat mengambil dua token dari H satu dari O dan memasukkan satu token ke dalam H2O. Masalah dengan pemodelan dengan cara ini adalah bahwa hanya satu dari masing-masing transisi tersebut yang dapat menyala secara bersamaan, berbeda dengan proses aljabar yang akan memungkinkan banyak transisi semacam itu untuk menyala pada suatu waktu.

Dave Clarke

@ Harun: tergantung pada apa yang Anda coba lakukan, kalki proses yang lebih modern seperti BioPEPA mungkin berguna bagi Anda.

András Salamon

Bidang pekerjaan lain yang - saya percaya - terkait dengan tetapi tidak sama dengan BioComputing (sayangnya saya tidak terlalu berpengalaman dalam bidang ini), adalah "komputasi membran."

Pemahaman saya tentang komputasi membran adalah bahwa ia menggunakan metafora yang sebagian besar dikembangkan di dunia proses-caclui (jawaban Dave Clarke memberikan serangkaian petunjuk yang baik di sana) secara eksplisit untuk memodelkan interaksi seluler. Panduan yang baik untuk komputasi membran mungkin adalah panduan yang tepat untuk komputasi membran oleh Paun dan Rozenberg di TCS. Itu beberapa tahun yang lalu (dan saya tidak berada di dalam paywall saat ini untuk memeriksa) tetapi saya percaya beberapa model komputasi membran memiliki gagasan "forking" yang seharusnya mencerminkan mitosis seluler.

Rob Simmons
sumber

Terima kasih, Rob. Pekerjaan Cardelli tidak menyentuh komputasi membran sejauh yang saya tahu. Ini lebih fokus pada membangun teori bahasa pemrograman untuk sirkuit DNA. Saya menghargai pointer, tapi saya rasa saya sedang mencari sesuatu yang lebih "mainstream" (artinya tidak terkait dengan bio dengan cara apa pun).

Aaron Sterling

Ini tentu alternatif. @ Harun: Cardel Brane Calculus lucacardelli.name/Papers/Brane%20Calculi.pdf memodelkan membran.

Dave Clarke

Ha! Kekuatan crowdsourcing! Terima kasih lagi! :-)

Aaron Sterling