Ортақ суреттер нысандары - Shared snapshot objects - Wikipedia

Жылы таратылған есептеу, а ортақ суретке түсіру нысаны түрі болып табылады мәліметтер құрылымы, ол бірнеше арасында бөлінеді жіптер немесе процестер. Көптеген тапсырмалар үшін a болуы маңызды мәліметтер құрылымы, бұл жад күйінің тұрақты көрінісін қамтамасыз ете алады. Іс жүзінде, жадының жай күйін тек біреуіне қол жеткізу арқылы алу мүмкін емес болып шығады ортақ тіркелім басқасынан кейін, өйткені жеке регистрлерде сақталатын мәндерді осы процестің кез келген уақытында өзгертуге болады. Бұл мәселені шешу үшін суреттің нысандары векторын сақтайды n компоненттері және келесі екеуін қамтамасыз етіңіз атомдық операциялар: жаңарту (i, v) ішіндегі мәнді өзгертеді менүшінші компонент v, және сканерлеу () барлығында сақталған мәндерді қайтарады n компоненттер.[1][2]Суретке түсіру нысандарын атомдық бір жазушы көп оқырманды қолдану арқылы жасауға болады ортақ тіркелімдер.

Жалпы, бір жазушы көп оқырманды (swmr) суретті нысандар мен көп жазушы көп оқырманды (mwmr) суретті нысандар деп ажыратады. Swmr суретке түсіру нысанында компоненттер саны процестердің санына және тек бір процеске сәйкес келеді Pмен жадына жазуға рұқсат етілген мен және барлық басқа процестерге жадты оқуға рұқсат етіледі. Керісінше, mwmr суретке түсіру нысанында барлық процестерге жадының барлық позицияларына жазуға рұқсат етіледі және жадыны да оқуға рұқсат етіледі.

Жалпы

A ортақ жады бірнеше бөлікке бөлінеді. Бұл бөліктердің әрқайсысы деректердің бір мәнін ұстайды. Бір жазушы көп оқырман жағдайында әр процесс Pмен жадына ие мен тағайындалған және тек осы процеске жадқа жазуға рұқсат етіледі. Дегенмен, кез-келген процеске жадтағы кез-келген позицияны оқуға рұқсат етіледі. Көп жазушы көп оқырман жағдайында шектеу өзгереді және кез-келген процеске жадтың кез-келген орнын өзгертуге рұқсат етіледі. Кез-келген процесс Pмен {1,...,n} in n-процесс жүйесі суретке түсіру объектісі бойынша екі әрекетті орындай алады: сканерлеу () және жаңарту (i, v). The сканерлеу операцияның аргументтері жоқ және жадтың тұрақты көрінісін береді. The жаңарту (i, v) операция жадты орнында жаңартады мен мәнімен v.

Операциялардың екі түрі де процестің шақыруы мен жадының қайтаруы арасында атомдық түрде жүреді деп саналады. Жалпы айтқанда, деректер векторында әр жазба г.к соңғысының дәлеліне сәйкес келеді сызықты жаңарту бөлігі жаңартылатын операция к жады.[1]

Бірлескен суретке түсіру нысандарының толық пайдасын алу үшін, валидациялар мен конструкциялардың оңайлатылуы тұрғысынан, суретке түсіру нысандарының құрылысына тағы екі шектеулер қосылды.[1] Бірінші шектеу архитектуралық болып табылады, яғни кез-келген суреттің нысаны тек онымен жасалады бір жазушы көп оқырманды тіркеу негізгі элемент ретінде. Бұл бір жазушыға арналған бірнеше оқырманның суреттері үшін мүмкін. Бірнеше оқырманға арналған бірнеше суретті суретке түсіру нысандары үшін пайдалануға болады көп оқырманды көп жазушы регистрлері, бұл өз кезегінде бір жазушы көп оқырман регистрлерінен жасалуы мүмкін.[1][3][4]

