كائنات اللقطة المشتركة

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 13 صور
الموسوعة الحرة

في الحوسبة الموزعة ، يُعدّ كائن اللقطة المشتركة نوعًا من هياكل البيانات التي تُشارك بين عدة سلاسل عمليات أو عمليات. في العديد من المهام، من المهم وجود هيكل بيانات يوفر رؤية متسقة لحالة الذاكرة. عمليًا، يتضح أنه من غير الممكن الحصول على حالة متسقة للذاكرة بمجرد الوصول إلى سجل مشترك تلو الآخر، لأن القيم المخزنة في السجلات الفردية قابلة للتغيير في أي وقت أثناء هذه العملية. لحل هذه المشكلة، تخزن كائنات اللقطة متجهًا من n عنصرًا وتوفر العمليتين الذريتين التاليتين : تُغيّر الدالة update(i,v) القيمة في العنصر i إلى v ، وتُعيد الدالة scan() القيم المخزنة في جميع العناصر n . [ 1 ] [ 2 ] يمكن إنشاء كائنات اللقطة باستخدام سجلات مشتركة ذرية أحادية الكاتب ومتعددة القارئ .

بشكل عام، يُفرّق بين كائنات اللقطة أحادية الكاتب ومتعددة القراء (swmr) وكائنات اللقطة متعددة الكتاب ومتعددة القراء (mwmr). في كائن اللقطة swmr، يتطابق عدد المكونات مع عدد العمليات، ويُسمح لعملية واحدة فقط (P i) بالكتابة إلى موقع الذاكرة i، بينما يُسمح لجميع العمليات الأخرى بقراءة الذاكرة. في المقابل، في كائن اللقطة mwmr، يُسمح لجميع العمليات بالكتابة إلى جميع مواقع الذاكرة وقراءتها أيضًا.

عام

تُقسّم الذاكرة المشتركة إلى أجزاء متعددة، يحتوي كل جزء منها على قيمة بيانات واحدة. في حالة الكتابة الفردية والقراءة المتعددة، يُخصص لكل عملية ( P <sub>i </sub>) موقع ذاكرة ( i) ، ويُسمح لهذه العملية فقط بالكتابة إلى هذا الموقع. مع ذلك، يُسمح لكل عملية بقراءة أي موقع في الذاكرة. أما في حالة الكتابة المتعددة والقراءة المتعددة، فيتغير هذا القيد، ويُسمح لأي عملية بتغيير أي موقع في الذاكرة .∈{\displaystyle \in }في نظام ذي n عملية، يمكن للدالة {1,..., n } تنفيذ عمليتين على كائن اللقطة: scan() و update(i,v) . لا تأخذ عملية scan أي وسيطات، وتعيد عرضًا متسقًا للذاكرة. أما عملية update(i,v) فتُحدِّث الذاكرة عند الموضع i بالقيمة v .

يُعتبر كلا النوعين من العمليات ذريين، حيث يتم تنفيذهما بشكل ذري بين استدعاء العملية وعودة البيانات من الذاكرة. وبشكل أعم، في متجه البياناتد¯{\displaystyle {\overline {d}}}يتوافق كل إدخال d k مع وسيط عملية التحديث الخطي الأخيرة ، والتي تقوم بتحديث الجزء k من الذاكرة. [ 1 ]

للاستفادة الكاملة من كائنات اللقطات المشتركة، من حيث تبسيط عمليات التحقق والإنشاء، أُضيف قيدان آخران على إنشاء كائنات اللقطات. [ 1 ] القيد الأول هو قيد معماري، ويعني أن أي كائن لقطة يُنشأ فقط باستخدام سجلات أحادية الكتابة ومتعددة القراءة كعنصر أساسي. هذا ممكن في لقطات أحادية الكتابة ومتعددة القراءة. أما في لقطات متعددة الكتابة ومتعددة القراءة، فيمكن استخدام سجلات متعددة القراءة والكتابة ، والتي بدورها يمكن إنشاؤها من سجلات أحادية الكتابة ومتعددة القراءة. [ 1 ] [ 3 ] [ 4 ]

