🔢 mathematics

Completion-Shock Queues: Departure-Induced Invalidation and Endogenous Service Correlation

यह शोध पत्र एक एकल-सर्वर FCFS कतार का विश्लेषण करता है जहाँ कार्य पूर्णता (job completions) ऐसे संभाव्य झटकों (probabilistic shocks) को सक्रिय करती है जो प्रतीक्षा कर रहे कार्यों को अमान्य कर देते हैं, जिससे उनके सुधार (remediation) की आवश्यकता होती है, और सिस्टम के प्रदर्शन पर ऐसे अंतर्जात सेवा सहसंबंधों (endogenous service correlations) के प्रभाव को मापने के लिए सटीक स्थिरता स्थितियों, स्थिर वितरणों (stationary distributions) और भारी-ट्रैफ़िक दंड (heavy-traffic penalties) को व्युत्पन्न करता है।

मूल लेखक: Igor Kleiner

प्रकाशित 2026-09-07

📖 7 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Igor Kleiner

मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

चीजों के सिस्टम के माध्यम से गति करने के अध्ययन में, जैसे कि राजमार्ग पर कारों से लेकर नेटवर्क पर डेटा पैकेटों तक, वैज्ञानिक अक्सर एक सरल मानसिक मॉडल पर भरोसा करते हैं: सेवा के लिए प्रतीक्षा कर रहे लोगों की एक पंक्ति। इस मॉडल के सबसे बुनियादी संस्करण में, जब एक व्यक्ति अपना टर्न पूरा करके जाता है, तो उनके पीछे प्रतीक्षा कर रहे लोगों द्वारा किए जाने वाले कार्य की मात्रा बिल्कुल समान रहती है। पंक्ति बस छोटी हो जाती है। यह धारणा गणित को प्रबंधनीय बनाती है और कई स्थितियों में अच्छी तरह काम करती है, लेकिन यह जटिल, परस्पर जुड़े कार्यों की वास्तविकता को पकड़ने में विफल रहती है। सॉफ्टवेयर विकास, इंजीनियरिंग या डेटा प्रोसेसिंग में, एक कार्य को पूरा करने से कभी-कभी प्रतीक्षा सूची में मौजूद कार्यों की प्रकृति बदल सकती है। एक नया कोड अपडेट पहले से तैयार किए गए टिकट को अमान्य कर सकता है, या एक डिजाइन निर्णय टीम को पहले से किए गए कार्य को फिर से करने के लिए मजबूर कर सकता है। जब एक काम को पूरा करने की क्रिया प्रतीक्षा में मौजूद अन्य कामों की आवश्यकताओं को बदल देती है, तो सिस्टम मानक मॉडलों की तुलना में बहुत अलग व्यवहार करता है।

होलोन इंस्टीट्यूट ऑफ टेक्नोलॉजी के एक शोधकर्ता ने ठीक इस घटना का पता लगाने के लिए एक नया गणितीय मॉडल बनाया है, जिसे उन्होंने "कम्प्लीशन-शॉक" (पूर्णता-आघात) कतार कहा है। यह अध्ययन एक एकल सर्वर पर केंद्रित है जो यादृच्छिक रूप से आने वाले कार्यों के प्रवाह को संभालता है। सामान्य परिस्थितियों में, एक कार्य "क्लीन" (स्वच्छ) होता है और उसे पूरा करने में एक निश्चित समय लगता है। हालांकि, यह मॉडल एक मोड़ पेश करता है: हर बार जब कोई कार्य सिस्टम से बाहर जाता है, तो एक "शॉक" (आघात) होने की संभावना होती है। यह शॉक अभी निकले हुए कार्य को प्रभावित नहीं करता है; इसके बजाय, यह लाइन में प्रतीक्षा कर रहे अगले दो कार्यों पर नज़र रखता है। यदि प्रतीक्षा कर रहे वे कार्य अभी भी अपनी मूल, क्लीन अवस्था में हैं, तो शॉक उन्हें "इनवैलिडेटेड" (अमान्य) घोषित कर देता है। एक अमान्य कार्य को तुरंत प्रोसेस नहीं किया जा सकता; इसे सामान्य सेवा के लिए लाइन के सामने वापस आने से पहले समस्या को ठीक करने के लिए एक सुधार चरण (रेमेडिएशन फेज) से गुजरना होगा। महत्वपूर्ण रूप से, यह शॉक सिस्टम द्वारा स्वयं उत्पन्न किया जाता है—एक कार्य की समाप्ति ही अन्य कार्यों के लिए अतिरिक्त कार्य को जन्म देती है।