Таратылған есептеулерде жүйенің құрылуы бүкіл жүйенің орындалу барысында алға басуының мақсатына негізделеді. Осылайша, процестің мінез-құлқы бүкіл жүйені тоқтата алмауы керек (Құлып еркіндігі ). Мұның мықты нұсқасы -ның қасиеті күту еркіндігі, яғни кез-келген процесс басқа процестің өз жұмысын тоқтатуына кедергі бола алмайтындығын білдіреді. Жалпы алғанда, бұл кез-келген операция басқа процестердің жүріс-тұрысына қарамастан шектеулі қадамдардан кейін аяқталуы керек дегенді білдіреді. Алғашқы суретке түсіру алгоритмі жалпы жүйенің дамуына кепілдік береді, бірақ тек құлыпсыз болады. Бұл алгоритмді күтуге болмайтындай етіп кеңейту оңай. Афек және басқалардың алгоритмі,[1] бөлімінде көрсетілген Іске асыру осы қасиетке ие.

Іске асыру

Ортақ суретке түсіру нысандарын іске асырудың бірнеше әдістері бар. Бірінші ұсынылған алгоритм суретке түсіру нысандарының негізгі орындалуын қамтамасыз етеді. Алайда, бұл іске асыру тек -тің қасиетін қамтамасыз етеді құлып еркіндігі. Афек және басқалар ұсынған екінші ұсынылған іске асыру.[1] деп аталатын мықты қасиетке ие күту еркіндігі. Басқа іске асыруларға шолу Fich ұсынған.[2]

Негізгі суретке түсіру алгоритмі

Бұл алгоритмнің негізгі идеясы - кез-келген процесті орындау сканерлеу () жадының барлық мәндерін екі рет оқиды. Егер алгоритм бірдей жад мазмұнын екі рет оқыса, онда басқа процесс ешқандай мәнді өзгертпеді және ол нәтижені қайтара алмайды. Орындалатын процесс жаңарту (i, v) оның жадындағы мәнін жаңартыңыз.

функциясы сканерлеу () уақыт шын        a [1..n]: = жинау; b [1..n]: = жинау; егер (∀i∈ {1, .., n} i орналасуы екі оқылым кезінде оны оқудың арасында өзгерген жоқ)) содан кейін            қайтару b; // қосарлы жинау сәтті циклСоңы
функциясы жаңарту (i, v) M [i]: = v;Соңы
1-сурет: Бір процесс әрдайым жадыны жаңартады, екінші процестің екі еселенген жиынтығы кезінде. Осылайша, сканерлеу процесі ешқашан тоқтатыла алмайды.

Бұл алгоритм суретке түсіру нысандарының негізгі орындалуын қамтамасыз етеді. Бұл жүйенің алға жылжуына кепілдік береді, ал жекелеген жіптер жеке процестердің мінез-құлқына байланысты аш болуы мүмкін. Процесс Pмен басқа процестің алдын алуы мүмкін Pj тоқтатудан а сканерлеу () әрқашан оның мәнін өзгерту арқылы жұмыс, екі жад арасында жиналады. Осылайша, алгоритм болып табылады құлыпсыз, бірақ жоқ күтусіз. Бұл қасиетті күштірек ұстау үшін басқа процестердің мінез-құлқына байланысты ешқандай процестің аштыққа ұшырауына жол берілмейді. 1-сурет проблеманы бейнелейді. Әзірге P1 орындауға тырысады сканерлеу () операция, екінші процесс P2 әрдайым «қос коллекцияны» алаңдатады. Осылайша, сканерлеу процесі әрдайым әрекетті қайта бастауға мәжбүр болады және ешқашан тоқтап, аштықтан құтыла алмайды.

Afek және басқалардың бір жазушымен көп оқырманды іске асыруы.