في الحوسبة الموزعة، يُبنى النظام على أساس هدف واحد: ضمان تقدم النظام ككل أثناء التنفيذ. لذا، يجب ألا يؤدي سلوك أي عملية إلى توقف النظام بأكمله ( عدم وجود أقفال ). ويُعدّ عدم وجود انتظار ، وهو شكل أقوى من هذه الخاصية ، يعني أنه لا يمكن لأي عملية منع عملية أخرى من إنهاء عملها. وبشكل أعم، يعني هذا أن كل عملية يجب أن تنتهي بعد عدد محدود من الخطوات بغض النظر عن سلوك العمليات الأخرى. تضمن خوارزمية اللقطات الأساسية تقدم النظام ككل، ولكنها لا تعتمد على الأقفال. ومن السهل توسيع هذه الخوارزمية لتصبح خالية من الانتظار. تتمتع خوارزمية أفيك وآخرون [ 1 ]، المعروضة في قسم التنفيذ، بهذه الخاصية.

تطبيق

توجد عدة طرق لتنفيذ كائنات اللقطات المشتركة. توفر الخوارزمية الأولى المعروضة تنفيذًا أساسيًا لكائنات اللقطات، إلا أن هذا التنفيذ يوفر فقط خاصية عدم الحاجة إلى القفل . أما التنفيذ الثاني المعروض، والذي اقترحه أفيك وآخرون [ 1 ]، فيتميز بخاصية أقوى تُسمى عدم الحاجة إلى الانتظار . ويقدم فيش [ 2 ] نظرة عامة على التنفيذات الأخرى.

خوارزمية التقاط الصور الأساسية لـ swmr

تعتمد الفكرة الأساسية لهذه الخوارزمية على أن كل عملية تُنفذ scan()العمليات تقرأ جميع قيم الذاكرة مرتين. إذا قرأت الخوارزمية نفس محتوى الذاكرة مرتين، ولم تُغير أي عملية أخرى أي قيمة بينهما، فيمكنها إرجاع النتيجة. أما العملية التي تُنفذ update(i,v)عملية ما، فتقوم ببساطة بتحديث قيمتها في الذاكرة.

دالة scan() بينما صحيح a[1..n] := collect; b[1..n] := collect; إذا لم يتغير الموقع i بين قراءتيه خلال عمليتي التجميع (∀i∈{1, .., n}) ، إرجاع b؛ // تم جمع البيانات المزدوجة بنجاح نهاية الحلقة
دالة التحديث(i, v) M[i] := v; نهاية
الشكل 1: تقوم إحدى العمليات بتحديث الذاكرة باستمرار، أثناء عملية التجميع المزدوجة للعملية الأخرى. وبالتالي، لا يمكن لعملية المسح أن تنتهي أبدًا.

تُقدّم هذه الخوارزمية تطبيقًا أساسيًا جدًا لكائنات اللقطات. وهي تضمن استمرار عمل النظام، مع إمكانية توقف بعض الخيوط بسبب سلوك العمليات الفردية. تستطيع العملية P1 منع العملية P2 من إنهاء عملية ماscan() عن طريق تغيير قيمتها باستمرار بين عمليتي جمع الذاكرة. وبالتالي، فإن الخوارزمية خالية من الأقفال ، ولكنها ليست خالية من الانتظار . ولتعزيز هذه الخاصية، لا يُسمح لأي عملية بالتوقف بسبب سلوك العمليات الأخرى. يوضح الشكل 1 المشكلة. فبينما تحاول P1 تنفيذ scan()العملية، تُقاطع عملية ثانية P2 عملية "الجمع المزدوج" باستمرار. وبالتالي، يتعين على عملية المسح إعادة تشغيل العملية دائمًا ، ولا يمكن أن تتوقف أو تتوقف.

تطبيق قارئ متعدد بكاتب واحد بواسطة أفيك وآخرون.

تعتمد الفكرة الأساسية لخوارزمية لقطة swmr التي طورها أفيك وآخرون على قدرة كل عملية على اكتشاف ما إذا كانت عملية أخرى قد غيرت موقعها في الذاكرة، وأن العمليات تتعاون فيما بينها. وللكشف عن تغيير قيمة موقعها، يُلحق عداد بكل سجل، وتقوم كل عملية بزيادة هذا العداد مع كل تحديث. أما الفكرة الثانية، فهي أن كل عملية تُحدّث موقعها في الذاكرة تُجري scan()عملية أخرى، وتُقدّم "رؤيتها للذاكرة" في سجلها إلى العمليات الأخرى. ويمكن لعملية المسح استعارة هذه scanالنتيجة وإعادتها.