शोधकर्ता ने पाया कि यह स्व-जनित फीडबैक लूप सिस्टम की क्षमता को नाटकीय रूप से कम कर देता है। एक मानक लाइन में जहाँ कार्य एक-दूसरे को प्रभावित नहीं करते हैं, सिस्टम एक निश्चित सीमा तक आगमन दर (अराइवल रेट) को संभाल सकता है इससे पहले कि वह अस्थिर हो जाए और लाइन अनंत रूप से लंबी हो जाए। इस नए मॉडल में, इन पूर्णता-प्रेरित शॉक्स की उपस्थिति का अर्थ है कि सिस्टम बहुत कम आगमन दर पर अस्थिर हो जाता है। उदाहरण के लिए, यदि शॉक होने की संभावना तीस प्रतिशत है, तो सिस्टम उस ट्रैफिक का केवल दो-तिहाई हिस्सा ही संभाल सकता है जिसे वह बिना किसी शॉक के प्रबंधित कर सकता था। लाइन अस्थिर इसलिए नहीं होती क्योंकि बहुत अधिक काम आ रहे हैं, बल्कि इसलिए होती है क्योंकि आने वाले कार्य एक-दूसरे के लिए अधिक काम पैदा कर रहे हैं, जिससे सिस्टम अंदर से ही अवरुद्ध हो जाता है।

यह समझने के लिए कि यह कैसे काम करता है, शोधकर्ता ने कतार को अवस्थाओं (स्टेट्स) की एक श्रृंखला के रूप में माना। जब लाइन पर्याप्त लंबी होती है, तो सिस्टम को लाइन में पहले दो लोगों की स्थिति को देखकर वर्णित किया जा सकता है: चाहे वे क्लीन हों या अमान्य। यह अवस्थाओं के बीच विभिन्न प्रकार के मूवमेंट का एक विशिष्ट पैटर्न बनाता है, जिसका शोधकर्ता ने "क्वासी-बर्थ-एंड-डेथ प्रोसेस" नामक पद्धति का उपयोग करके विश्लेषण किया। इस दृष्टिकोण ने सिस्टम की स्थिरता और इसके दीर्घकालिक व्यवहार की सटीक गणना करने की अनुमति दी। परिणामों ने दिखाया कि सिस्टम केवल तभी स्थिर रहता है जब नए कार्यों की आगमन दर इतनी कम हो कि वह मूल कार्य और शॉक्स के कारण होने वाले अतिरिक्त सुधार कार्य, दोनों को साफ करने की दर द्वारा संतुलित की जा सके।

सबसे आश्चर्यजनक निष्कर्षों में से एक लाइन में मौजूद कार्यों के बीच का संबंध है। एक मानक कतार में, एक व्यक्ति को सेवा देने में लगने वाला समय आमतौर पर अगले व्यक्ति को सेवा देने में लगने वाले समय से स्वतंत्र होता है। इस शॉक मॉडल में, सेवा का समय आपस में जुड़ जाता है। क्योंकि एक एकल शॉक दो लगातार कार्यों को अमान्य कर सकता है, इसलिए एक कार्य के लिए सुधार की आवश्यकता दूसरे कार्य के लिए सुधार की आवश्यकता से सांख्यिकीय रूप से जुड़ी होती है। शोधकर्ता ने सिद्ध किया कि यह संबंध केवल तत्काल पड़ोसी तक ही सीमित है; लाइन में दो स्थान नीचे वाला कार्य उसी शॉक घटना से सीधे प्रभावित नहीं होता है। यह निर्भरता का एक विशिष्ट, पूर्वानुमेय पैटर्न बनाता है जहाँ लाइन का इतिहास उसके भविष्य को प्रभावित करता है, लेकिन केवल एक छोटी दूरी के लिए।