Swek snapshot алгоритмінің негізгі идеясы Afek et al. бұл процесс басқа процестің жадының орнын өзгерткен-өзгертпегенін анықтай алады және процестер бір-біріне көмектеседі. Басқа процесс өзінің мәнін өзгерткен-өзгермегендігін анықтау үшін, әрбір регистрге есептегіш бекітіліп, процесс әрбір жаңартуда есептегішті көбейтеді. Екінші идея, жадының күйін жаңартатын әрбір процесс а сканерлеу () жұмыс және оның регистріндегі «жадтың көрінісін» басқа процестерге қамтамасыз етеді. Сканерлеу процесі мұны қарызға алуы мүмкін сканерлеу нәтижесі және оны қайтару.

Шексіз жадыға негізделген

Осы идеяны қолдану арқылы а күтусіз шектеусіз көлемдегі регистрлерді қолданатын алгоритм. Жаңарту әрекетін орындайтын процесс процесті сканерлеуді аяқтауға көмектеседі. Негізгі идея: егер процесс басқа жад орнын жаңартатын басқа процесті көрсе, онда бұл процесс толық орындалуы керек, сызықты, арасында жаңарту әрекеті. Мұны жүзеге асыру үшін әр жаңарту операция алдымен a орындайды сканерлеу жадын таңдап, содан кейін суреттің мәнін жаңа мәнмен бірге атомдық түрде жазады v және реттік нөмір. Егер процесс жадыны сканерлеп жатса және процестің жад бөлігін екі рет жаңартқанын анықтаса, жаңартуды аяқтау үшін «ендірілген» сканерлеуді «қарызға» ала алады. сканерлеу жұмыс.[1]

функциясы scan () // жадының тұрақты көрінісін қайтарады үшін j = 1 дейін n істеу жылжытылды [j]: = 0 Соңы    уақыт шын істеу        a [1..n]: = жинау; // жинайды (мәліметтер, дәйектілік, көрініс) үш есе b [1..n]: = жинау; // үштікті жинайды (мәліметтер, дәйектілік, көрініс) егер (∀j∈ {1, ..., n}) (a [j] .seq = b [j] .seq) содан кейін            қайту (b [1] .data, ..., b [n] .data) // жады өзгерген жоқ басқасы үшін  j = 1 дейін n істеу            егер a [j] .seq ≠ b [j] .seq содан кейін                 // процесс жылжытылды егер жылжытылды [j] = 1 содан кейін                    // процесс бұрын ауыстырылған қайту b [j] .қарау; басқа жылжытылды [j]: = жылжытылды [j] + 1; Соңы    Соңысоңғы функция
рәсім жаңарту (мен,v) // регистрлерді деректер мәндерімен жаңартады, реттік нөмірді жаңартады, енгізілген сканерлеу s [1..n]: = қарап шығу; // ендірілген сканерлеу rмен : = (v, rмен.seq = rмен.seq + 1, s [1..n]);аяқтау процедурасы
2-сурет: Бір оқырманның көп оқырмандық суретке түсіру нысаны үшін сызықтық тәртіптің мысалы. Бірінші сканерлеу () екі рет жинауды сәтті орындай алады, ал екінші сканерлеудің «екі рет жинауы» екінші процесспен екі рет үзіледі. Осылайша, процесс енгізілген сканерлеуді алады.

Әрбір регистр деректер мәніне арналған өрістен, реттік нөмірден және соңғы жаңартуға дейін жиналған соңғы енгізілген сканерлеу нәтижесінің өрісінен тұрады. Әрбір сканерлеу операциясында процесс Pмен реттік нөмірді пайдаланып, процесс өзінің жадын өзгерткен-өзгертпейтіндігін шеше алады. Егер екі рет жинау кезінде жадында өзгеріс болмаса, Pмен екінші сканерлеудің нәтижесін қайтара алады. Процесс басқа процестің жадты жаңартқанын байқағаннан кейін, бұл ақпаратты жылжытылған өріске сақтайды. Егер процесс болса Pj сканерлеуді (), сканерлеу процесін орындау кезінде оның жадын екі рет өзгертті Pмен жаңарту кезінде өзінің регистрінде сақтаған жаңарту процесінің енгізілген қарап шығуын қайтара алады.