يعتمد على ذاكرة غير محدودة

باستخدام هذه الفكرة، يمكن بناء خوارزمية لا تتطلب انتظارًا وتستخدم سجلات ذات حجم غير محدود. يمكن لعملية تُجري عملية تحديث أن تساعد عملية أخرى في إكمال عملية المسح. الفكرة الأساسية هي أنه إذا رأت عملية ما عملية أخرى تُحدِّث موقعًا في الذاكرة مرتين، فلا بد أن تلك العملية قد نفَّذت عملية تحديث كاملة ومتسلسلة بينهما. لتنفيذ ذلك، تُجري كل عملية تحديث أولًا مسحًا للذاكرة، ثم تكتب قيمة اللقطة بشكل ذري مع القيمة الجديدة v ورقم تسلسلي. إذا كانت عملية ما تُجري مسحًا للذاكرة واكتشفت أن عملية أخرى قد حدَّثت جزءًا من الذاكرة مرتين، فيمكنها "استعارة" المسح "المُضمَّن" للتحديث لإكمال عملية المسح . [ 1 ]

دالة scan() // تُعيد عرضًا متسقًا للذاكرة for j = 1 to n do moved[j] := 0 end while true do a[1..n] := collect; // يجمع ثلاثيات (البيانات، التسلسل، العرض) b[1..n] := collect; // يجمع ثلاثيات (البيانات، التسلسل، العرض) إذا كان (∀j∈{1, ..., n}) (a[j].seq = b[j].seq) فإن return (b[1].data, ..., b[n].data) // لم يقم أي عملية بتغيير الذاكرة. وإلا، فلكل j من 1 إلى n ، إذا كان a[j].seq ≠ b[j].seq فإن // تم نقل العملية. إذا تم نقل moved[j] = 1 فإن // تم نقل العملية مسبقًا. return b[j].view; وإلا moved[j] := moved[j] + 1; end end end function
إجراء التحديث ( i ، v ) // يُحدِّث السجلات بقيم البيانات، ويُحدِّث رقم التسلسل، والمسح المضمن s[1..n] := scan; // مسح ضوئي مضمن r i := (v, r i .seq = r i .seq + 1, s[1..n]); end procedure
الشكل 2: مثال على ترتيب التخطيط الخطي لكائن لقطة متعدد القراءات ذي كاتب واحد. يمكن لعملية المسح الأولى (scan()) إجراء عملية جمع مزدوجة بنجاح، بينما تتم مقاطعة عملية الجمع المزدوجة لعملية المسح الثانية مرتين بواسطة العملية الثانية. وبالتالي، تستعير العملية عملية مسح مضمنة.

يتكون كل سجل من حقل لقيمة البيانات، ورقم تسلسلي، وحقل لنتيجة آخر مسح مضمن، تم جمعه قبل آخر تحديث. في كل عملية مسح، يمكن للعملية P i تحديد ما إذا كانت عملية أخرى قد غيرت ذاكرتها باستخدام الرقم التسلسلي. إذا لم يحدث أي تغيير في الذاكرة أثناء عملية الجمع المزدوجة، يمكن لـ P i إرجاع نتيجة المسح الثاني. بمجرد أن تلاحظ العملية أن عملية أخرى قد حدثت الذاكرة في الفترة الفاصلة، فإنها تحفظ هذه المعلومات في الحقل "moved". إذا غيرت عملية P j ذاكرتها مرتين أثناء تنفيذ دالة scan()، يمكن لعملية المسح P i إرجاع المسح المضمن للعملية المُحدِّثة، والذي حفظته في سجلها الخاص أثناء عملية التحديث.

يمكن تبسيط هذه العمليات عن طريق تبسيط كل عملية تحديث () عند كتابتها إلى السجل. أما عملية المسح فهي أكثر تعقيدًا في تبسيطها. إذا نجحت عملية التجميع المزدوجة لعملية المسح، فيمكن تبسيط عملية المسح في نهاية عملية المسح الثانية. في الحالة الأخرى - إذا قام أحد العمليات بتحديث سجله مرتين - فيمكن تبسيط العملية عند قيام عملية التحديث بتجميع المسح المضمن قبل كتابة قيمته إلى السجل. [ 1 ]

استنادًا إلى الذاكرة المحدودة