अध्ययन ने यह भी देखा कि क्या होता है जब सिस्टम को उसकी पूर्ण सीमा तक धकेला जाता है, जिसे "हेवी ट्रैफिक" (भारी यातायात) की स्थिति कहा जाता है। इस ब्रेकिंग पॉइंट के पास सिस्टम के गणितीय विवरण का विस्तार करके, शोधकर्ता ने एक सटीक गुणांक (कोएफिशिएंट) निकाला है जो अस्थिरता के करीब पहुँचने पर लाइन के बढ़ने का वर्णन करता है। एक मानक सिस्टम (जहाँ कार्य स्वतंत्र हैं लेकिन उनका औसत सेवा समय समान है) के साथ तुलना करने पर, शॉक-संचालित सिस्टम लगातार खराब प्रदर्शन करता है। शॉक्स द्वारा निर्मित अतिरिक्त कार्य सिस्टम की दक्षता पर एक मापने योग्य दंड (पेनल्टी) लगाता है। यह पाया गया कि यह दंड सख्ती से सकारात्मक (स्ट्रिक्टली पॉजिटिव) है, जिसका अर्थ है कि कार्यों के बीच की निर्भरता हमेशा कतार को लंबा और प्रतीक्षा समय को अधिक बनाती है, भले ही कार्य को ठीक करने का औसत समय समान क्यों न रहे।

इन सैद्धांतिक परिणामों की शुद्धता सुनिश्चित करने के लिए, शोधकर्ता ने एक कंप्यूटर सिमुलेशन बनाया जिसने सरलीकृत गणितीय समूहों पर निर्भर रहने के बजाय प्रत्येक कार्य और उसकी विशिष्ट स्थिति को ट्रैक किया। सिमुलेशन ने उच्च सटीकता के साथ सैद्धांतिक भविष्यवाणियों की पुष्टि की, जिससे पता चला कि गणितीय मॉडल सिस्टम के व्यवहार को सटीक रूप से पकड़ता है। अध्ययन ने यह भी पता लगाया कि क्या होता है यदि शॉक लाइन में और आगे तक पहुँच जाए, जो दो के बजाय तीन कार्यों को प्रभावित करता है। हालाँकि उस परिदृश्य में गणित अधिक जटिल हो जाता है, लेकिन मौलिक सिद्धांत वही रहता है: शॉक की सीमा यह निर्धारित करती है कि निर्भरता कितनी दूर तक विस्तारित होती है, जो कतार के माध्यम से फैलने वाली अतिरिक्त कार्य की एक श्रृंखला अभिक्रिया (चेन रिएक्शन) बनाती है।

यह कार्य उन प्रणालियों को समझने का एक सुलभ तरीका प्रदान करता है जहाँ एक क्षेत्र में सफलता दूसरे में विफलता पैदा करती है। यह एक निष्क्रिय कतार के विचार से आगे बढ़ता है, जहाँ प्रतीक्षा कर रहे कार्य केवल बैठे रहते हैं, और यह पहचानता है कि कतार स्वयं भविष्य के कार्यभार को उत्पन्न करने में एक सक्रिय भागीदार है। निष्कर्ष बताते हैं कि किसी भी ऐसे सिस्टम में जहाँ अपस्ट्रीम परिवर्तन डाउनस्ट्रीम तैयारियों को अमान्य कर सकते हैं, सिस्टम की क्षमता केवल इस बात का मामला नहीं है कि सर्वर कितनी तेजी से काम करता है, बल्कि इस बात का भी है कि एक कार्य की पूर्णता प्रतीक्षा कर रहे कार्यों की आवश्यकताओं को कैसे नया रूप देती है। यह मॉडल इन सीमाओं की गणना करने के लिए एक स्पष्ट, सटीक ढांचा प्रदान करता है, जो दिखाता है कि परस्पर निर्भरता की लागत प्रदर्शन में वास्तविक, मापने योग्य कमी है।