Бұл операциялар болуы мүмкін сызықты әрбір жаңарту () әрекетін регистрге жазу кезінде сызықтық жолмен. Сканерлеу әрекеті сызықтық сипатта күрделене түседі. Егер сканерлеу операциясының қосарланған жиынтығы сәтті болса, сканерлеу әрекеті екінші сканерлеудің соңында сызықтық сипатқа ие болуы мүмкін. Басқа жағдайда - бір процесс өзінің регистрін екі рет жаңартты - жаңарту процесі оның мәнін регистрге жазбас бұрын енгізілген сканерлеуді жинау кезінде сызықты түрде жүргізілуі мүмкін.[1]

Шектеулі жадқа негізделген

Ұсынылған алгоритмнің шектеулерінің бірі оның негізделетіндігінде шексіз жады өйткені реттік нөмір үнемі өсіп отырады. Осы шектеуден шығу үшін, процесс арасында жадының екі рет өзгергендігін анықтаудың басқа әдісін енгізу қажет. Процестердің әр жұбы екі жазушы бір оқырманды (swsr) екі атомдық биттен тұратын екі регистрді қолдана отырып байланысады. Процесс «екі рет жинауды» бастамас бұрын, серіктес процестің мәнін өзінің жеке регистріне көшіреді. Егер сканер-процесс болса Pмен серіктес процестің құндылығын «екі рет жинауды» орындағаннан кейін байқайды Pj арасында өзгерді, бұл процесс жадта жаңарту әрекетін орындағанын көрсетеді.[1]

функциясы сканерлеу () // жадының тұрақты көрінісін қайтарады    үшін j = 1 дейін n істеу жылжытылды [j]: = 0 Соңы    уақыт шын істеу        үшін j = 1 дейін n істеу qi, j : = rj.pj, i Соңы        a [1..n]: = жинау; // үштікті жинайды (деректер, бит-вектор, ауыстырып қосу, қарау)        b [1..n]: = жинау; // үштікті жинайды (деректер, бит-вектор, ауыстырып қосу, қарау)        егер (∀j∈ {1, ..., n}) (a [j] .ppj, i = b [j] .pj, i = qi, j) және a [j] .toggle = b [j] .toggle содан кейін            қайту (b [1] .data, ..., b [n] .data) // жады өзгерген жоқ        басқасы үшін  j = 1 дейін n істеу            егер (a [j] .pj, i ≠ qi, j) немесе (b [j] .pj, i ≠ qi, j) немесе (a [j] .toggle ≠ b [j] .toggle) содан кейін // процесс j жаңартуды жүзеге асырды                егер жылжытылды [j] = 2 содан кейін                   // процесс бұрын ауыстырылған                    қайту b [j] .қарау; басқа жылжытылды [j]: = жылжытылды [j] + 1; Соңы    Соңысоңғы функция
рәсім жаңарту (мен,v)                        // барлық регистрлердің деректер мәнімен, «жазу күйімен» регистрлерді жаңартады, ауыстырып қосқыш пен енгізілген сканерлеуді төңкереді    үшін j = 1 дейін n істеу f [j]: = ¬qj, i Соңы    s [1..n]: = қарап шығу; // ендірілген сканерлеу    рмен : = (v, f [1..n], ¬rмен.toggle, s [1..n]);аяқтау процедурасы

