संदेश पासिंग और साझा मेमोरी

संदेश पासिंग (message passing) और साझा मेमोरी (shared memory) दो मूलभूत अवधारणाएँ हैं जिनके माध्यम से समवर्ती प्रक्रियाएँ (concurrent processes) परस्पर क्रिया करती हैं, और वितरित कंप्यूटिंग (distributed computing) का अधिकांश अध्ययन इस बात पर केंद्रित है कि एक को दूसरे के साथ कैसे अनुकरण (simulate) किया जाए।

Definition

संदेश-पासिंग मॉडल में प्रक्रियाएँ केवल चैनलों (channels) पर संदेश भेजकर और प्राप्त करके संचार करती हैं; साझा-मेमोरी मॉडल में वे रजिस्टरों (registers) जैसी साझा वस्तुओं को पढ़कर और लिखकर संचार करती हैं। प्रत्येक अपनी स्वयं की शुद्धता शर्तों (correctness conditions) के साथ एक सटीक कम्प्यूटेशनल मॉडल है।

Scope

यह विषय पॉइंट-टू-पॉइंट (point-to-point) और ब्रॉडकास्ट संदेश-पासिंग मॉडल (broadcast message-passing models) को उनकी डिलीवरी और ऑर्डरिंग सिमेंटिक्स (delivery and ordering semantics) के साथ, रीड/राइट रजिस्टरों (read/write registers) और मजबूत सिंक्रनाइज़ेशन ऑब्जेक्ट्स (stronger synchronization objects) से निर्मित साझा-मेमोरी मॉडल (shared-memory models) को, और उन शास्त्रीय परिणामों को शामिल करता है जो दर्शाते हैं कि विभिन्न विफलता धारणाओं (failure assumptions) के तहत संदेश पासिंग के ऊपर साझा मेमोरी का अनुकरण (और इसके विपरीत) कैसे किया जा सकता है। इसमें रजिस्टर पदानुक्रम (register hierarchy) और सर्वसम्मति पदानुक्रम (consensus hierarchy) भी शामिल है जो साझा वस्तुओं की शक्ति को रैंक करते हैं।

Core questions

• एक चैनल क्या डिलीवरी और ऑर्डरिंग गारंटी प्रदान करता है, और वे एल्गोरिथम डिज़ाइन को कैसे प्रभावित करते हैं?
• क्या एक अविश्वसनीय संदेश-पासिंग नेटवर्क के शीर्ष पर एक साझा-मेमोरी अमूर्तता को मज़बूती से बनाया जा सकता है?
• सर्वसम्मति को हल करने की अपनी शक्ति में सिंक्रनाइज़ेशन ऑब्जेक्ट्स कैसे भिन्न होते हैं?

Key theories

रजिस्टर और सर्वसम्मति पदानुक्रम

साझा वस्तुओं को उनकी सर्वसम्मति संख्या (consensus number) द्वारा रैंक किया जाता है—प्रक्रियाओं की अधिकतम संख्या जिसके लिए वे वेट-फ्री सर्वसम्मति (wait-free consensus) को हल कर सकते हैं—सरल रीड/राइट रजिस्टरों को सबसे नीचे और तुलना-और-स्वैप (compare-and-swap) जैसी सार्वभौमिक वस्तुओं को सबसे ऊपर रखते हुए।

रजिस्टर निर्माण

लैम्पर्ट का सुरक्षित (safe), नियमित (regular) और परमाणु (atomic) रजिस्टरों का पदानुक्रम, और कमजोर रजिस्टरों से मजबूत रजिस्टरों का निर्माण, यह औपचारिक रूप देता है कि समवर्ती रीड और राइट्स का सही ढंग से व्यवहार करने का क्या अर्थ है।

संदेश पासिंग पर साझा मेमोरी का अनुकरण

परमाणु एकल-लेखक (single-writer) और बहु-लेखक (multi-writer) रजिस्टरों को कोरम तकनीकों (quorum techniques) का उपयोग करके क्रैश विफलताओं (crash failures) के अल्पसंख्यक को सहन करने वाले एक अतुल्यकालिक संदेश-पासिंग नेटवर्क (asynchronous message-passing network) पर अनुकरण किया जा सकता है, जिससे दो संचार मॉडल एकीकृत होते हैं।

Clinical relevance

संदेश-पासिंग/साझा-मेमोरी का अंतर सीधे वास्तविक प्लेटफॉर्म पर लागू होता है: क्लस्टर (clusters) और क्लाउड (cloud) संदेश-पासिंग सिस्टम हैं, मल्टीकोर सर्वर (multicore servers) साझा मेमोरी प्रदान करते हैं, और वितरित कुंजी-मूल्य स्टोर (distributed key-value stores) प्रभावी रूप से एक संदेश-पासिंग नेटवर्क पर एक साझा-रजिस्टर अमूर्तता (shared-register abstraction) प्रस्तुत करते हैं।

History

लैम्पर्ट (Lamport) के 1986 के पत्रों ने समवर्ती रजिस्टरों (concurrent registers) को औपचारिक रूप दिया; हर्लिही (Herlihy) के 1991 के वेट-फ्री पदानुक्रम (wait-free hierarchy) ने सर्वसम्मति संख्या (consensus number) द्वारा सिंक्रनाइज़ेशन प्रिमिटिव (synchronization primitives) को रैंक किया; और अत्तिया (Attiya) और वेल्च (Welch) के पाठ ने संदेश पासिंग और साझा मेमोरी से संबंधित सिमुलेशन को समेकित किया, जिससे इस क्षेत्र के मूल में द्वैत (duality) स्थापित हुआ।

Key figures

• Leslie Lamport
• Maurice Herlihy
• Nir Shavit
• Hagit Attiya
• Jennifer Welch

Seminal works

• herlihy2008
• attiya2004
• lamport1986

Frequently asked questions

क्या संदेश पासिंग और साझा मेमोरी समतुल्य हैं?

वे उपयुक्त विफलता धारणाओं (failure assumptions) के तहत कम्प्यूटेशनल शक्ति में समतुल्य हैं—प्रत्येक दूसरे का अनुकरण कर सकता है—लेकिन वे प्रोग्रामिंग सुविधा और प्रदर्शन में तेजी से भिन्न होते हैं, यही कारण है कि सिस्टम एक को अपने मूल मॉडल के रूप में चुनते हैं।