इस परिदृश्य में एक पैक्सोस एजेंट के लिए उचित व्यवहार क्या है?

Question

मैं पैक्सोस में देख रहा हूं और मैं उलझन में हूं कि एल्गोरिदम को इस प्रदूषित उदाहरण में कैसे व्यवहार करना चाहिए। मुझे आशा है कि नीचे दिया गया चित्र परिदृश्य बताता है।

कुछ अंक:

• प्रत्येक एजेंट एक प्रस्तावक/स्वीकर्ता/शिक्षार्थी के रूप में कार्य करता है
• तैयार संदेशों रूप (instance, proposal_num)
• का प्रस्ताव संदेश है प्रपत्र (instance, proposal_num, proposal_val)
• Server1 और सर्वर 2 दोनों एक ही समय में प्रस्ताव प्रक्रिया शुरू करने का निर्णय लेते हैं
• शुरुआत संदेशों एम 1, M2 और M3 में एक साथ होते हैं

यह यहाँ है कि हालांकि प्रोटोकॉल 'सही' है, यानी केवल एक मान S2 चुना जाता है लगता है, Server1 और Server2 मानना ​​है कि यह क्योंकि अलग से चुना गया था प्रस्ताव संख्या

क्या पैक्सोस एल्गोरिदम केवल तभी समाप्त होता है जब Decide(...) संदेश शिक्षार्थियों को भेजा जाता है? मुझे गलतफहमी होना चाहिए पैक्सोस मेड सरल लेकिन मैंने सोचा कि चुनाव को उनके Propose(...) संदेशों के लिए कोरम हासिल करने के पल को चुना गया था।

यदि विकल्प केवल Decide(...) संदेश एजेंटों को भेजे जाने के बाद किया गया है, तो सर्वर 2 को Decide(1, 5, S2) भेजना चाहिए जब यह ठीक हो जाए क्योंकि यह बाद में Prepare(1, 7) देखा गया था? फिर से परिभाषित

Answer 1

बस वाला शर्तें (चलो भी 1 बाहर फेंक क्योंकि हम केवल एक Paxos यात्रा जायज़ा ले रहे हैं):

1) का प्रस्ताव (एन) == प्रस्ताव (एन), वर्तमान के साथ एक प्रस्तावक से संदेश पहचान एन

2) AcceptPrepare (n, v) == ack (n, v), प्रेजेंटर को भेजा गया संदेश n। v खाली है अगर इस नोड ने अभी तक कोई मान स्वीकार नहीं किया है, o.w. v

3) CreateDecide (n, v) == स्वीकार करें! (x, v), नोड्स को इस मान को पहचान x के साथ स्वीकार करने के लिए पूछने के लिए पूछता है। नोड्स संदेश को खारिज कर देंगे अगर उन्होंने एक तैयार (एन) संदेश लिखा है जहां n> x

तैयार करने के लिए कोरम प्राप्त होने के बाद (एन) - यानी, बहुमत ने संदेश लिखा है - तो पहचान एन के साथ प्रस्तावक एक आदेश स्वीकार करता है! (एन, वी)। यदि एक तैयार (एन + एक्स), एक्स> 0, पहचान एन + एक्स के साथ एक प्रस्तावक द्वारा भेजा गया था - और यह बहुमत से है - एएके (एन, वी) संदेशों और स्वीकार के बीच! (n, v), तो बहुमत ने वादा किया है कि टाइमस्टैम्प < एन + एक्स, एक्स> 0 (एकेए नोड्स स्वीकृति को अस्वीकार कर देगा!)

पसंद के रूप में बनाया गया है जैसे ही बहुमत को स्वीकार होता है! (एन, वी) संदेश जिसे उन्होंने अनदेखा करने का वादा नहीं किया है।

इस प्रकार, जब server2 ऑनलाइन वापस आता है और इसे स्वीकार! (5, एस 2) भेजता है, यह ध्यान नहीं दिया जाएगा क्योंकि 5 < 7.

Answer 2

स्वीकार किए जाते हैं जवाब के लिए एक जवाब देने के लिए, एल्गोरिथ्म ही वास्तव में जरूरत है कभी नहीं को किसी भी बहुत अच्छी तरह से परिभाषित अर्थ में समाप्त करें।एल्गोरिदम में अपनी भागीदारी को व्यक्तिगत रूप से समाप्त करने वाले प्रत्येक नोड के बारे में बात करना अधिक समझ में आता है, जो कार्यान्वयन-परिभाषित है। तो शायद आप कह सकते हैं कि एल्गोरिदम स्वयं समाप्त हो गया है जब सभी भाग लेने वाले नोड्स निकल गए हैं, अगर यह जानना उपयोगी था।

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

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

प्रत्येक नोड एल्गोरिदम में अपनी भागीदारी को समाप्त कर सकता है, जब यह पता चलता है कि एल्गोरिदम किस प्रकार परिवर्तित हुआ है, हालांकि यह आपके कार्यान्वयन बाधाओं के आधार पर लंबे समय तक भाग लेना पसंद कर सकता है।

आपको खुद को यह समझाने में विफलता-सहिष्णुता के बारे में कुछ सोचना होगा कि समाप्त होने पर निर्णय समाप्त हो गया है: यदि सभी नोड्स जो जानते हैं कि किस मूल्य का फैसला किया गया था, वे इसे साझा करने से पहले मरने के लिए थे, फिर भी प्रगति होगी ? जवाब सौभाग्य से है, हां: जब तक नोड्स का बहुमत जीवित रहता है, यदि उनमें से कोई भी निर्धारित मूल्य जानता है तो यह इसे दूसरों के साथ साझा कर सकता है, और यदि नहीं तो वहां भाग लेने वाले नोड्स का बहुमत है जिसे बस चुनना है एक उच्च मतपत्र संख्या और एक और दौर चलाते हैं। !

विकल्प जैसे ही बहुमत जो वे नहीं है एक को स्वीकार (एन, वी) संदेश प्राप्त किया जाता है:

---

एक बात स्वीकार किए जाते हैं जवाब में की सावधान रहना होगा इस वाक्यांश है अनदेखा करने का वादा किया।

सबसे पहले, वहाँ प्रोटोकॉल के बारे में AcceptPropose संदेशों की उपेक्षा का वादा में कुछ भी नहीं है। वादे से संबंधित Propose मैसेज को अनदेखा/अस्वीकार कर दिया जाना चाहिए। AcceptPropose संदेशों में से अधिकांश हमेशा का उपयोग मतपत्र के बावजूद चुने गए मूल्य को जानने के लिए किया जा सकता है।

दूसरी बात, जैसे ही बहुमत AcceptPropose संदेश भेजता है, तो विकल्प प्रभावी ढंग से बनाया जाता है। आप इसे सीधे नहीं देख सकते हैं, इसलिए आपको यह जानने से पहले कि कम से कम एक नोड को बहुमत से AcceptPropose संदेश प्राप्त हुए हैं, तब तक प्रतीक्षा करना होगा। एक बार ऐसा होने के बाद, आप AcceptPropose संदेशों के माध्यम से या Decided संदेशों के प्रसारण/गपशप के माध्यम से चुने गए मूल्य को साझा कर सकते हैं, जो आपके कार्यान्वयन की बाधाओं को बेहतर बनाता है।