Шектелмеген реттік нөмір екіге ауыстырылады қол алысу биттер процестердің әр жұбы үшін. Бұл қол алысу биттері swsr регистрлеріне негізделген және оларды матрица арқылы көрсетуге болады М, қайда процесс Pмен жолға жазуға рұқсат етілген мен және бағандағы қол алысу биттерін оқуға рұқсат етіледі мен. Сканерлеу процесі қосарланған жинауды бастамас бұрын, оның бағанын оқып, барлық регистрлерден барлық қол алысу биттерін жинайды. Осыдан кейін, процесс екі еселенген мән кезінде өзінің мәнін өзгерткен-өзгертпегендігін шеше алады. Сондықтан процесс тек бағанды ​​қайтадан бастапқыда қол алысу биттерімен салыстыру керек. Тек бір процесс болса Pj жинау кезінде екі рет жазды Pмен сканерлеу кезінде қол алысу биттері өзгермеуі мүмкін. Сонымен, «ауыстырып қосқыш» деп аталатын басқа бит енгізу керек, бұл бит әр жазуда өзгертіледі. Бұл кез-келген басқа процесс өзінің тізілімін жаңартпаса да, екі жазбаны қатарынан ажыратуға мүмкіндік береді. Бұл тәсіл сканерлеу процедурасында ешнәрсені өзгертпестен, шектелмеген реттік нөмірлерді қол алысу биттерімен ауыстыруға мүмкіндік береді.

Сканерлеу процесі кезінде Pмен оның қосарлы жиынтығын қолдана алатынын анықтау үшін қол алысу битін қолданады, басқа процестер жаңарту әрекеттерін де орындай алады. Алғашқы қадам ретінде олар басқа процестерде берілген қол алысу биттерін қайтадан оқып, олардың толықтырылуын жасайды. Осыдан кейін бұл процестер қайтадан енгізілген сканерлеуді қалыптастырады және жаңартылған деректер мәнін, жинақталған - толықтырылған - қол алысу биттерін, толықтырылған ауыстырып қосуды және кірістірілген сканерлеуді регистрге сақтайды.

Қол алысу биттері реттік сандарды баламалы түрде ауыстырғандықтан, сызықтық жадының шексіз жағдайындағыдай.

Multi-Writer Multi-Reader бағдарламасын Afek және басқалар жүзеге асырады.

Көп жазғышты көп оқырмандық суретке түсіру объектісінің құрылысы деп болжайды n тұратын жадтағы кез келген орынға процестерді жазуға рұқсат етіледі, ол тұрады м тіркеушілер. Сонымен, енді процесс идентификаторы мен жадтың орналасуы арасында ешқандай байланыс жоқ. Сондықтан, қол алысу биттерін немесе енгізілген сканерлеуді деректер өрістерімен біріктіру енді мүмкін емес. Демек, қол алысу биттері, мәліметтер жады және енгізілген сканерлеу бір регистрде сақтала алмайды, сондықтан жадқа жазу атомдық әрекет емес.

3-сурет: Көпжазбалы көп оқырмандық суретке түсіру нысаны үшін үлгілі сызықтық көріністі көрсетеді

Сондықтан жаңарту () процесс үш түрлі регистрді дербес жаңартуы керек. Алдымен ол қолмен оқитын биттерді сақтауы керек, содан кейін енгізілген сканерлеуді жүзеге асырады және соңында оның мәнін белгіленген жад орнына сақтайды. Әрбір жазу дербес түрде атомдық түрде жасалатын сияқты, бірақ бірге емес. Жаңа жаңарту () процедура кейбір өзгерістерге әкеледі сканерлеу () функциясы. Енді қол алысу биттерін оқып, жад мазмұнын екі рет жинау жеткіліксіз. Басталуын анықтау үшін жаңарту процесс, процесс жад мазмұнын жинағаннан кейін екінші рет қол алысу биттерін жинауы керек.

Егер екі рет жинау сәтсіздікке ұшыраса, ендірілген сканерлеуді бастамас бұрын процесс басқа процестің үш рет жылжуын көруі қажет. 3-сурет проблеманы бейнелейді. Бірінші қос жинау сәтсіздікке ұшырайды, өйткені жаңарту сканерлеу операциясы жадты жазуды аяқтағанға дейін басталды. Алайда, осы жазбаның ендірілген сканері бұрын орындалады және сақталады P1 жадыны сканерлеуді бастайды, сондықтан сызықтықтаудың жарамды нүктесі болмайды. Екінші қос жинау сәтсіздікке ұшырайды, өйткені процесс P2 екінші жазуды бастайды және қол алысу биттерін жаңартады. Swmr сценарийінде біз ендірілген сканерлеуді қарызға алып, оны қайтарамыз. Mwmr сценарийінде бұл мүмкін емес, себебі ендірілген сканерлеу екіншісінен басталады жазу сканерлеу интервалында әлі де сызықты емес (жұмыс басталады және аяқталады). Осылайша, сканерлеу аралығы кезінде кем дегенде бір ендірілген сканерлеу сызықты болғанына толық сенімді болу үшін процесс басқа процестен үшінші өзгерісті көруі керек. Бір процестің үшінші өзгеруінен кейін сканерлеу процесі сызықтық критерийін бұзбай ескі жады мәнін ала алады.