तकनीकी सारांश: कंप्लीशन-शॉक क्यूज़ (Completion-Shock Queues): प्रस्थान-प्रेरित अमान्यता और अंतर्जात सेवा सहसंबंध

समस्या विवरण
पारंपरिक कतार मॉडल (queueing models) आमतौर पर यह मानते हैं कि एक सेवा पूर्णता (service completion) केवल कार्यभार को कम करती है, जिससे शेष ग्राहकों की सेवा आवश्यकताएं अपरिवर्तित रहती हैं। हालांकि, उन प्रणालियों में जिनमें आश्रित कार्य मदें (dependent work items) शामिल हैं—जैसे कि सॉफ्टवेयर विकास, इंजीनियरिंग डिज़ाइन, या डेटा पाइपलाइन—एक सफल पूर्णता उन धारणाओं या कॉन्फ़िगरेशन को अमान्य कर सकती है जिनका उपयोग लंबित कार्यों के लिए किया जा रहा था, जिससे पुन: कार्य (rework) की आवश्यकता होती है। यह शोध पत्र एक ऐसी कतार प्रणाली का समाधान करता है जहाँ एक जॉब के प्रस्थान (departure) से प्रतीक्षा कर रहे जॉब्स की सेवा आवश्यकताओं में वृद्धि हो सकती है। विशेष रूप से, यह मॉडल एक सिंगल-सर्वर, फर्स्ट-कम-फर्स्ट-सर्वर्ड (FCFS) कतार की जांच करता है जहाँ एक प्रस्थान के बाद "कंप्लीशन शॉक" (completion shock) उत्पन्न हो सकता है, जो प्रतीक्षा की पहली दो स्थितियों को अमान्य कर देता है। अमान्य किए गए जॉब्स को मानक सेवा प्राप्त करने से पहले एक अतिरिक्त सुधार चरण (remediation phase) से गुजरना पड़ता है। महत्वपूर्ण रूप से, यह निर्भरता अंतर्जात (endogenous) है: प्रतीक्षा कर रहे जॉब्स की सेवा आवश्यकताएं किसी बाह्य संकेत या पूर्व-निर्धारित सहसंबंध संरचना के बजाय, कतार की अपनी प्रस्थान प्रक्रिया द्वारा निर्धारित होती हैं।

कार्यप्रणाली (Methodology)
लेखक इस प्रणाली को एक निरंतर-समय मार्कोव चेन (CTMC) के रूप में मॉडल करते हैं।

