Input/output automaton
इनपुट/आउटपुट ऑटोमेटा एक औपचारिक मॉडल प्रदान करता है, जो एक अतुल्यकालिक समवर्ती प्रणाली के अधिकांश प्रकारों का वर्णन करने में लागू होता है। अपने आप में, आई/ओ ऑटोमेटन मॉडल में एक बहुत ही बुनियादी संरचना होती है जो इसे विभिन्न प्रकार की वितरित प्रणालियों का मॉडल बनाने में सक्षम बनाती है। विशिष्ट प्रकार की अतुल्यकालिक प्रणालियों का वर्णन करने के लिए, इस मूल मॉडल में अतिरिक्त संरचना को जोड़ा जाना चाहिए। मॉडल प्रणाली घटकों के बारे में वर्णन और तर्क के लिए एक स्पष्ट विधि प्रस्तुत करता है जैसे कि प्रक्रियाएं और संदेश चैनल जो एक दूसरे के साथ बातचीत करते हैं, जो मनमाने सापेक्ष गति पर काम करते हैं। आई/ओ ऑटोमेटा को पहली बार नैन्सी ए. लिंच और मार्क आर. टटल द्वारा "वितरित एल्गोरिदम के लिए पदानुक्रमित शुद्धता प्रमाण", 1987 में पेश किया गया था। एक आई/ओ ऑटोमेटन एक वितरित प्रणाली घटक को मॉडल करता है जो अन्य प्रणाली घटकों के साथ बातचीत कर सकता है। यह एक सरल प्रकार की अवस्था मशीन है जिसमें संक्रमण नामित क्रियाओं से जुड़े होते हैं। तीन प्रकार की क्रियाएँ होती हैंः इनपुट, आउटपुट और आंतरिक क्रियाएँ। ऑटोमेटन अपने वातावरण के साथ संवाद करने के लिए अपने इनपुट और आउटपुट क्रियाओं का उपयोग करता है, जबकि आंतरिक क्रियाएं केवल ऑटोमेटन को ही दिखाई देती हैं। आंतरिक और उत्पादन क्रियाएँ जो स्वचालित यंत्र द्वारा चुनी और की जाती हैं, उनके विपरीत, इनपुट क्रियाएँ-जो बस पर्यावरण से आती हैं-स्वचालित यंत्र के नियंत्रण में नहीं होती हैं। उदाहरण आई/ओ ऑटोमेटा का उपयोग एक वितरित प्रणाली के अलग-अलग घटकों को मॉडल करने के लिए किया जा सकता है, जैसे कि एक प्रक्रिया, एक संदेश प्रवाह प्रणाली में एक संदेश चैनल, या एक साझा स्मृति प्रणाली में एक साझा डेटा संरचना। प्रक्रिया I/O स्वचालित चित्र 1 एक अतुल्यकालिक संदेश-पारित वितरित प्रणाली में एक प्रक्रिया के लिए I/O स्वचालित का एक उदाहरण दर्शाता है। इस सेटिंग में, प्रोसेस पाई एक संदेश पारित करने वाली प्रणाली का उपयोग करके अन्य प्रक्रियाओं के साथ संवाद करती है। इसकी आउटपुट क्रियाएँ सेंड (एम) आई, जे के रूप में होती हैं, जो पी. जे. को संसाधित करने के लिए सामग्री एम के साथ एक संदेश भेजने वाली प्रक्रिया पी. आई. का प्रतिनिधित्व करती है। इनपुट क्रियाएँ फॉर्म रिसीव (एम) के, आई की होती हैं, जो प्रोसेस पी. के. से प्रोसेस पी. आई. द्वारा सामग्री के साथ संदेश की प्राप्ति का प्रतिनिधित्व करती हैं। (पाई की आंतरिक क्रियाएँ, जो उस एल्गोरिथ्म के अनुरूप होंगी जो प्रक्रिया चल रही है, नहीं दिखाई गई हैं।) एफ. आई. एफ. ओ. संदेश चैनल एक संदेश चैनल को आई/ओ स्वचालित द्वारा भी मॉडल किया जा सकता है। चित्र 2 एक विशिष्ट यूनिडायरेक्शनल एफ. आई. एफ. ओ. चैनल ऑटोमेटन को दर्शाता है, जिसका नाम सी. आई., जे है। इसमें सेंड (एम) आई, जे प्रपत्र की इनपुट क्रियाएँ हैं और रिसीव (एम) आई, जे प्रपत्र की आउटपुट क्रियाएँ हैं। प्रत्येक संदेश m में 0 या 1 (m ω {0,1}) हो सकता है। ऑटोमेटन की स्थिति उन सभी संदेशों की एक एफ. आई. एफ. ओ. कतार को संग्रहीत करती है जो भेजे गए हैं लेकिन अभी तक प्राप्त नहीं हुए हैं। एक विशिष्ट वितरित प्रणाली में जहां प्रक्रिया ऑटोमेटा और संचार चैनल ऑटोमेटा दोनों मौजूद हैं, वे इस तरह से बनाए जाते हैं कि एक ऑटोमेटन के आउटपुट कार्यों का मिलान किया जाता है और दूसरे ऑटोमेटा के समान नाम वाले इनपुट कार्यों के साथ निष्पादित किया जाता है। उदाहरण के लिए, दो प्रक्रियाओं, पाई और पीजे से बनी एक प्रणाली पर विचार करें, और प्रक्रिया पाई से पीजे को संसाधित करने के लिए एक संचार चैनल सीआई, जे पर विचार करें। इस सेटिंग में, प्रोसेस पाई आउटपुट एक्शन सेंड (एम) आई, जे को निष्पादित करता है, अगर और केवल तभी जब चैनल सी, जे भी अपनी सेंड (एम) आई, जे इनपुट एक्शन को निष्पादित करता है। परमाणु पठन/लेखन रजिस्टर चित्र 3 दो प्रक्रियाओं, पी1 और पी2 के साथ एक साझा स्मृति प्रणाली में एक परमाणु पठन/लेखन रजिस्टर आई/ओ ऑटोमेटन को दर्शाता है। रजिस्टर में संग्रहीत मान V पूर्णांक (V bul Z) प्रकार का होता है। ऑटोमेटन की स्थिति इस मूल्य को संग्रहीत करती है। इनपुट क्रियाओं में राइटी (वी) होता है, जो प्रक्रिया पाई का प्रतिनिधित्व करता है जो रजिस्टर में एक मान वी लिखने का अनुरोध करता है (जहां i ω {1,2} और V ω Z), और रेडी, जो एक प्रक्रिया पाई से मेल खाती है जो वर्तमान में रजिस्टर में संग्रहीत मूल्य को पढ़ने का अनुरोध करती है। आउटपुट एक्शन अक्की का उपयोग प्रक्रिया पाई को सूचित करने के लिए किया जाता है कि लेखन अनुरोध सफलतापूर्वक पूरा हो गया है। आउटपुट एक्शन वीआई उस मूल्य वी का प्रतिनिधित्व करता है जिसे प्रोसेस पी. आई. द्वारा पढ़ने के अनुरोध की प्रतिक्रिया के रूप में वापस किया जा रहा है। ऑटोमेटन में आंतरिक क्रियाएं भी शामिल हैं-'लिखें' (वी), जो रजिस्टर में 'वी' का मान लिखती है (ऑटोमेटन की स्थिति को अद्यतन करके), और 'पढ़ें' का प्रदर्शन करती है, जिसका उपयोग राज्य में संग्रहीत 'वी' का मान पढ़ने के लिए किया जाता है। (ये आंतरिक क्रियाएँ चित्र 3 में नहीं दिखाई गई हैं।) एक आई/ओ ऑटोमेटन ए, या बस एक ऑटोमेटन में पाँच घटक होते हैंः सिग (ए) में कहा गया है कि (ए) प्रारंभ (ए) ट्रांस (ए) कार्य (ए) इन पाँच घटकों का वर्णन नीचे किया गया है। हस्ताक्षर आई/ओ ऑटोमेटन ए के औपचारिकरण में प्रारंभिक चरण इसके हस्ताक्षर, सिग (ए) की परिभाषा है। एक हस्ताक्षर एस आई/ओ ऑटोमेटन की क्रियाओं का वर्णन करता है जो क्रियाओं के तीन अलग-अलग सेटों का उपयोग करता हैः इन (एस): इनपुट क्रियाएँ, आउट (एस): आउटपुट क्रियाएँ, और इंट (एस): आंतरिक क्रियाएँ। इनपुट, आउटपुट और आंतरिक कार्यों के उपरोक्त औपचारिकरण के आधार पर, निम्नलिखित वस्तुओं को परिभाषित करना संभव है। ext (S): बाहरी क्रियाएँ, जिन्हें (S) ≤ out (S) स्थानीय (S) में परिभाषित किया गया हैः स्थानीय रूप से नियंत्रित क्रियाएँ, जिन्हें (S) ≤ int (S) extsig (S) के रूप में परिभाषित किया गया हैः बाहरी हस्ताक्षर, जिसे (S) में, बाहर (S), ω) अधिनियमों (S) के रूप में परिभाषित किया गया है, को हस्ताक्षर S के सभी कार्यों के समूह के रूप में परिभाषित किया गया है। यह परिमित स्वचालित की सामान्य धारणा का एक महत्वपूर्ण सामान्यीकरण है, क्योंकि यह काउंटर और असीमित लंबाई की कतारों जैसी असीमित डेटा संरचनाओं के साथ मॉडलिंग प्रणालियों को सक्षम बनाता है। प्रारंभिक अवस्थाओं का समुच्चय (जिसे प्रारंभिक अवस्थाओं के रूप में भी जाना जाता है) अवस्थाओं का एक गैर-खाली उपसमुच्चय है। एकाधिक प्रारंभ अवस्थाओं की अनुमति है ताकि कुछ इनपुट जानकारी को प्रारंभ अवस्थाओं में शामिल किया जा सके। संक्रमण संबंध ऑटोमेटन ए के अवस्था-संक्रमण संबंध को ट्रांस (ए) स्टेट्स (ए) × एक्ट (सिग (ए)) × स्टेट्स (ए) के रूप में दर्शाया जाता है। यह इस गुण को संतुष्ट करता है कि "प्रत्येक अवस्था s और प्रत्येक इनपुट क्रिया π के लिए, एक संक्रमण (s, π, s ') bul ट्रांस (A) है।" एक संक्रमण, जिसे I/O ऑटोमेटन A के एक चरण के रूप में भी जाना जाता है, को ट्रांस (A) के एक तत्व (s, π, s ') के रूप में परिभाषित किया जाता है। एक इनपुट संक्रमण एक संक्रमण (s, π, s ') को संदर्भित करता है जब π एक इनपुट क्रिया है, आउटपुट संक्रमण एक संक्रमण (s, π, s') को इंगित करता है जब π एक आउटपुट क्रिया है और इसी तरह। किसी भी अवस्था s और क्रिया π के लिए, यदि I/O स्वचालित A में रूप (s, π, s ') का कुछ संक्रमण है, तो π को s में सक्षम कहा जाता है। I/O स्वचालित को इनपुट-सक्षम के रूप में वर्णित किया जाता है क्योंकि सभी इनपुट कार्यों को प्रत्येक स्थिति में सक्षम करने की आवश्यकता होती है। एक शांत अवस्था s को एक ऐसी अवस्था के रूप में परिभाषित किया जाता है जहाँ केवल इनपुट क्रियाएँ सक्षम होती हैं। I/O स्वचालित A का पाँचवाँ घटक, कार्य (A), एक कार्य विभाजन है, जिसे A की स्थानीय रूप से नियंत्रित क्रियाओं पर एक समतुल्यता संबंध के रूप में परिभाषित किया गया है, जिसमें अधिक से अधिक कई समतुल्यता वर्ग हैं। अनौपचारिक रूप से, कार्य विभाजन कार्य (ए), ए के भीतर "कार्यों", या "नियंत्रण के धागे" के एक अमूर्त विवरण का प्रतिनिधित्व करता है। इस विभाजन का उपयोग ऑटोमेटन के निष्पादन पर निष्पक्षता शर्तों को परिभाषित करने के लिए किया जाता है। इन स्थितियों के लिए ऑटोमेटन को अपने निष्पादन के दौरान अपने प्रत्येक कार्य को उचित मोड़ देना जारी रखना पड़ता है। यह विशेष रूप से तब सहायक होता है जब एक प्रणाली घटक का प्रतिरूपण किया जाता है जो कई कार्य करता है। उदाहरण के लिए, एक घटक जो समय-समय पर अपने पर्यावरण को स्थिति की जानकारी देते हुए एक चल रहे एल्गोरिदम में भाग लेता है, उसके दो कार्य होंगे। विभाजन तब भी उपयोगी होता है जब कई ऑटोमेटा बनाए जाते हैं (एक बड़े सिस्टम ऑटोमेटन का उत्पादन करने के लिए) जब यह निर्दिष्ट किया जाता है कि रचना में सभी ऑटोमेटा रचना प्रणाली में कदम उठाना जारी रखते हैं। उदाहरण-चैनल आई/ओ ऑटोमेटन की औपचारिक परिभाषा जैसा कि ऊपर वर्णित है, सी. आई., जे. आई/ओ ऑटोमेटन का एक उदाहरण है जो प्रक्रिया पी. आई. से लेकर प्रक्रिया पी. जे. तक एक दिशात्मक एफ. आई. एफ. ओ. चैनल का प्रतिनिधित्व करता है। मान लीजिए कि m एक द्विआधारी संदेश हैः m bul {0,1}। ऑटोमेटन सी. आई., जे. को औपचारिक रूप से निम्नानुसार परिभाषित किया जा सकता है। हस्ताक्षरः सिग (सी. आई., जे.) निर्दिष्ट करता है कि स्वचालित यंत्र में दो प्रकार की क्रियाएँ होती हैंः (सी. आई., जे.) की एक इनपुट क्रिया सेंड (एम.) आई, जे. के रूप में होती है, जहाँ एम. (सी. आई., जे.) की एक आउटपुट क्रिया रिसीव (एम) आई, जे. के रूप में होती है, जहाँ एम. सहज रूप से, सेंड (m) i, j क्रिया इंगित करती है कि एक संदेश m ने चैनल में प्रवेश किया है जब इसे प्रोसेस Pi द्वारा भेजा जाता है और कार्रवाई रिसीव (m) i, j इंगित करती है कि एक संदेश m ने चैनल छोड़ दिया है जब इसे Pj को संसाधित करने के लिए वितरित किया जाता है। अवस्थाएँः अवस्थाएँ (सी. आई., जे.) तत्वों के सभी परिमित अनुक्रमों का समुच्चय है जो एम. अंतर्ज्ञानी रूप से, राज्य वर्तमान में प्रेषक से प्राप्तकर्ता को भेजे गए संदेशों के अनुक्रम का प्रतिनिधित्व करता है, पी. आई. को संसाधित करता है, पी. जे. को उसी क्रम में संसाधित करता है जिस क्रम में उन्हें भेजा गया था। प्रारंभ (सी. आई., जे.), जो कतार की प्रारंभिक अवस्थाओं का प्रतिनिधित्व करता है, में केवल खाली अनुक्रम होता है। संक्रमण संक्रमण संबंध को एक पूर्व शर्त-प्रभाव शैली में मॉडल किया जा सकता है, जहां सभी संक्रमण जिनमें प्रत्येक विशिष्ट प्रकार की क्रिया शामिल होती है, को कोड के एक टुकड़े में समूहीकृत किया जाता है। इस संहिता में, जिन शर्तों को किसी कार्रवाई की अनुमति देने से पहले पूरा किया जाना चाहिए, उन्हें पूर्व-स्थिति s पर एक विधेय के रूप में औपचारिक रूप दिया जाता है, जो कार्रवाई होने से पहले की स्थिति है। क्रिया के निष्पादन के परिणामस्वरूप राज्य में होने वाले परिवर्तनों को एक सरल कार्यक्रम के रूप में कूटबद्ध किया जाता है। इस कार्यक्रम को एकल संक्रमण के रूप में अविभाज्य रूप से निष्पादित किया जाता है। यदि यह कार्यक्रम राज्य एस पर लागू किया जाता है, तो नए राज्य एस परिणाम देते हैं। सी. आई., जे. के संक्रमणों को इस प्रकार वर्णित किया गया हैः भेजने के लिए (एम) आई, जेः पूर्व शर्तः कोई प्रभाव नहींः प्राप्त करने के लिए (एम) आई, जेः पूर्व शर्तः एम स्थिति में संग्रहीत अनुक्रम में पहला तत्व है (जहां एम ω {1,0}) प्रभावः स्थिति में संग्रहीत अनुक्रम के पहले तत्व को हटा दें सहज रूप से, भेजने की क्रिया को किसी भी समय निष्पादित किया जा सकता है; यह संदेश एम को चे चैनल में संदेशों की कतार के अंत में जोड़ता है। प्राप्त क्रिया कतार के पहले तत्व को हटा देती है और वापस कर देती है। कार्य कार्य (सी. आई., जे.), एक कार्य विभाजन का प्रतिनिधित्व करता है जो एक ही कार्य में प्राप्त होने वाली सभी क्रियाओं को एक साथ समूहित करता है। सहज रूप से, पी. जे. को संसाधित करने के लिए संदेशों को सौंपना एक एकल कार्य माना जाता है। {प्राप्त करें (m) i, j: m bul {0,1}}। निष्पादन और अनुरेखण निष्पादन एक ऑटोमेटन के एक रन में, एक स्ट्रिंग उत्पन्न होती है जो ऑटोमेटन मॉडल के घटक के व्यवहार का वर्णन करती है। "आई/ओ ऑटोमेटन ए का एक निष्पादन टुकड़ा या तो एक परिमित अनुक्रम है, s0, π1, s1, π2,., πr, sr, या एक अनंत अनुक्रम, s0, π1, s1, π2,., πr, sr,., वैकल्पिक अवस्थाओं और ए की क्रियाओं का ऐसा है कि (एसके, πk + 1, एसके + 1) प्रत्येक के लिए ए का एक संक्रमण है। एक परिमित अनुक्रम को एक अवस्था के साथ समाप्त होना चाहिए। एक निष्पादन को एक निष्पादन खंड के रूप में परिभाषित किया जाता है जो प्रारंभिक अवस्था से शुरू होता है। ए के निष्पादन के समूह को निष्पादन (ए) द्वारा दर्शाया जाता है। आई/ओ ऑटोमेटन ए में एक पहुँच योग्य अवस्था ए के परिमित निष्पादन की अंतिम स्थिति है। मान लीजिए कि α अवस्था sf के साथ समाप्त होने वाला A का एक सीमित निष्पादन टुकड़ा है। आगे मान लीजिए कि α 'A का कोई भी निष्पादन टुकड़ा है जो α की अंतिम स्थिति sf से शुरू होता है। इस मामले में, α और α 'को संयोजित करके और α की अंतिम स्थिति, sf की डुप्लिकेट घटना को समाप्त करके उत्पन्न अनुक्रम को α. α' द्वारा दर्शाया जाता है। यह अनुक्रम आई/ओ ऑटोमेटन ए का एक निष्पादन टुकड़ा भी है। ट्रेस आई/ओ ऑटोमेटन ए का एक निशान बाहरी क्रियाओं का क्रम है जो ए के कुछ निष्पादन α में होता है। ए के सभी निशानों के समूह को निशान (ए) के रूप में दर्शाया जाता है। उदाहरण-तीन निष्पादन निष्पादन ए, बी और सी स्वचालित सी, जे के तीन निष्पादन हैं जिनका वर्णन चैनल आई/ओ स्वचालित की औपचारिक परिभाषा में किया गया है (जहाँ संदेश m bul {0,1})। इस उदाहरण में, राज्यों को कोष्ठक में कतार में संदेशों के अनुक्रम को रखकर इंगित किया जाता है; खाली अनुक्रम को λ द्वारा दर्शाया जाता है। (a) [λ], सेंड (1) i, j, [1], रिसीव (1) i, j, [λ], सेंड (0) i, j, [0], रिसीव (0) i, j, [λ] (b) [λ], सेंड (1) i, j, [λ], रिसीव (1) i, j, [λ], सेंड (0) i, j, [0] (c) [λ], सेंड (1) i, j, [1], सेंड (1) i, j, [11], सेंड (1) i, j, [11], सेंड (0) i, j, [110]. ऑटोमेटा कम्पोजिशन ऑपरेशन पर ऑपरेशंस कम्पोजिशन करना संभव है। इस मामले में, प्रत्येक घटक ऑटोमेटा में एक ही नाम वाले कार्यों को एक साथ पहचाना जाता है। इसलिए, जब एक घटक स्वचालित एक कदम उठाता है जिसमें एक क्रिया π शामिल होती है, तो अन्य सभी घटक स्वचालित भी अपने हस्ताक्षर में π के साथ उस कार्रवाई को करते हैं। निम्नलिखित में स्वचालित ए और ए 'की संरचना की शर्तों को रेखांकित किया गया है जिन्हें अनुमति दी जानी चाहिएः ए की आंतरिक क्रियाएं ए' की क्रियाओं से अलग होनी चाहिए। यह ए 'में एक चरण के प्रदर्शन को रोकता है जब ए की आंतरिक क्रियाएँ-ए' की क्रियाओं के समान नाम के साथ-की जाती हैं। A और A 'की आउटपुट क्रियाएँ अलग-अलग होनी चाहिए। यह शर्त यह सुनिश्चित करती है कि केवल एक घटक स्वचालित उत्पादन क्रिया के प्रदर्शन को नियंत्रित करता है। यदि संरचना का निर्माण स्वचालित के एक गणना योग्य अनंत संग्रह से किया जाता है, तो एक अतिरिक्त बाधा होती हैः प्रत्येक क्रिया को केवल सीमित रूप से कई घटक स्वचालित की क्रिया होने की आवश्यकता होती है। स्वचालित की अनंत संरचना तार्किक प्रणालियों के प्रतिरूपण की अनुमति देती है जिन्हें कई तार्किक घटकों से बनाया जा सकता है। तार्किक प्रणाली को अक्सर एक भौतिक प्रणाली पर लागू किया जाता है जिसमें कम घटक होते हैं। उदाहरण-रचना चित्र 4 में दो प्रक्रियाओं, पी. आई. और पी. जे. और एक एफ. आई. एफ. ओ. संदेश चैनल सी. आई., जे. की संरचना को दर्शाया गया है, जो एक ऑटोमेटन की आउटपुट क्रियाओं को अन्य ऑटोमेटा की समान रूप से नामित इनपुट क्रियाओं के साथ मिलान करता है। इस प्रकार, प्रक्रिया पी. आई. द्वारा किए गए एक सेंड (एम) आई, जे आउटपुट का मिलान किया जाता है और चैनल सी. आई., जे. द्वारा किए गए सेंड (एम) आई, जे इनपुट के साथ किया जाता है। प्रोसेस पाई संदेश m भेजता है, जहाँ m bul {1,0} चैनल Ci, j के माध्यम से प्रोसेस Pj को जाता है। प्रोसेस पीजे पाई से प्राप्त संदेश एम में अपनी आंतरिक कार्रवाई रिवर्स का उपयोग करके बिट को उलट देता है-चित्र में नहीं दिखाया गया है-और संदेश को सिस्टम के अन्य हिस्सों में आगे बढ़ाता है। ऑपरेशन को छिपाना आई/ओ ऑटोमेटन की आउटपुट क्रियाओं को "उन्हें आंतरिक क्रियाओं के रूप में पुनर्वर्गीकृत करने" के माध्यम से छिपाना संभव है। इससे उन्हें प्रणाली के अन्य हिस्सों के साथ संचार से बाहर रखने का प्रभाव पड़ता है। औपचारिक रूप से, हस्ताक्षरों के लिए छिपाने की कार्रवाई का वर्णन इस प्रकार किया गया हैः मान लीजिए कि एस एक हस्ताक्षर है और φ बाहर (एस)। हाइड (एस) नया हस्ताक्षर एस 'है, जहाँ (एस') = इन (एस) आउट (एस ') = आउट (एस)-φ इंट (एस') = इंट (एस) φ इसलिए, "यदि ए एक ऑटोमेटन है और φ आउट (ए) है, तो हाइड (ए) ए से प्राप्त ऑटोमेटन ए 'है जो सिग (ए) को सिग (ए) से बदलकर सिग (ए) = हाइड (ए) से प्राप्त होता है।" निष्पक्षता याद रखें कि एक कार्य विभाजन को आई/ओ ऑटोमेटन के स्थानीय रूप से नियंत्रित कार्यों पर एक समतुल्यता संबंध के रूप में परिभाषित किया गया है, जिसमें अधिक से अधिक गिनती में कई समतुल्यता वर्ग शामिल हैं। इस सेटिंग में, निष्पक्षता को प्रत्येक कार्य को लगातार एक कार्य करने का अवसर प्रदान करने के रूप में परिभाषित किया जा सकता है। आई/ओ ऑटोमेटन ए में, सी को कार्यों (ए) के एक वर्ग का प्रतिनिधित्व करने दें। औपचारिक रूप से, ए के एक निष्पादन खंड α को उचित माना जाता है यदि प्रत्येक वर्ग सी के लिए नीचे दिए गए मानदंड हैंः "यदि α परिमित है, तो सी को α की अंतिम स्थिति में सक्षम नहीं किया जाता है।" "यदि α अनंत है, तो α में या तो C से अनंत रूप से कई घटनाएँ होती हैं या उन अवस्थाओं की अनंत रूप से कई घटनाएं होती हैं जिनमें C सक्षम नहीं है।" एक घटना को "एक अनुक्रम में एक क्रिया की घटना, उदाहरण के लिए, एक निष्पादन या एक निशान" के रूप में परिभाषित किया गया है। निष्पक्षता की परिभाषा के आधार पर, "असीम रूप से अक्सर", प्रत्येक कार्य (या तुल्यता वर्ग सी) को एक कार्य करने का मौका मिलता है। जब किसी कार्य (या समतुल्यता वर्ग) सी को कोई कार्य करने का मौका मिलता है, तो दो मामले संभव होते हैंः सी में एक कार्य वर्तमान स्थिति में सक्षम होता है और किया जा सकता है, या सी में कोई भी कार्य वर्तमान स्थिति में सक्षम नहीं होता है और इसलिए, किया नहीं जा सकता है। इस प्रकार, अंतिम अवस्था एस. एफ. के साथ एक सीमित निष्पक्ष निष्पादन को एक निष्पादन के रूप में परिभाषित किया जा सकता है जहां ऑटोमेटन लगातार सभी कार्यों को राउंड-रॉबिन फैशन में मोड़ देता है, लेकिन कोई भी क्रिया निष्पादित नहीं की जाती है क्योंकि एस. एफ. में कोई भी सक्षम नहीं है। आई/ओ ऑटोमेटन ए के निष्पक्ष निष्पादन के समूह को फेयरएक्स (ए) द्वारा दर्शाया जाता है। मान लीजिए कि β ए के उचित निष्पादन का निशान है। तब β ए का एक उचित निशान है। ए के सेट फेयर ट्रेस को फेयरट्रेस (ए) द्वारा दर्शाया जाता है। निष्पादन उदाहरण में, निष्पादन (ए) उचित है, क्योंकि इसकी अंतिम स्थिति में कोई प्राप्त कार्रवाई सक्षम नहीं है। निष्पादन (बी) सीमित है, फिर भी एक प्राप्त क्रिया अपनी अंतिम स्थिति में सक्षम है। इसलिए निष्पादन (बी) उचित नहीं है। निष्पादन (सी) अनंत है, जिसमें प्राप्त घटनाएँ शामिल नहीं हैं, और पहले चरण के बाद सभी बिंदुओं पर, प्राप्त क्रियाएँ सक्षम हैं। इसलिए, यह एक उचित निष्पादन नहीं है। निष्पक्षता की परिभाषा में एक महत्वपूर्ण गुण हैः "एक रचना का निष्पक्ष निष्पादन घटकों के निष्पक्ष निष्पादन की संरचना हैः" अर्थात, निष्पक्ष (Πi AI) = Πi निष्पक्ष (AI)। गुण और प्रमाण विधियाँ I/O ऑटोमेटा अतुल्यकालिक प्रणालियों का सटीक विवरण प्रदान करते हैं। इनका उपयोग "सिस्टम क्या कर सकते हैं" के बारे में "सटीक दावों" को औपचारिक रूप देने और साबित करने के लिए भी किया जाता है। इस खंड में कई महत्वपूर्ण प्रकार के गुणों का वर्णन किया गया है। इनके साथ-साथ आगे के गुणों और प्रमाण विधियों को वितरित एल्गोरिदम में समझाया गया है। इनपुट सक्षम करने वाले गुण इनपुट सक्षम करने वाले गुण में कहा गया है कि ऑटोमेटन इनपुट कार्यों को होने से रोक नहीं सकता है। इस गुण के होने के दो महत्वपूर्ण फायदे हैंः चूंकि मॉडल को मनमाने इनपुट से निपटने के लिए डिज़ाइन किया गया है, अप्रत्याशित इनपुट को संभालने में विफलता के कारण सिस्टम त्रुटियों का एक प्रमुख स्रोत समाप्त हो जाता है। इनपुट-सक्षम करने वाला गुण "बाहरी क्रियाओं के अनुक्रमों के आधार पर एक स्वचालित के लिए बाहरी व्यवहार की सरल धारणाओं" का उपयोग करता है। मॉडल में कुछ प्रमेयों के प्रमाण इस गुण की धारणा के बिना विफल हो सकते हैं। ट्रेस गुण एक आई/ओ ऑटोमेटन के आंतरिक कार्यों के रूप में एक उपयोगकर्ता के लिए अदृश्य हैं; आई/ओ ऑटोमेटन एक ब्लैक बॉक्स प्रतीत होता है और उपयोगकर्ता केवल "ऑटोमेटन के निष्पादन (या निष्पक्ष निष्पादन) के निशान" देखता है। आई/ओ ऑटोमेटा के कुछ गुणों और उनके प्रमाणों को आम तौर पर "उनके निशान या उचित निशान के गुणों" के रूप में औपचारिक रूप दिया जाता है। मान लीजिए कि पी एक अनुरेखण गुण है; पी में निम्नलिखित घटक हैंः सिग (पी), जो एक हस्ताक्षर का प्रतिनिधित्व करता है जिसमें कोई आंतरिक क्रिया निशान (पी) नहीं है, जो "कृत्यों में क्रियाओं के अनुक्रम (सिग (पी))" के एक समूह से मेल खाता है। यह समुच्चय अनंत हो सकता है। ट्रेस गुण एक बाहरी हस्ताक्षर के साथ-साथ उस इंटरफेस पर देखे गए अनुक्रमों के एक सेट (या एक गुण) का वर्णन करता है। कभी-कभी कार्य (सिग (पी)) को एक आशुलिपि संकेतन कार्य (पी) द्वारा दर्शाया जाता है। जब यह उल्लेख किया जाता है कि आई/ओ ऑटोमेटन ए एक ट्रेस गुण पी को संतुष्ट करता है, तो (कम से कम) दो अलग-अलग अर्थ हो सकते हैंः "एक्सटिग (ए) = सिग (पी) और ट्रेस (ए) ट्रेस (पी)" एक्सटिग (ए) = सिग (पी) और फेयरट्रेस (ए) ट्रेस (पी) "सहज रूप से, इसका मतलब है कि जब ए एक बाहरी व्यवहार उत्पन्न करता है तो वह गुण पी द्वारा अनुमत है। हालाँकि, ए के लिए वास्तव में पी के प्रत्येक ट्रेस का प्रतिनिधित्व करना आवश्यक नहीं है। चूंकि ए इनपुट-सक्षम है, तो इनपुट क्रियाओं के प्रत्येक संभावित अनुक्रम के लिए, फेयरट्रेस (ए) (और इसलिए ट्रेस (ए) में ए द्वारा प्रतिक्रिया शामिल है। यदि फेयरट्रेस (ए) ट्रेस (पी) धारण करता है, तो गुण पी में सभी उत्पन्न अनुक्रम होने चाहिए। सुरक्षा गुण स्वाभाविक रूप से, एक सुरक्षा गुण इस तथ्य का प्रतिनिधित्व करता है कि कुछ भी "बुरा" नहीं होता है। अधिक औपचारिक रूप से, मान लीजिए कि पी एक ट्रेस प्रॉपर्टी है। पी एक निशान सुरक्षा संपत्ति, या सुरक्षा संपत्ति है, यदि निम्नलिखित मानदंड निशान (पी) के लिए हैं। निशान (पी) खाली नहीं हैः किसी भी घटना की घटना से पहले कुछ बुरा नहीं हो सकता है; इसलिए, निशान (पी) पर गैर-खाली होना एक उचित शर्त है। ट्रेस (पी) "उपसर्ग-बंद" हैः मान लीजिए कि β 'ट्रेस (पी) और β' β के एक परिमित उपसर्ग का प्रतिनिधित्व करते हैं। विस्तार से, मान लीजिए कि एक निशान है जिसमें कुछ भी बुरा नहीं होता है। इसलिए, उस निशान के किसी भी उपसर्ग में कुछ भी बुरा नहीं होता है। इस प्रकार, उपसर्ग-बंद होना निशान (पी) पर एक उचित शर्त है। ट्रेस (पी) "सीमा-बंद" हैः मान लीजिए β1, β2,। .. .. ट्रेस (पी) में परिमित अनुक्रमों के एक अनंत अनुक्रम का प्रतिनिधित्व करते हैं। इसके अलावा, मान लीजिए कि प्रत्येक i के लिए, βi, βi + 1 का उपसर्ग है। इस मामले में, अद्वितीय अनुक्रम β, जो कि "क्रमिक विस्तार क्रम के तहत βi की सीमा" भी निशान (P) में मौजूद है। इसलिए, यदि किसी निशान में कुछ बुरा होता है, तो यह निशान में कुछ विशिष्ट घटना का परिणाम होगा। इस मामले में सीमा बंद होना इस प्रकार निशान (पी) पर एक उचित शर्त है। जीवंतता गुण अनौपचारिक रूप से, एक जीवंतता गुण की व्याख्या कुछ "अच्छा" के रूप में की जा सकती है जो अंततः होता है। इसलिए, इस बात की परवाह किए बिना कि समय में एक निश्चित बिंदु पर क्या हुआ है, भविष्य में किसी समय कुछ अच्छा हो सकता है। अधिक औपचारिक रूप से, मान लीजिए कि पी एक ट्रेस प्रॉपर्टी है। पी एक निशान जीवंतता गुण है, या एक जीवंतता गुण है, "यदि कृत्यों (पी) पर प्रत्येक परिमित अनुक्रम का निशान (पी) में कुछ विस्तार है।" टाइमड आई/ओ ऑटोमेटनः प्रोबेबिलिस्टिक आई/ओ ऑटोमेटनः सामान्य रूप से सुरक्षा गुणों और जीवंतता गुणों की चर्चा के लिए, सुरक्षा और जीवंतता गुण देखें। यह भी देखें कि अनुक्रमिक प्रक्रियाओं का संचार अभिनेता मॉडल संदर्भ वितरित कंप्यूटिंग