Күрделілік

Afek және басқалардың бірлескен суретке түсіру нысандарының негізгі ұсынысы. қажеттіліктер жад операциялары.[1] Андерсонның өз бетінше жасаған тағы бір іске асыруы экспоненциалды операцияларды қажет етеді .[5] Сондай-ақ, swmr регистрлеріне негізделген жедел суреттер нысандарын кездейсоқ іске асырулар бар операциялар.[6] Израиль мен Ширазидің шексіз жадыны қолдана отырып, тағы бір іске асыруы қажет жадыдағы операциялар.[7][8] Израиль және т.б. кез-келген жаңарту операциясы үшін төменгі деңгейдегі операциялардың төменгі шегін басқа жұмыста көрсету. Төменгі шекара , қайда w бұл жаңартқыштардың саны және р сканерлер саны. Аттия мен Рахман swmr регистрлеріне негізделген детерминирленген суретке түсіру алгоритмін ұсынады жаңарту және сканерлеу кезіндегі операциялар.[8] Израиль, Шахам және Ширазидің жалпы әдісін қолдану [9] мұны шектеусіз суретке түсіру алгоритміне дейін жақсартуға болады, оған тек қажет сканерлеуге арналған операциялар және жаңарту бойынша операциялар. Inoue және басқалар ұсынған одан әрі жетілдірулер бар,[10] тек оқу және жазу операцияларының сызықтық санын қолдану. Ұсынылған басқа әдістерден айырмашылығы, бұл тәсіл swmr регистрлерін емес, mwmr регистрлерін қолданады.

Қолданбалар