स्टेट स्पेस (State Space): सिस्टम नौकरियों की संख्या $N(t)$ और प्रतीक्षा की पहली दो स्थितियों के "मार्क्स" (Clean या Invalidated) को ट्रैक करता है। $N(t) \ge 2$ के लिए, स्टेट को मार्क्स के जोड़े द्वारा परिभाषित किया जाता है, जिसके परिणामस्वरूप चार चरण (00, 01, 10, 11) प्राप्त होते हैं।
गतिशीलता (Dynamics):
- जॉब्स $\lambda$ दर वाले पॉइसन प्रोसेस (Poisson process) के माध्यम से आते हैं।
- 'क्लीन' जॉब्स को $\mu$ दर पर सेवा दी जाती है; 'इनवैलिडेटेड' जॉब्स को $\nu$ दर पर सुधार (remediation) से गुजरना पड़ता है, जिसके बाद वे 'क्लीन' होकर सेवा में प्रवेश करते हैं।
- एक प्रस्थान (departure) पर, प्रायिकता $p$ के साथ एक सामान्य शॉक (common shock) होता है। यह शॉक प्रतीक्षा की पहली दो स्थितियों का निरीक्षण करता है, और वहां मौजूद किसी भी 'क्लीन' जॉब को 'इनवैलिडेटेड' में बदल देता है। 'इनवैलिडेटेड' जॉब्स 'इनवैलिडेटेड' ही रहते हैं (इनवैलिडेशन का संचय/stacking नहीं होता है)।
विश्लेषणात्मक ढांचा (Analytical Framework):
- $N(t) \ge 2$ के लिए, सिस्टम को एक क्वासी-बर्थ-एंड-डेथ (QBD) प्रक्रिया के रूप में दर्शाया गया है जिसमें चार-चरणों वाली संरचना है।
- विश्लेषण मैट्रिक्स-एनालिटिक विधियों का उपयोग करता है, विशेष रूप से $R$ दर मैट्रिक्स को हल करने के लिए जो द्विघात मैट्रिक्स समीकरण $A_+ + RA_0 + R^2A_- = 0$ को संतुष्ट करता है।
- हेवी-ट्रैफिक विश्लेषण (Heavy-Traffic Analysis): शोध पत्र QBD कर्नेल के क्रिटिकल डबल रूट पर प्रत्यक्ष विस्तार (direct expansion) का उपयोग करके प्रथम-क्रम के हेवी-ट्रैफिक गुणांकों को प्राप्त करता है।
- सत्यापन (Validation): सैद्धांतिक परिणामों को एक कस्टमर-लेवल डिस्क्रीट-इवेंट सिमुलेशन के विरुद्ध सत्यापित किया गया है, जो QBD पुनरावृत्ति (recursion) पर निर्भर रहने के बजाय स्पष्ट रूप से इनवैलिडेशन मार्क्स को ट्रैक करता है।

प्रमुख योगदान और परिणाम

सटीक स्थिरता स्थिति (Exact Stability Condition):
यह शोध पत्र इस प्रणाली के लिए एक सटीक स्थिरता सीमा (stability boundary) व्युत्पन्न करता है। कतार तभी पॉजिटिव रिकरेंट (positive recurrent) है यदि और केवल यदि:
$\lambda \left( \frac{1}{\mu} + \frac{2p - p^2}{\nu} \right) < 1$
यह दर्शाता है कि प्रभावी क्षमता (effective capacity) शॉक की प्रायिकता ( $p$ ) और सुधार दर ( $\nu$ ) द्वारा कम हो जाती है। उदाहरण के लिए, यदि $\mu = \nu$ और $p=0.3$ है, तो स्वीकार्य बाहरी लोड $\rho < 1$ (मानक M/M/1) से घटकर $\rho < 0.662$ हो जाता है।
मैट्रिक्स-जियोमेट्रिक स्टेशनरी सॉल्यूशन (Matrix-Geometric Stationary Solution):
लेखक एक मैट्रिक्स-जियोमेट्रिक स्टेशनरी डिस्ट्रीब्यूशन ( $\pi_n = \pi_2 R^{n-2}$ के लिए $n \ge 2$ ) और सिस्टम में नौकरियों की औसत संख्या ( $E[N]$ ) तथा सुधार की वास्तविक अंश ( $\alpha_{eff}$ ) के लिए स्पष्ट सूत्र प्रदान करते हैं। यह दिखाया गया है कि सुधार का अंश अंतर्जात है, जो सिस्टम लोड के साथ बढ़ता है और संतृप्त सीमा (saturated limit) $\alpha = p(2-p)$ के करीब पहुँच जाता है।
संतृप्त सहसंबंध संरचना (Saturated Correlation Structure):
एक स्थायी रूप से बैकलॉग वाली प्रणाली में, शोध पत्र यह सिद्ध करता है कि इनवैलिडेशन इंडिकेटर्स का क्रम सटीक रूप से 1-डिपेंडेंट (1-dependent) है।
- आसन्न सेवा समय (adjacent service times) के बीच कोवेरिएंस (covariance) को $Cov(S_n, S_{n+1}) = \frac{p(1-p)^3}{\nu^2}$ के रूप में व्युत्पन्न किया गया है।
- लैग $k \ge 2$ के लिए कोवेरिएंस शून्य हो जाता है।
- यह उन मॉडलों के विपरीत है जहाँ निर्भरता बाह्य रूप से थोपी जाती है; यहाँ, 1-डिपेंडेंस स्वाभाविक रूप से शॉक विंडो के पहले दो स्थानों पर ओवरलैप होने से उत्पन्न होता है।
हेवी-ट्रैफिक पेनल्टी (Heavy-Traffic Penalty):
एक प्रत्यक्ष QBD कर्नेल विस्तार का उपयोग करते हुए, शोध पत्र सटीक प्रथम-क्रम हेवी-ट्रैफिक गुणांक प्राप्त करता है। यह स्थापित करता है कि, समान संतृप्त मार्जिनल सर्विस-टाइम डिस्ट्रीब्यूशन वाले IID कतार की तुलना में, कंप्लीशन-प्रेरित निर्भरता एक सकारात्मक हेवी-ट्रैफिक पेनल्टी उत्पन्न करती है।
- पेनल्टी अनुपात $H_{sat}$ , 1 से स्पष्ट रूप से अधिक है।
- अधिकतम पेनल्टी $p^* \approx 0.177$ पर होती है, जहाँ अनुपात लगभग 1.060 है।
- यह "शुद्ध निर्भरता प्रभाव" (pure dependence effect) को अलग करता है, यह दिखाते हुए कि भले ही मार्जिनल डिस्ट्रीब्यूशन समान हों, कतार की गतिशीलता से उत्पन्न सहसंबंध भीड़भाड़ (congestion) को बढ़ाता है।