من عيوب الخوارزمية المعروضة أنها تعتمد على ذاكرة غير محدودة، حيث سيزداد رقم التسلسل باستمرار. وللتغلب على هذا القيد، من الضروري إيجاد طريقة مختلفة للكشف عما إذا كان أحد العمليات قد غيّر موقعه في الذاكرة مرتين خلال عملية واحدة. كل زوج من العمليات⟨Pأنا،Pج⟩{\displaystyle \langle P_{i},P_{j}\rangle }يتواصل النظام باستخدام سجلين أحاديي الكتابة والقراءة (swsr)، يحتوي كل منهما على بتتين ذريتين. قبل أن تبدأ العملية بتنفيذ عملية "الجمع المزدوج"، تنسخ قيمة العملية الشريكة لها إلى سجلها الخاص. إذا لاحظت عملية المسح الضوئي P i بعد تنفيذ عملية "الجمع المزدوج" أن قيمة العملية الشريكة P j قد تغيرت، فهذا يشير إلى أن العملية قد أجرت عملية تحديث على الذاكرة. [ 1 ]

دالة scan() // تُعيد عرضًا متسقًا للذاكرة for j=1 to n do moved[j] := 0 end while true do for j=1 to n do q i,j := r j .p j,i end a[1..n] := collect; // يجمع ثلاثيات (البيانات، متجه البت، التبديل، العرض) b[1..n] := collect; // يجمع ثلاثيات (البيانات، متجه البت، التبديل، العرض) إذا كان (∀j∈{1, ...,n}) (a[j].p j,i = b[j].p j,i = q i,j ) و a[j].toggle = b[j].toggle ثم أرجع (b[1].data, ..., b[n].data) // لم يقم أي معالج بتغيير الذاكرة وإلا لـ j=1 إلى n do إذا كان (a[j].p j,i ≠ q i,j ) أو (b[j].p j,i ≠ q i,j ) أو (a[j].toggle ≠ b[j].toggle) ثم // قام المعالج j بتنفيذ تحديث إذا تم نقله[j] = 2 ثم // تم نقل المعالج مسبقًا أرجع b[j].view; وإلا تم نقله[j] := moved[j] + 1; نهاية نهاية نهاية الدالة
الإجراء update( i , v ) // يُحدِّث السجلات بقيمة البيانات، وحالة الكتابة لجميع السجلات، ويعكس بت التبديل، والمسح المضمن. من أجل j = 1 إلى n، نفِّذ f[j] := ¬q j,i end s[1..n] := scan; // المسح المضمن r i := (v, f[1..n], ¬r i .toggle, s[1..n]); end procedure

يُستبدل رقم التسلسل غير المحدود ببتّي مصافحة لكل زوج من العمليات. تعتمد بتّات المصافحة هذه على سجلات swsr، ويمكن تمثيلها بمصفوفة M ، حيث يُسمح للعملية P i بالكتابة في الصف i وقراءة بتّات المصافحة في العمود i . قبل أن تُجري عملية المسح عملية التجميع المزدوج، تجمع جميع بتّات المصافحة من جميع السجلات بقراءة عمودها. بعد ذلك، يُمكنها تحديد ما إذا كانت إحدى العمليات قد غيّرت قيمتها أثناء عملية التجميع المزدوج أم لا. لذلك، ما على العملية سوى مقارنة العمود مرة أخرى مع بتّات المصافحة المقروءة في البداية. إذا كتبت عملية واحدة فقط P j مرتين، فمن المحتمل ألا تتغير بتّات المصافحة أثناء عملية التجميع الخاصة بـ P i . لذا، من الضروري إضافة بتّ آخر يُسمى "بتّ التبديل"، يتغير هذا البتّ في كل عملية كتابة. هذا يُتيح التمييز بين عمليتي كتابة متتاليتين، حتى لو لم تُحدّث أي عملية أخرى سجلها. يسمح هذا النهج باستبدال أرقام التسلسل غير المحدودة ببتات المصافحة، دون تغيير أي شيء آخر في إجراء المسح.

بينما تستخدم عملية المسح الضوئي Pi بتة المصافحة لتحديد إمكانية استخدام عملية التجميع المزدوج، قد تُجري عمليات أخرى عمليات تحديث. كخطوة أولى، تقرأ هذه العمليات بتات المصافحة المُقدمة من العمليات الأخرى، وتُنشئ مُكملاتها. بعد ذلك، تُنشئ هذه العمليات المسح الضوئي المُضمن مرة أخرى، وتحفظ قيمة البيانات المُحدثة، وبتات المصافحة المُجمعة والمُكملة، وبتة التبديل المُكملة، والمسح الضوئي المُضمن في السجل.