Бірнеше алгоритмдер жылы таратылған есептеу ортақ суретке түсіру нысандарын қолдану арқылы дизайнда және / немесе тексеруде жеңілдетілуі мүмкін.[1] Бұған мысал ретінде алып тастау проблемалары,[11][12][13] уақыт белгілері бойынша жүйелер,[14] шамамен келісім,[15] рандомизацияланған консенсус[16][17] және басқа деректер құрылымдарының күтулерсіз орындалуы.[18] Mwmr суретті нысандары арқылы атомдық көп жазғышты көп оқырман құруға болады тіркеушілер.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б в г. e f ж сағ мен j к Афек, Ехуда; Аттия, Хагит; Долев, Дэнни; Гафни, Эли; Меррит, Майкл; Шавит, Нир (1993 ж. Қыркүйек). «Ортақ жадының атомдық суреттері». J. ACM. 40 (4): 873–890. дои:10.1145/153724.153741.
  2. ^ а б Fich, Faith Ellen (2005). «Суретке түсіру қаншалықты қиын?». SOFSEM 2005: Информатика теориясы мен практикасы. Информатика пәнінен дәрістер. 3381 (SOFSEM 2005: Информатика теориясы мен практикасы. Ред.). Springer Berlin Heidelberg. 28-37 бет. дои:10.1007/978-3-540-30577-4_3. ISBN  978-3-540-24302-1.
  3. ^ Ли, Мин; Тромп, Джон; Vitanyi, Paul M. B. (шілде 1996). «Бір уақытта күтетін айнымалыларды қалай бөлісуге болады». J. ACM. 43 (4): 723–746. CiteSeerX  10.1.1.56.3236. дои:10.1145/234533.234556.
  4. ^ Питерсон, Гари Л; Бернс, Джеймс Э. (1987). «II жазу кезінде қатар оқылым: көп жазушының кейсі». Информатика негіздері, 1987., 28-ші жыл сайынғы симпозиум. 383–392 бб.
  5. ^ Андерсон, Джеймс Н (1993). «Композиттік регистрлер». Таратылған есептеу. 6 (3): 141–154. дои:10.1007 / BF02242703.
  6. ^ Аттия, Хагит; Хелихи, Морис; Рахман, Офир (1995). «Торлы келісімді қолданатын атомдық суреттер». Таратылған есептеу. 8 (3): 121–132. дои:10.1007 / BF02242714.
  7. ^ Израиль, Амос; Ширази, Асаф (1992). «2-торлы келісімді қолданумен суретке түсірудің тиімді хаттамасы». Қолжазба.
  8. ^ а б Аттия, Хагит; Рахман, Офир (сәуір, 1998). «O (n log n) операцияларындағы атомдық суреттер». Есептеу бойынша SIAM журналы. 27 (2): 319–340. дои:10.1145/164051.164055.
  9. ^ Израиль, Амос; Шахам, Амнон; Ширази, Асаф (1993). «Теңгерімсіз жүйелер үшін сызықтық уақыттық суретке түсіру хаттамалары». Таратылған алгоритмдер. Спрингер. 26-38 бет. дои:10.1007/3-540-57271-6_25. ISBN  978-3-540-57271-8.
  10. ^ Иноуэ, Мичико; Масузава, Тошимитсу; Чен, Вэй; Токура, Нобуки (1994). Көп жазушы көп оқырман регистрлерін қолданатын сызықтық уақыттық суретке түсіру. Таратылған алгоритмдер. 857. Спрингер. 130-140 бет. дои:10.1007 / BFb0020429. ISBN  978-3-540-58449-0.
  11. ^ Долев, Дэнни; Гафни, Эли; Шавит, Нир (1988). «Атомдық емес дәуірге қарай: сынақ жағдайы ретінде l-алып тастау». Есептеу теориясы бойынша ACM жиырмасыншы симпозиумының материалдары. 78-92 бет.
  12. ^ Катсефф, Ховард П (1978). «Сындарлы бөлім мәселесінің жаңа шешімі». Есептеу теориясы бойынша оныншы ACM симпозиумының материалдары. 86–88 беттер.
  13. ^ Лампорт, Лесли (1988). «Өзара алып тастау мәселесі: II бөлім - мәлімдеме және шешімдер». ACM журналы. 33 (2): 327–348. CiteSeerX  10.1.1.32.9808. дои:10.1145/5383.5385.
  14. ^ Долев, Дэнни; Шавит, Нир (1989). «Уақыт штаммының шектелген жүйелері құрастырылады». Есептеулер теориясы бойынша жиырма бірінші ACM симпозиумының материалдары. ACM. 454-466 бет.
  15. ^ Аттия, Хагит; Линч, Нэнси; Шавит, Нир (1990). «Күтусіз алгоритмдер жылдам ба?». Информатика негіздері, 1990. Жинақ., 31 жылдық симпозиум. 55-64 бет.
  16. ^ Авраамсон, Карл (1988). «Ортақ жадты қолдану арқылы консенсусқа қол жеткізу туралы». Таратылған есептеу принциптері бойынша жетінші жыл сайынғы ACM симпозиумының материалдары. 291–302 бет.
  17. ^ Аттия, Хагит; Долев, Дэнни; Шавит, Нир (1989). Шектелген полиномдық рандомизацияланған консенсус. Таратылған есептеу принциптері бойынша сегізінші жыл сайынғы ACM симпозиумының материалдары. 281–293 бб.
  18. ^ Аспнес, Джеймс; Херлихи, Морис (1990). «PRIN асинхронды моделіндегі деректердің күтілуінсіз құрылымы». Параллельді алгоритмдер мен архитектуралар бойынша екінші жыл сайынғы ACM симпозиумының материалдары. ACM. 340–349 беттер.