महत्व और दावे
शोध पत्र का दावा है कि यह स्थानीय पुन: कार्य प्रसार (local rework propagation) के लिए एक सुगम कतार मॉडल (tractable queueing model) प्रदान करता है, जहाँ सेवा निर्भरता बाहरी इनपुट के बजाय सिस्टम की अपनी गतिशीलता द्वारा उत्पन्न होती है।

सैद्धांतिक योगदान: यह अंतर्जात सेवा सहसंबंध वाले सिस्टम के लिए सटीक स्टेशनरी और हेवी-ट्रैफिक परिणाम प्रदान करता है, जो एक ऐसा वर्ग है जिसे अक्सर अनुमानों (approximations) की आवश्यकता होती है।
तंत्र अलगाव (Mechanism Isolation): शॉक रेडियस को $d=2$ पर स्थिर करके, यह मॉडल उस न्यूनतम स्थानीय नियम का प्रतिनिधित्व करता जहाँ शॉक विंडो ओवरलैप होकर निर्भरता पैदा करती है, जो इसे $d=1$ (IID) और बड़े रेडियस (उच्च-क्रम निर्भरता) से अलग करता है।
परिचालन अंतर्दृष्टि (Operational Insight): परिणाम रेखांकित करते हैं कि निर्भर कार्य मदों वाली प्रणालियाँ उन लोड पर भी अस्थिर हो सकती हैं जो मानक मॉडलों में स्थिर होते, और भीड़भाड़ एक फीडबैक लूप बनाता है जहाँ उच्च लोड लंबित जॉब्स को इनवैलिडेशन के प्रति अधिक संवेदनशील बना देता है, जिससे सेवा आवश्यकताएं और बढ़ जाती हैं।

लेखक नोट करते हैं कि हालांकि विश्लेषण को एक विश्लेषणात्मक रूप से छोटे स्टेट स्पेस (चार चरण) को बनाए रखने के लिए $d=2$ तक सीमित रखा गया है, फिर भी यह ढांचा एक पदानुक्रम (hierarchy) का सुझाव देता है जहाँ बड़े रेडियस ( $d=3$ , आदि) $(d-1)$ -डिपेंडेंट अनुक्रमों के साथ बड़े फेज स्पेस उत्पन्न करेंगे। यह कार्य यह समझने के दिशा में एक आधारभूत कदम है कि कैसे प्रस्थान-प्रेरित अमान्यीकरण (departure-induced invalidation) FCFS प्रणालियों में पुन: कार्य को प्रसारित करता है।

इसी तरह के और पेपर