بما أن بتات المصافحة تحل محل أرقام التسلسل بشكل مكافئ، فإن عملية التخطيط الخطي هي نفسها كما في حالة الذاكرة غير المحدودة.

تطبيق متعدد الكتابة والقراءة بواسطة أفيك وآخرون.

يفترض بناء كائن لقطة متعدد الكتابة والقراءة السماح لعدد n من العمليات بالكتابة إلى أي موقع في الذاكرة، التي تتكون من m من المسجلات. لذا، لم يعد هناك ارتباط بين مُعرّف العملية وموقع الذاكرة. وبالتالي، لم يعد من الممكن ربط بتات المصافحة أو المسح المضمن بحقول البيانات. ومن ثم، لا يمكن تخزين بتات المصافحة وذاكرة البيانات والمسح المضمن في نفس المسجل، ولم تعد الكتابة إلى الذاكرة عملية ذرية.

الشكل 3: يوضح مثالاً على التخطيط الخطي لكائن لقطة متعدد الكتابة ومتعدد القراءة

لذا، update()يتعين على العملية تحديث ثلاثة سجلات مختلفة بشكل مستقل. أولًا، عليها حفظ بتات المصافحة التي تقرأها، ثم إجراء المسح المضمن، وأخيرًا حفظ قيمتها في موقع الذاكرة المحدد. تبدو كل عملية كتابة مستقلة وكأنها تتم بشكل ذري، لكنها في الواقع ليست كذلك مجتمعة. update()يؤدي الإجراء الجديد إلى بعض التغييرات في scan()الوظيفة. لم يعد كافيًا قراءة بتات المصافحة وجمع محتوى الذاكرة مرتين. للكشف عن updateعملية قيد التشغيل، يجب على العملية جمع بتات المصافحة مرة ثانية، بعد جمع محتوى الذاكرة.

في حال فشل عملية التجميع المزدوج، يصبح من الضروري أن يرى أحد العمليات عملية أخرى تتحرك ثلاث مرات قبل استعارة المسح المضمن. يوضح الشكل 3 هذه المشكلة. تفشل عملية التجميع المزدوج الأولى لأن عملية updateبدأت قبل انتهاء عملية المسح من كتابة الذاكرة أثناء عملية التجميع المزدوج الأولى. مع ذلك، يتم تنفيذ المسح المضمن لهذه الكتابة وحفظه قبل أن تبدأ العملية P1 بمسح الذاكرة ، وبالتالي لا توجد نقطة خطية صالحة. تفشل عملية التجميع المزدوج الثانية لأن العملية P2 تبدأ عملية كتابة ثانية وتُحدّث بتات المصافحة الخاصة بها. في سيناريو swmr، سنستعير المسح المضمن ونعيده. أما في سيناريو mwmr، فهذا غير ممكن لأن المسح المضمن من العملية الثانية writeلم يتم خطيته بعد ضمن فترة المسح (بداية ونهاية العملية). لذا، يجب أن ترى العملية تغييرًا ثالثًا من العملية الأخرى للتأكد تمامًا من أن مسحًا مضمنًا واحدًا على الأقل قد تم خطيته خلال فترة المسح. بعد التغيير الثالث بواسطة عملية واحدة، يمكن لعملية المسح الضوئي استعارة قيمة الذاكرة القديمة دون انتهاك معيار الترتيب الخطي.

تعقيد

يتطلب التنفيذ الأساسي المقدم لكائنات اللقطات المشتركة من قبل أفيك وآخرونيا(ن2){\displaystyle O(n^{2})}عمليات الذاكرة. [ 1 ] هناك تطبيق آخر من أندرسون ، تم تطويره بشكل مستقل، ويحتاج إلى عدد هائل من العمليات.يا(2ن){\displaystyle O(2^{n})}[ 5 ] توجد أيضًا تطبيقات عشوائية لكائنات اللقطات تعتمد على سجلات swmr باستخداميا(نسجل2⁡ن){\displaystyle O(n\log ^{2}n)}العمليات. [ 6 ] يتطلب تطبيق آخر من قبل إسرائيلي وشيرازي، باستخدام ذاكرة غير محدودةيا(ن3/2سجل2⁡ن){\displaystyle O(n^{3/2}\log ^{2}n)}العمليات على الذاكرة. [ 7 ] [ 8 ] يُظهر إسرائيلي وآخرون في عمل مختلف الحد الأدنى للعمليات منخفضة المستوى لأي عملية تحديث. الحد الأدنى هوΩ(مين{w،ر}){\displaystyle \Omega (\min\{w,r\})}حيث يمثل w عدد المُحدِّثين و r عدد الماسحات الضوئية. يقدم عطية وراشمان خوارزمية لقطة حتمية تعتمد على سجلات swmr، والتي تستخدميا(نسجل⁡ن){\displaystyle O(n\log n)}[ 8 ] بتطبيق طريقة عامة من قِبل إسرائيلي وشاهام وشيرازي [ 9 ]، يمكن تحسين ذلك إلى خوارزمية لقطة غير محدودة، والتي تحتاج فقط إلىيا(نسجل⁡ن){\displaystyle O(n\log n)}عدد العمليات لكل عملية مسحيا(ن){\displaystyle O(n)}عدد العمليات لكل تحديث. وقد أدخل إينوي وآخرون [ 10 ] تحسينات إضافية باستخدام عدد خطي فقط من عمليات القراءة والكتابة. وعلى عكس الطرق الأخرى المعروضة، يستخدم هذا النهج سجلات mwmr وليس سجلات swmr.

التطبيقات

توجد العديد من الخوارزميات في الحوسبة الموزعة التي يمكن تبسيط تصميمها و/أو التحقق منها باستخدام كائنات اللقطات المشتركة. [ 1 ] ومن أمثلة ذلك مسائل الاستبعاد، [ 11 ] [ 12 ] [ 13 ] وأنظمة الطوابع الزمنية المتزامنة، [ 14 ] والاتفاق التقريبي، [ 15 ] والإجماع العشوائي ، [ 16 ] [ 17 ] والتنفيذات الخالية من الانتظار لهياكل البيانات الأخرى. [ 18 ] وباستخدام كائنات اللقطات mwmr، يُمكن أيضًا إنشاء سجلات ذرية متعددة الكتابة والقراءة .

انظر أيضاً

مراجع

  1. 1 2 3 4 5 6 7 8 9 10 11 أفيك، يهودا ؛ عطية، هاجيت ؛ دوليف، داني ؛ جافني، إيلي؛ ميريت، مايكل؛ شافيت، نير (سبتمبر 1993). "لقطات ذرية للذاكرة المشتركة" . مجلة ACM . 40 (4): 873-890 . doi : 10.1145/153724.153741 . hdl : 1721.1/149162 . S2CID 52150066 . 
  2. 1 2 فيش، فيث إيلين (2005). "ما مدى صعوبة التقاط لقطة؟". SOFSEM 2005: نظرية وممارسة علوم الحاسوب . سلسلة محاضرات في علوم الحاسوب. المجلد 3381. سبرينغر برلين هايدلبرغ. الصفحات 28-37 . doi : 10.1007/978-3-540-30577-4_3 . ISBN   978-3-540-24302-1.
  3. ↑ لي، مينغ؛ ترومب، جون؛ فيتاني، بول إم بي (يوليو 1996). "كيفية مشاركة المتغيرات المتزامنة غير المنتظرة". مجلة ACM . 43 (4): 723-746 . CiteSeerX 10.1.1.56.3236 . doi : 10.1145/234533.234556 . S2CID 15035117 .  
  4. ↑ بيترسون، غاري ل.؛ بيرنز، جيمس إي. (1987). "القراءة المتزامنة أثناء الكتابة II: حالة الكاتب المتعدد". الندوة السنوية الثامنة والعشرون حول أسس علوم الحاسوب (SFCS 1987) . الصفحات 383-392 . doi : 10.1109/SFCS.1987.15 . ISBN  0-8186-0807-2.
  5. ↑ أندرسون، جيمس هـ (1993). "السجلات المركبة". الحوسبة الموزعة . 6 (3): 141-154 . doi : 10.1007/BF02242703 . S2CID 1688458 . 
  6. ↑ عطية، حجيت؛ حليهي، موريس؛ رحمان، أوفير (1995). “لقطات ذرية باستخدام اتفاقية شعرية”. الحوسبة الموزعة . 8 (3): 121-132 . دوى : 10.1007 / BF02242714 . S2CID 26538026 . 
  7. ↑ إسرائيلي، عاموس؛ شيرازي، آساف (1992). "بروتوكول لقطة فعال باستخدام اتفاق شبكي ثنائي". مخطوطة .
  8. 1 2 عطية، هاجيت؛ راشمان، أوفير (أبريل 1998). "اللقطات الذرية في O(n log n) عملية". وقائع الندوة السنوية الثانية عشرة لجمعية ACM حول مبادئ الحوسبة الموزعة - PODC '93 . الصفحات 29-40 . doi : 10.1145/164051.164055 . ISBN  0-89791-613-1. S2CID 15199715 . 
  9. ↑ إسرائيلي، عاموس؛ شاهام، أمنون؛ شيرازي، آساف (1993). "بروتوكولات اللقطات الخطية للأنظمة غير المتوازنة" . الخوارزميات الموزعة . سبرينغر. ص 26-38 . doi : 10.1007/3-540-57271-6_25 . ISBN  978-3-540-57271-8.
  10. ↑ إينوي، ميتشيكو؛ ماسوزاوا، توشيميتسو؛ تشين، وي؛ توكورا، نوبوكي (1994). "لقطة زمنية خطية باستخدام سجلات متعددة الكتابة والقراءة". الخوارزميات الموزعة . سلسلة محاضرات في علوم الحاسوب. المجلد 857. سبرينغر. الصفحات 130-140 . doi : 10.1007/BFb0020429 . ISBN   978-3-540-58449-0.
  11. ↑ دوليف، داني؛ غافني، إيلي؛ شافيت، نير (1988). "نحو عصر غير ذري: استبعاد l كحالة اختبار". وقائع الندوة السنوية العشرين لجمعية ACM حول نظرية الحوسبة - STOC '88 . الصفحات 78-92 . doi : 10.1145/62212.62220 . ISBN  0-89791-264-0.
  12. ↑ كاتسيف، هوارد ب. (1978). "حل جديد لمشكلة المقطع الحرج". وقائع الندوة السنوية العاشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '78 . الصفحات 86-88 . doi : 10.1145/800133.804335 . 
  13. ↑ لامبورت، ليزلي (1988). "مشكلة الاستبعاد المتبادل: الجزء الثاني - الصياغة والحلول". مجلة ACM . 33 (2): 327-348 . CiteSeerX 10.1.1.32.9808 . doi : 10.1145/5383.5385 . S2CID 7387839 .  
  14. ↑ دوليف، د.؛ شافيت، ن. (1989). "أنظمة الطوابع الزمنية المتزامنة المحدودة قابلة للإنشاء". وقائع الندوة السنوية الحادية والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '89 . الصفحات 454-466 . doi : 10.1145/73007.73051 . ISBN  0-89791-307-8.
  15. ↑ عطية، ح.؛ لينش، ن.؛ شافيت، ن. (1990). "هل الخوارزميات الخالية من الانتظار سريعة؟". وقائع الندوة السنوية الحادية والثلاثين حول أسس علوم الحاسوب [ 1990 ] . الصفحات 55-64 . doi : 10.1109/FSCS.1990.89524 . ISBN  0-8186-2082-X.
  16. ↑ أبراهامسون، كارل (1988). "حول تحقيق الإجماع باستخدام ذاكرة مشتركة". وقائع الندوة السنوية السابعة لجمعية آلات الحوسبة حول مبادئ الحوسبة الموزعة - PODC '88 . الصفحات 291-302 . doi : 10.1145/62546.62594 . ISBN  0-89791-277-2.
  17. ↑ عطية، هاجيت؛ دوليف، داني؛ شافيت، نير (1989). "التوافق العشوائي متعدد الحدود المحدود". وقائع الندوة السنوية الثامنة لجمعية آلات الحوسبة حول مبادئ الحوسبة الموزعة - PODC '89 . الصفحات 281-293 . doi : 10.1145/72981.73001 . ISBN  0-89791-326-4.
  18. ↑ أسبنيس، ج.؛ هيرليهي، م. (1990). "هياكل البيانات الخالية من الانتظار في نموذج PRAM غير المتزامن". وقائع الندوة السنوية الثانية لجمعية ACM حول الخوارزميات والهياكل المتوازية - SPAA '90 . الصفحات 340-349 . doi : 10.1145/97444.97701 . ISBN  0-89791-370-1.