グリッドコーラムによる効率的な分散相互排除アルゴリズム

全文

(1)2005−AL−103（12） 2005／11／11. 社団法人情報処理学会研究報告 IPSJ SIG Technical Report.

(2) !#"%$'&)(*$#+%,#-!$. /10 2436587:9<;>=@?BADC:E4FHGJILK8MON6PRQHSUTWVYXOZU[4\:]6^`_<aLGDb@cdPRQd;èYf:g1hLGJi:Z4[4\:]Yj4; kOlRm [:^>n6FoGJp1qBAWr6st^vu4w1FxGDI1KUMdN1yvz|{d}~1]BLJ6THRt U]BJ:vGD1:`LH^vbL|Ry z:xo{tB}~1 ]L¡v¢ ^YvFoGJ<<B6tGDi6cYdg1S4THRt 4]L^>bL|Ry`zk {d}~1]@gYT<Z4[Y\<]L^R1 ktlm [<A ?d;6y`z{d}~1]Y;8£1¤d^YoJ4¥6¦tAWFoGDiRt 4]1§v¨ LD©B}Uª«Rt U]1AR¬1®¯T` ktlm [<A <Bo ¡ Z@[@\<]@g1SYT4°1±4:|²³oG1Wt U]1A¬16FG H´Wµ £1¤< ¡ GDI1KUMtN1yvz{ }¶~1]Y;v·Y¸oAWFoGJi :. Efficient Algorithm by Grid Based Quorum for Distributed Mutual Exclusion Sen Moriya Department of Informatics, School of Science and Engineering Kinki University Abstract: Designing an algorithm for solving the mutual exclusion problem is an fundamental issue in distributed systems. Some researchers have investigated quorum based mutual exclusion algorithms, which can achieve load balance among processes in the distributed system. In this paper, we consider efficiency of quorum based mutual exclusion algorithms in case some processes have failed. We propose an algorithm by grid based quorum, and show that the proposed algorithm is more efficient than an algorithm based on a general quorum in the face of some failed processes.. ¹ º®»½¼ ¾ O;H¿ÁÀ:^Â6Ã@FtG kOlJm [Y>ILK^@Ä<ª m LÅvÆ4ÇtAJw RÈ ^ d´ °8ÉHADw VYXOZ8[4\:]6AR¥tÊYGJivV XOZ@[@\<]Y;`bYcOÑ<PW QH;8e6fdÛT4Ë4d ; kdlm [6 f<kO;8lJ2Ym 3L5U7 2Y3BÌ1Í¨4zkOT lDk m }WÎ4§ÏT<Ä`Ð®} ¡HÑ A¯Ò: FHG>Ó1¡W;>ÛU=@Ü?t^ nYÔYÛ FBGvÕBß PRQO1h:È GJiU=@? [6;:Ö`Õo²T f<; [L;U×<^WnØ82@3658719 ;>Ù4Ú Ý1Þ@TÙ A@h8à:Ê6G ¯g`=@?tAJC:E4FHGvPRQoAá@â6ãLä6åvæ È i ;YPWQBkdADlC6m ç6FBG¯è<Û é ¡`ê@ë YJ@ToÛ }³:ì>í6îyWzx{O}~Lkd] lm AR1dG È JÛ 8¥tÊd²ÏBG`¡ @T È ;`ï üû4ë ý:g6þS ÿ±<^6^ dGðo>ñ _ UO[6:Uh:Ù GDi YA>ò@àYóôTOhLJYG T@Ùf<; kdARõ1löØm [6J@ tY GD÷tô; ¡ ´ T 1[6U; øLkdùdlm ^>Ù[645UA>7HòYóO;WÒ:g<Bú ARõ1öY¯Fo G kdlm Û Ê6G H ¡ ï ë g6SU T @

(3) B^ ¡ G kOlDm [L^pLq ÖFoG È W^ ¡x´ TvV@XOZ@[4\:]L^Yh ´ [L ^>ÙgLS ¡ A d 8i È g@T È ®²J; ADC:EUFoGDVYX@ILK`MONLyvzx{O} ~L]H6J@T ¯1>HG L:`LH^>bL|yvz{d}~1]L^YvFBG¯<<B@tG ¡ i ´ Rt 4]Ykt;>lLm H^>bL I1KUMdN1´ yvz {d}~1]Y;4_6_ YÕ dBS O´ ;8° g:h:WGDßi|Rt U]6SvV6XdZY[@\<]L^ FG! [1;"LV <?dg:h T #:Ý$;dWB U]6; :?B^ >d§o}@ 1?&%BA'&(LFGDi

(4) )*t; fOkd;tlDRm H U]LS4T +,:26° kdlRm [A -1fYi6Ù Û A +&. ¶FoG kdktlDlm m [1SYT1hG fd;dWt U]1Û ^ FoGRF /O ;È H [:¡ ^WnØJ85U7oA¯Ò:YFBG .YödA 0UÉô¯

(5) T Y;` F /:L; 7 [6Õ2² 13AóOà 4

(6) 1g`Ù 6A 5@óOg:¡ úLGDi ; TORd U]6^>b6xRy>z{O}~L]6SUT ^ `·Y¸ :à 9i 8: g1S8T ;9<< R. 1. 1. (. ). 1. (. ). (mutual exclusion problem). [5]. 1. [3]. (quorum). [1, 2, 7]. 1. 2. 1. 1. =?>. Sanders. Maekawa. [7] @BA?C DFEHG Maekawa I?JLKMONFPRQ2SBTU6VXWHUZY[I]\_^?`baHc6dfe gbh[i_j]ARCDuEOG?kblBnqI]v6w]e Maekawa IRJBKMqNxPHQzy[h|{?r. −77−. [7]. Sanders. 1. [7]. gHh]i]j_kmlLnbaBA2CDFEOj_oqp [9]]r s2tb@mS[e.

(7) ` ]@ë;' ( ë 6@TW3~}

(8) 9 ^Rb6 ï ë O 8] kOlDm [:A69< ¡ 99$^ 4F GDï ©o}`ª«Rd U]

(9) <@tGJiRt 8]L^>b6| ILKUMdN1µ y>z{d} ~1]6SUTLyvz{O}~1]@;v£1¤<S Rt 4]Bv©B}@ª« >t U]6S4T ^Rt 4]ë Y¨:~:S g:h:GDiOà H¯6T UL]Y;:6^@¨:S ~:^1DFotGD 8i ]@;vïd D t 8 ] Y 1 ¨ Y ~ x J 4 Y e : ï O T d 8 Y ] ; 9 ' ( 1 S H © U } H ª ¶ « t 8ë ]@;`ï: È ë H ¶ ¡ ég1hLGJ&i g@T1©H}`ªo« d 8]@;'9( ARbdÛT<t `]@¨1~:AOL²^6¶FHG '( ; : µ @tGDi êYë Rt 4]L^>bL| S4THRt U]6jY;¡ kdlm [6 ¡BÑ ^ H´ :®ÈJà ¢ ?Og µ T 1;dRt U]@g1yvz{d} ,t^R÷H ;dRt¡ U]1¡ AR&í ¡ ô _|JLy`z{d}~1]1zA &1¡ FoG D

(10) 3

(11) ¡tg:Ñ h:GDiôJÕxJTHRt U]1A ¡ ~L]:´? zA Á í 9o aRd ² ²TYy>zx{O}~6]YS Y£L¤1<^ GD

(12) i 89: g1SUTdDd 8]L^ G¯I1K MN1y>z{O}~L]4¡ g ! klDm [Y>L®4 ¾ ¥&¡ ¦ Ht `]LA ¡Yfda 7 ¢WF @g6;>£1¤d6A £ ¤ 9¾ ¥¦ b§

(13) È6¨®È ¯T©«ª t U]L^8_O a1G6£ ¤ ^YvFoGR¥6¦OAw @tGDi g6T4e ¬t;dRt U]1^ GDI1¡ KUMdN<yv¡ z{d}~1]@g:S4THRt U]1R´ ARí L FoG &®L ¡ ¯

(14) ° U¥HÊt² ¡ ¡ ²TBRt U]6S< LÎUì6]L^v í ô aWd m² ,YTHRt U]>í d; G Y£1¤ ±A ² ³1FoGU;L S ´µtg:h GJi1eYï<kdTOlm ©B}Uª«Rt U]Yg1S4 T )*O; f;dRt U]@ kdlm [UÝkd$<lm;8&Æ OAµ -·¶UT Ñ ; kdlm [69 U®² ;`&Æ [6g:h:G`Õ6 ¸&¹t

(15) ^ ºYÕOGDi YàYT4e ¬t;dRB U]@g1S [6g 1®J@1àx²URt U]BL »~®È ¡ :;1^>nô¢ ¯TO©B}Uª «7Rt U]@g1S@xf<ÕL; ktlm [6ktv1l®m D@1 µ Rt¡ 4]BLJL;»~HA6¼FBG D6g< ¾ ú1¥&G ¦ ?O:h:¡ GDi 4Tt©tkd}@lªm « >t U]@g1S4T ! [6v1ôJ@ oRt U]1 A ¡6ft

(16) a ¢ F µ 6gL; £ ¤ ~ g1S TYx¡ f<Õ1; [6v1®D@tGO:ÈJ µ RH U]BÜ LDL; »BÛ 6A ¼-ôJYtkG lDm;<[6 A ¡Y`£1ft¤:

(17) a <¢vF6^£1t¤< U½ ]Y.;v í BAGDwi6cY7 d`Ù g1Û S4ATd56©HóO}4g<ªú1«¶G WBt U ¡ ]Yyv; z®{d}²~L; ]Y¾;8¿t¥6A ¦tAôw JY i TUÙ A . À6FoG [10]. (. (FPP. ). ). √ O( n). FPP. FPP. [4, 6]. [8]. (probe complexity). 2. 2. 1. ÁÃÂÅÄÇÆÉÈËÊÍÌÏÎÉÐÒÑ VYXOZ@[U\:]LA kd¡ lDm µ [L ? P = {P , P , ..., P } T)&*<; kOkdllm m [ Ó4g1Ädª m <ÅvÆ4Çt^ H´ °UÉBADw à¡BÔ Ñ ;`°@HÉ ´ }WÎ98Õ kdÕxl² m G ;o FoGDiOà µ DT P ¡ ^ FoGF</ 1; [6ÖLÂô2oaUOGORS }²m,YT ^ e9O" ; [1SW1®kdlJm@tG`Õ ³ Ui cYdg:S4T`1®kdlJm@tG [<kdAl× m ØÙÚzÛ ÜkdlJm91 T`1 kdlm [UkdÝ9lÝdm ; kd¡ lm [<A Þ ßà¡ ÙµÚzÛ Ü|Já6g â Ú: S ã®² ; Fo¡ GDi Ö kÂ dFolDm GDi [6ÖLSR÷tÂ ;6Ö Â kO[:lS4m T`[o÷t³; ILKd^YÄd[1ªm ÖL:Â Å`Æ4Çt^ [Ldg:´ h:°UG`ÉOÕvg<1úL GDi&L ;`[ °UÉH;YS Õ:FIFO É9Lä °UÉOT`F º&8¶ T hLG kOlJm [ P kdÕlD²üm ÷d; kOlm [ P 940 É m ¶à1Äª m <Å@SUTvm 3}

(18) 4`Ó ÝjY^40 kdÉltå m ^ P Uæ ÉLFBG µ ;B F GJiY àYT`1 kdlm[U99@0 ÉØà:Ädª kd<lÅ6m S4T

(19) Hç >:Ätª <kdÅBlmLJ@0 É Û [6@æ ÉLFoGDi ËR;`=6?LFoGRß [L;<Ö8Õ² 1 f; [ARí«o¢ ¯T 1 ; H´ [:^vn®J8Ù A t ÊLG=6?YC<E<PWQA áYâLã:äLå8æØ i6c 8 g1S4T8I1K8MdN1PWQA>Ý:Þ1; 2 è

(20) Bé ^ §

(21) 6¨ FoGDi * ;

(22) 4t ê ^8_61YTUÙ Û AzëL - FoG kdlm [L;vdSìª 1 f:g:h:GDi • )O Û A61- f kOlJm [1S+9Y, 3}

(23) 4`Ó Ýj6^6 ;vÙ Û AC Yí FBGmî&4§ FHGJTvÙ Û A.9À JUdG kOlm [@ • Ù Û ¡ È ¡. 2. 1. i. n. 2. j. j. Lø ùd^>Ù ARóô²³ RS Ui ILK8MÛ N6PRQoAJC y>zo{O}¶~Y]@H;>´_£Lñ9¤:ò SUT kOlDm [@`Ù Û kdAl.9m À@FtG`y>Û zo{O}¶~6µ ]6Aï µ ð YÕo¡ ²TL; kOl¯mk [YlDmUÙ AÛ56óLFoGYgL;

(24) 4&Ó1^ FoGDi1Ùd^4T`Û÷t; [6UÙ Azë&- .À J@ ß |>úYÛT [68Ù A . À@FoG8yvz{d}~1]1Aïð®J6Õx²³Ù Az56óLFoGYgL;

(25) 4Ó:A8Tóôõ öxJ i. 3. ÷ùøúÌüûþýÅÿ Ê.

(26) . Ñ Ê. êUë ë k lD£Lm ¤1[ 11?ÎLK8^>Mn®N6¯PRT QoA¯;CØ < g ¡ 6"6¯VU 1T:? Dd 8A ]t1#9>'t(ôGJ¯LT 1 1? 9% t^b6L6àWC H ã ² :;4è

(27) Oé GJi Adà8FØ>ú8T A | LT A Rß i )*; ^>n®JYT. 3.1. P. (i). Qi. P. i, j(1 ≤ i, j ≤ M ). Qi. M. Q. Qi ∩ Qj 6= ∅. −78−. Q = {Q1 , Q2 , . . ., QM }. (i)(ii).

(28) (ii). )*<;. 3.2. i, j(1 ≤ i, j ≤ M ). ^>n®JYT. Qi 6⊆ Qj. !#"$&%'()*,+-/.10. R t U]L^>bL|³I1KUMdN1yvzkd{dlm }¶~1]B<L JYT ;6y>z{do} ~1]@ã®² @tG i ;vI1K MON:yvz{d}~1]1A>btÛT`1 [OA Z@[@\<]1^>n32dg<ú1G ^BJàYT4e¬t;tRt U]Y;YàÔY;vI1KUM NLyvz{d}~1]1A>Ý1Þ<^54/BGDi Ù Û Û A +.|³FHG kOlDm m [ SUT<§B}D^ È6FBÈ GUh1GLRO 8] Aí

(29) ®T ^ FBGJF /:L; kOlJm [:^>Ù A . ÀYFoG4Ätª <Å A 0@É1FoGDi gYT 6 ÔU A>u4w1Fo7 GO>úUS4T<hB²JÕxñ ÔWç ÔU@_61à

(30) 7 ¡ t U]1A L7 ¯` í LFoGDi 894YFoG Õx;² : A>u4wLFoGOWú@S8T`«ç ÔB²³<=à <?>3@?A C^ B = DL í O;dt U] ; ftA LJ` í LFoGD9i E94®Jà CS D0@Ét; kdlm [L;4×<^ 0@É1FoGDi YàYT ^YS4T§v¨]@[<§1Î k LJ 0@É 41; ~4GF C; Ho5A I3JôJ@_xüi Ñ µ O k l m O k l m Am 6æ4ÉôJà [ S8T

(31) L;496g kOlD; m [LÛ ^ Ù Û A dÊ8¡ U ¡ ¡ ²UHT 94Ù Û A tÊ Û G8ÄO A tª Ê8:YÅtG kdlm 6A [<04A ÉLFBGJLi ¯T 1h1 G Õxm² æ@[6É ^WÙ Jà A OÊ`C^ 4I9dJ G ²D@UtTWzG Ý1ÞL~; 4GF5; ^WHoFB5A G K9L6FovGDÙ i ~4GFM; Hd |D4ïtO^ NPE ¦ :h:GO FoGDi ;vïC NQE ¦ ìY ¡ ²JUÛ T 9S U ^WÙ Û AWe ¦1R1S FoÛ G H . À4FBGDmi `Ù Û A R1S FBGvT6h G><S`5UÛ 7H;WRQÒ:S H5A TH¢ Ê88Ù A Jàx²¯T S 9YÙ A tÊ:G4Ätª OÅ A 0@É1FoGDi 8Ù A ¦ Jà ?t¡ S4T ; . À A ; ë&-6FoG V·¶Qw WHM^ X1YLFoGDi ;`ïCNPE

(32) ì6 ²UT ;. À A ;ë -LFoGV·¶wQWH^MX9YLFoGDi 7 kdlDm Û Èà W ^ ¡ GDi A æd a>ò à Aæ@É [LJà; 1kd?lm`«ç[6g6ÔBTU² Ù Û=à Z3A[Q56\1ó ]QJ^3à9_ 49:;HOA ROtà Ud] 4T ^ SvÙ`@6A 56 ó¡ g<kú lm [ 3`1FBG ¡ ²4T S È ; 491g ^6Ätª m <Å A 0UÉ1FoGDi B ´ ¡ È 7 d k R l m 6àYT ´ ^ FxGJ: [<^ è é adào D&ºYÕ à ¢ ?tS@T Õx²yvz|{d}J~ ]1CA b 8F8i U5U7d;WÒ1tA5TtÊ8à 7 ¡ ²Jkd4lT m ^ FoGJF /<6; kOlm [:^RÙ Û A 9¡ U FoGUÄOª m :Å µ ¦ A0 É1Foµ G¯i ´ A æHat kdàlDm [ S4aT V·¶DQw Wd;<Ö4 ^ . À<Lh:G ²49T 1;<Öàg c NPE ; ì ;:A>ò ¢oJY T 1; [:^ 6A 0@É1FoGDi È@È g@T )&*;`ï ë ^ t´ ' (®Jà8e ¬t;OO§B}gLS8T ;Ot 8] ;W9í ¯° ;vÙ Û 5@ó è é S`Ý:Þ1; B ^ ¡ GDi í Û ¯

(33) ° )*5; DL í d;dRt U]LAR í LFoGDkdi lm 9 Ù 56ó è

(34) é Rt 8] ^ FoGDF /<L; [6Õ² A æ@ÉLFoGDi ¯ ° Û È B Ý1ÞLgLS4TW í T>Ù 5Yó èéoA ; C^ d&§ ¯àLy>z{O}~6]1A`1T efhgjë i

(35) Ü J ß i@e ï:TUc@tg`·Y¸1¡ FoGY©o}Uª«Rt U]L¯^ ° GRI1KUdMd´ N1yvz|{d}~1]@g1S@ T 1; '´ ( Û A ®¯ T )*tµ ^RHk U]1lm A í LFBGv;Yg kOag 49/B GJ9í ¡

(36) ^ d U]@;> í < 3<g1h T`Ù 5Yó èé

(37) e "O; [YÕx² A æ4É1F6d GJi Maekawa. [9] Maekawa. Pi req. Step1:. •. Q. Q. Step1. •. 1. Q. Step3 Q. Step1. R. req. req. [3]. Pj. Step2: req. Pi. Pj. locked. Pk. • Pi. Pk. : Pj. Pi. Pk. Pj. Pk. Pk. • Pk. Step3: Pi. Lamport. req. req. Pk. req. Pi. req. Pj Pj. Pi. locked. Pj. Pi. C. locked. Pi. Q. locked. Pj. Pi. Pj. Q. release. Step1. C. Step4: Pi. Q. release. Pj locked. release. Step1. Q. R. Step3. C. R:. Q. C:. locked. GENERAL. 4.3. R. C. locked. 4. l mon p

(38) q rtsvuxwzy { m|}u ~11

(39) MhQ1??P5??=&?Q=?? ¡9¢

(40) £ −79−.

(41) Q34 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. (a). 23. 24. Q34. Q r3 4={11,12,13,15}. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Q r4 1={17,18,19,20}. 11. 12. 13. 14. 15. Q c4 1={1,6,11,21}. 16. 17. 21. 22. Q c3 4={4,9,19,24}. Q41. 25. ¤9¥¦3§©¨ ª«a¬. Q r3 4={11,12,13,15} Q c3 4={4,9,19} Q r5 2={21,18,19,20} Q c5 2={2,7,12,17}. 18. 19. 20 Q52. 9¤ ¥¦3§©¨ ª«a¬ 1:

(42) Mh1®=¯. 25. (b). 22. ° 1:

(43) Mh1®5±#²³Óµ¶a·5¸3¹?º»Q·¼9· MhQ½=¾P³ ³Óµ¶a· (N ) ²¿»Q· (N ) G¼9· (N ) ®QÀMÁ º3ÅQ· x 5¸ÆÇ N = x, N = dN/xe Grid (x − 1) < N ≤ x ÂOÃÄ º3ÅQ· x 5¸Æ© N = x, N = dN/xe Grid2 2(x − 1) < N ≤ 2x ÂOÃÄ º3ÅQ· x 5¸Æ© N = x, N = dN/xe Grid4 4(x − 1) < N ≤ 4x ÂOÃÄ º3ÅQ· x 5¸Æ© N = x, N = dN/xe Grid8 8(x − 1) < N ≤ 8x ÂOÃÄ r. 2. c. 2. r. 2. 2. 2. 2. 2. 2. c. r. c. r. c. r. c. ÈÊÉ&ËÍÌ=ÎÏÐÑ Ò Ó ~1Ô=Õ×Ö ÇM1®=ØQÙ=P? ¡?¢

(44) O£GÚPÛ P =Ü9º³´Mµ¶QÝaÞ9ßP N » N ¼® ØPÙÆM 1

(45) h²ºC£9äå?Pæ9 P Â P (i = i/N + 1, i = i (mod N ) ) ²GçO°Pº,è²aÆ 2 àPá1âPã Â ²;º£3éPê® s , s (1 ≤ s ≤ N , 1 ≤ s ≤ N ) 5¸ÆÇ 1Mh Q P = {P |1 ≤ i ≤ N , 1 ≤ i ≤ N } C ® P ì í 1 î ® ð ï # » ; ² 9 ñ í 1 î # ® ïò¼®1³Óµ¶9óõô¿ÙõÇÚ?Û Q = {P |i = s ∨ i = s } ²ö÷P£ ÂøÆMë à9 9á3=âQÚPãÛQù ºO£&è®²=üG?ý&ôóMÚPÛ Q æ1³Ćµ¶· Q = {Q |1 ≤ s ≤ N , 1 ≤ s ≤ N } Â=úPû 7 ® O

(46) ½ M ² 3 £ 1 ~ Ô = 3 þ ? ÿ

(47) º P9® ?P

(48) = O Â ý=º N = N ×N ( 1(a)) 5¸ÆÇ ®CìPíî1®5»h ®

(49) Ò a³Óµ¶Q®CÚ?Û ²QÆÇ Q ñ1íhî1®=¼® ë à9

(50) á3ÒâQ ã a³´Mµ¶Q®CÚPÛ Â Q (= {P |i 6= s ∧ iÂ =Q s })(=²{Pö9º|i=£1»#s ²j∧ ¼hi ®6=s &})²C ³Óµ¶ P æ Q ² Q ® hôMç

(51) Ò £ 9=³´µP¶C·Ý5Å1·® Qa GÛæ N ä P® â9ã Â ë à1áGâ3ã Â Ø3ÙÆ" !$#®M» %ü Â & 7 3!ïð'» ®1³ÓµP¶9 !(#®5»h® %hü Â ) Ö ( 1(b))£ Ò Ä *+®P

(52) a M Â Õ Ö-, .QæM3® /G¾P Â !$0hCº Ä ÷3 N = N ²QÆÇ 2 à9á3â ã Ö©2Â

(53) 1 $í 3$M²;ºh?3è®5² ± Â 4Â °~²QÆO69 3ºah£ aÝ1~1ÔPæC»Q·²j¼9· Ý 51

(54) Mç ú9û ºO£9~1Ô=Õ ä 799³Óµ¶a·$²Mh91 ½=¾P³ (2 à9á3âQã ®5»Q· N a¼9· N ) æ1=&? 8G:» 9;(<aö Ò 7 3. ça®²;ºõ£ ChG1®5Ø?Ùhæ3 FPP C9 O®MhG

(55) >² =9¢ ?ýôóP ?@' AP£ ø ® Ä ÷G B Ch32 Ý

(56) 'CP³hÓµ¶5Ú?Û FG9º?è²Ý9ü?£&è=® H$IóõôÇ?P1=&? Â 8G»ü 2 9

(57) Ö Mh Â J$K º?èÂ²ÝD L E M²M£ 4.1. r. i. i1 i2. 1. r. 2. i1 i2. c. 1. c. 1. 2. c. 2. r. 1. r. 1. r. 2. c. 2. i1 i2. s1 s2. s1 s2. c. s1 s2. 1. 1. 2. 2. c. c. r s1 s2. s1 s2. c s1 s2. s1 s2. r s1 s2. i1 i2. 1. 1. 2. i1 i2. 1. 1. 2. 2. 2. c s1 s2. r. r. c. c. ÈÊÉ&ËÍÌ=ÎÏÐÑONQPOR 3þ ÿ?º

(58) G

(59) O9P1©Q?5õQ Â ¡9¢

(60) <5þ3ÿ5&;?3® Ä ÷G® )S

(61) Â ¡9¢£ CõQ ²T5VU MþGÿ5õ9G9®2HW XY$Z [ æ\]®3³´µP¶1óô º bac(d³´µ?¶9óô locked Â^_ º

(62) QèP²Oæ2e Ó CÆ=ç fgVh £ ø èC1locked 5ä7Q®Â )^ S_ a` Ma£3º GENERAL. 4.2. −80−.

(63) æ

(64) O?½=¾P³ Â

(65) Mh1®½=¾P³²;º i3¶jQQ? 1

(66) Mh1óõôkcd³´Mµ¶ Â lmU;o np1Û® qQÞ Â º£ r(s 1 éPê®M Q Â5úut ©£vi3¶jPQcd³Óµ¶9Ýw xÆOô ` Q æy®O®M ²ç 2 (ä ® z{³ÓµP¶ Â G£|hPô2cd³ÓµP¶P1ÀÆÇ ä 7?®G Ó$ ó9Ý5Ù}UT~h t º :` Q æ yhu® O®Mh Q ²çhunQ²ç 1 ®z${³Óµ¶ Â 7 3£ Q ² Q ®Ö hu nQ²"ç \1íæ cd³Óµ¶ Â

(67) ÒaÓ P ç cd³Óµ¶9?æ9£ • Q ² Q ®Ö \1íæ c(d³Óµ¶ Â

(68) ÒaÓ y?íæ cd³ÓµP¶9??³Óµ¶ Â

(69) 'CG£ • Q ý » ¼®P OGóô¿Ù iG¶ jP1=QQ Ç£ ® 1Û ²M ( Q ) N® z${?N³ÓµP¶?æ P ∈ Q ² P ∈ Q ® 2 úuA?t £ s7 G6= t Q, s 6= Ò t Ä æ Q Q® \3í®MÚ?Û CÜ9ºOºQ¢ Q®1³Óµ¶ Â Q óõô lU;1? ç5 Q ² Q ® z${³´µ¶?2æ wx?º£ Ò Ä s 6= t , s = t ®2Û Q ²O Q ®z {P³´©µ?¶Qæ P , ..., P (i 6= s ), ..., P ∈ Q ® N − 1 ² P A?©£ 7 3 Q CÜ3º

(70) ºQ¢P 9®G³ÓµP¶3 Ò Ä æ Q ®Mé?ê® $]ÚQÛCÜ3º ºQ¢ Q®1³Óµ¶² P Â Q óõôlU;3? ç5 Q ² Q ®z${³Óµ¶?æ2w x?º£ ® 1Ûõç

(71)

(72) Æ© z${³Óµ¶?æ5 Ù ~Gº£ s = t , s 6= t 2 a Ý Ù O T U 3 ~ è²u U ä 7 Â ö 9º£ )S 1 1 a Oa Q óô c$d³´µP¶1®MÚQÛ P CÜ3º

(73) =³´µ?¶ Â lmUjG Ä ²jº

(74) Ç£

(75) èM®

(76) ²Cüa P Ý ä 7?®G $Ó ó ÂÃÄ º$²5üMh Q 2æ AP²Ç#Ö £ s1 s2. s1 s2. t1 t2. s1 s2. t1 t2. r s1 s2. c s1 s2. r s1 s2. c s1 s2. r. s1 s2. c. 1. t1 t2. r s1 s2. s 1 t2. t1 s 2. s1 s2. 1. 1. c. 2. 1. 2. 2 r s1 s2. s1 s2. 2. c s1 s2. t1 t2. t1 t2. is2. 1s2. c s1 s2. s1 s2. s1 s2. 1. s1 s2. s1 s2. 2. 1. c s1 s2. N c s2. 1. c s1 s2. c s1 s2. s1 ,s2. s1 ,s2. t1 ,s2. 2. s1 s2. F. F. s1 s2. • Qrs1 s2 ∩ PF = ∅ • Qcs1 s2 ∩ PF = ∅. ∧ ∧. (Qcs1 s2 ∪ {Ps1 s2 }) 6⊆ PF (Qrs1 s2 ∪ {Ps1 s2 }) 6⊆ PF. ³´µ?¶9Ý A?QO ÆÇ 95õQ 8»ÆÇ G²Müa ®onPóQ®3³´µP¶1Ýc$d ³Óµ¶11 Q Ý39Q&²"Â b1Jó(K Ä ²;º

(77) £è=®

(78) ²5Â ücdP³ÓµP¶Q®MÚ?Q ÛPuU Q ä®Oh ® óõôÇ 1 APQ

(79) ÖOh ÂJ$K ü?1ÛÝ AP£. r(s 2 é?ê®P= h Q ² c$d³´ÇµP¶9®MÚ1Û P ÂCú:t ©£ Ä Æ Q ² P 3æ Ä ï ®z {?³´µ?¶1 Ý w x#ÆÇ P æ P

(80) 2Ò ²jº

(81) £è5®

(82) ²CüG® Ä ï 2® z${P³´µP¶ Â P ²¿º

(83) ©£9 Ò

(84) Ò a³ÓµP¶ Â Oha Q óõô lmU;3 Ä ²5ü= Q Ý 3 AP Ä ÷G®Z [æ Q Ý ∩P Q c(d³Óµ¶9?Q³Óµ¶ Â hunQ²aç 1

(85) Cè² AP£ ý ) N » N ¼®

(86) a M3óô¿Ù i3¶ jPQ=Q? úvt £Q Ò Q ®1³ÓµP¶Q®,Ö P ∈ ( "Ý cdQ³?´µ3¶²ÆjPC Q Ý 9GC² º£ à C Q Â©aú t ;£ Q = {P , ..., P (i 6= Q (t 6= s ) ®Q³´Mµ¶Pæ=ºQ¢ ³Óµ¶Q A£õ G 9 Q Ý 1' AP31æ1 Q Ý h nQ²ç 1 t), ..., P ® (³Óµ} ¶ Â

(87) ÷ ` C£ 2 )S 2 æG J$K Æ Ä Mh Q ÝG3ñ9íî1®=¼ Q c d³Óµ¶ Â 1 '

(88) aC1Û=?? ?® )Sv Ý3=ìPíî1®5» Q cd³Óµ¶ Â 1 '

(89) 'C1Û=Q? çh® )S ÝaÙ}UT~33£ r(s 3 é?ê®P= h Q ² c$d³´ÇµP¶9®MÚ1Û P ÂCú:t ©£ Ä Æ Q ² P 3æ Ä ï ®z {?³´µ?¶1 Ý w x#ÆÇ P æ P

(90) 2Ò ²jº

(91) £è5®

(92) ²CüG® Ä ï 2® z${P³´µP¶ Â P ²¿º

(93) ©£9 Ò

(94) Ò a³ÓµP¶ Â Oha Q óõô lmU;3 Ä ²5ü= Q Ý 3 AP Ä ÷G® Z [æ Q Ý Q ∩P c(d³Óµ¶9?Q³Óµ¶ Â hunQ²aç 1

(95) Cè² AP£ 2 ä u U Æ ChG ®ñ9íî9®=¼ Ò æCìPíî9®5»®

(96) ô©óP® cd³Óµ¶9Ý ô ` a Q JÝK 3PÄ Q GÛQçC à 2PP 3Ä a "Â JK º

(97) 1èP²©Ý1Pü9Ç£hè1èCG1³ ´µ?¶3Ý c(d³ÓµP¶3 A? P ²;º²Ç Ý ® c(d³´µ¶

(98) C 1ÛOh Ý 1 APæ 1 − π Â Qπ Ý Ä 1Q ®cdÄ ³ Ó1 µP ¶ P Â

(99) 'C1PÛOÂ h Q Ý3 QAP?æ A?Ç£a~3Ô ú1û º

(100) Qæ N ( A?©£ = 3 1 ® c(d³´©µP¶ P 1−π

(101) Â 'CG¼² 1 ®cd³Óµ¶ P Grid2,

(102) Â 'CGrid4, »Ýw Grid8 x?º 1Ûhæ5N¼ <Â ÆÇ à æ Q Â J$K ºQça®²;º£ 2. s1 s2. s1 s2. s1 s2. s1 s2. s1 s2. s1 s2. s1 s2. c s1 s2. F. t1 s 2. F. t1 s 2. r. r t1 s 2. t1 s 2. c. c s1 s2. F. F. s1 s2. s1 s2. 1. ts2. us2. N c s2. ts2. c ts2 r us2. 1s2. is2. c s1 s2. s1 s2. r s1 s2. s1 s2. s1 s2. s1 s2. r s1 s2. F. F. F. s 1 t2. F. s 1 t2. c s 1 t2. s 1 t2. s1 s2. s1 s2. r s1 s2. Nc −1. t1 s 2. c s1 s2. t1 s 2. s 1 t2. Nr −1. s 1 t2. r. s 1 t2. c. t1 s 2. t1 s 2. −81−.

(103) È É&ËÍÌ=ÎÏÐÑQ/É#Ñ Ê ¡Q¢ ?PPP

(104) Mh1=&? þ1ÿ?º£3þ1ÿh=&?9æ ¡14.2 ¢ Ä CõÄ2Q) SÂ Â4 4 ~$²9Æ JK$ ¡ R ²THWXY$Z [ C Â ä 7Q®Â hÖ¢(£ºÇ£1äQå1èC®15&3.29 Â ¤¥u¦u§p¨© GRID ² ª«£ APMhG Æ Qa&? 83»Æ 3²5üG ¬ JK( ¡ R: H$W Â ef²º³Óµ¶ P æ3 M' ¿µQ ® Â^ _ ºh=2ó ¯ó?Qv U Q CÜ1º

(105) B ³´Qµ?Â ¶3J$Ý K c(dP³´©µP¶32ó $PÂ ³´µP¶3ó3$Ý b3ó£ ø èM3 ® B ³´µP¶1Ý ³´µP¶12ó c$d³ÓµP¶1ó 6°$Æ© on £ b3ó " $³Óµ?¶3 c(dP³ Óµ¶QQ® ±² Â 4 J$K Æ Ä Mh Q ?u n; Â yh®MQ5¸Æ© "ç 1oó Ö;ó Â (³?º

(106) £ Ý 1?u n Step1 2 ´: Ä ²5üG ä 7P® 1 óõô 3 ® µ ¶ 1 Ò 1? J$K Æ© 3 Ä Mh Q T² ·PöÆ©

(107) Mh1' ® aóõôÇ à J$K ºQMh Â ¸ ö3º©£ cd³´Mµ¶9Ý 1 2 y®1³Ćµ¶9Ýº?¢ ³´Mµ¶9' AP¼hÝ wx?ºô ` ø ®

(108) Ö c d 1. ³´µ¶Q®#ï P 5¸Æ© Q Â J$K º£ cd³´Mµ¶9Ý 1 2 y®1³Ćµ¶9Ýº?¢ ³´Mµ¶9' AP©»Ý wx?ºô ` ø ®

(109) Ö c d 2. ³´µ¶Q®#ï P 5¸Æ© Q Â J$K º£ ø ä ®CéPê®Mh Â J$K º£ 3. 2 HW$X$Y(Z[ C: ³Óµ¶ P Ý HW Â e(f²?Æ© 3h²QÆÇ P Ý locked Â ^_ Æ Ä ³Óµ¶Q®CÚ?Û Â P P Ý c$d³´µP¶² ¹ h=³´µ¶9®MÚ?Û Â P ²jº

(110) ©£Q Ò P ÝOh Q Â JK ÆÇ 9=õ9 Ù U~ P Ýaaä 7?®G $Ó óQ® Z[ ÂOÃhÄ ºô ` P æ Â 8G»Æ© 1h²;º²© P ∪ P ⊇ Q Ýa} HW Â X$Yü?£. 4.3. i. t1 t2. t1 t2. t1 t2. t1 t2. i. i. l. f. l. • Qrs1 s2 ∩ Pf = ∅. • Qcs1 s2 ∩ Pf = ∅. 5. ∧ ∧. f. i. s1 s2. i. s1 s2. f. i. (Qcs1 s2 ∪ {Ps1 s2 }) 6⊆ Pf. (Qrs1 s2 ∪ {Ps1 s2 }) 6⊆ Pf. 2. º¼». ~31CþGÿhCõQ1®C½ Â ¾¿ º Ä ÷1O»v Ä 8À®Á½ Â Â ºa£ÃaÄ9®8ÀPQæ Ò Ä æ 500 ®1o¶ Ê1 Â ³Óµ¶²QÆ© 2 & hpË iÌÍ:Ê'iVÎÏ Â »Ð Ä £ 150 . 1. ® Æ3¶ÈÇÉ Å . Ñ|ÒÓNoÔ}Õ Æ3¶ÇÖQ & º"×³´µP¶9®õÖa9ÏØ39 JK Æ Ä 1 ³´©µP¶9® 9ÝHW Â fg,Æy®3³´µQ¶Qæ ø ® HWh®f$h g 5¸9ºõ"Ù'L® Â »Ö £ B M1®¶ÈÇ æÆ1¶ÓÇÚ(AVU HW Â f$g1ºa³´Mµ¶?æ ø ®&Ç¶ Ç 3 C Û µ?¶Æ© Oh1® JK req µQ 1 ® ®2Ü _ Â » Öð£è5®²Müa95&? GENERAL ²¿þ3ÿ PA =&? GRID Â Ý GÞ Â 0 óõô 0.2 Ò 0.025 ß 2¢ àáhpË 100 Ä Ó (8G»ÆÇHW Â f$g1º ³´µ?¶9ÝHW Â X9Y º

(111) Ò 1®C¹$â'ã(3ä ®åæç Â =$è Æ Ä £PCQ GENERAL æOÁQ·PPO/G¾ 9®0éh FPP OhaQPuU8 »Æ Ä (ä 97 è=®1=õ9 Â FPP ²16 º )£ Ò Ä 3=&Q GRID æ 9½5¾?³ Â Grid, Grid2, Grid4,Grid8 ²9ÆÇ 8 »Æ Ä (ä17 è ô®15õ;Q Â ø ê Grid, Grid2, ²>Q6 º £³h´Mµ¶a· ø aê FPP, Grid, Grid2, Grid4, Grid8 Â G8 »!Æ Ä ²=üG®hM

(112) Grid4, Grid8 1/ ¾PP=?? a° )5.1 96 ºa£ 150, 500. 5.1. ë}ì. ³ ´Mµ¶a· 150,500 ø 'ê ®1Û?=&©? Â 83»Æ Ä ²=üG®5¹(âãä Â 2 Â ÆÇc(d³Óµ¶QÝ? Ý ÞG 0 ®1Û$²p=èÆÇ Q®5¹(âaã(äí î Â 3 Â ºa£Q1³Óµ¶=· 500 ®1Û® FPP ² Grid æ=º1¢ 9®Mh ÂJK Æ© ç"HW Â X$Yü3ï?¶9Ý 10%ä$P A$ Ä1Ä ÷#Æ Ä £Ý ÞGÝ 0 ®1ÛhæV ®Ch3?=& Â J$K Æ© ç Ý'ÞQ³Óµ¶QÝ2

(113) Ò Ä ÷2ð J$K ®efæ9un=¹(âãäQæM. 5.2. −82−.

(114) ° FPP Grid Grid2 Grid4 Grid8. ³ Óµ¶a· 150, 500 ®21Û®Mh/1¾Q ³´µ¶a· ®GÛ® ³Óµ¶a· ®1Û® Oh /1¾P150(»?· , ¼9· ) Mh/1¾P500(»Q· , ¼1· 14 24 » ¼ » ¼ 24 (13 12 ) 44 (23 22 ) » ¼ » ¼ 25 (9 17 ) 47 (32 16 ) » ¼ » ¼ 28 (7 22 ) 53 (12 42 ) » ¼ » ¼ 34 (5 30 ) 70 (8 63 ) 2:. ). /3¾P2=3¯QºPè²C1£'\Gí Ý ÞGÝ ñ9ºG*uG 1 J$K Æ Ä Ch3Ý2cd³Óµ¶ Â

(115) 'CÝ oC n ÷9M ð º e$f Ý ò|Çó a¹(âaãGä ÝIánC£ OhÄ3ô ®2× ³´µ?¶9Â Ý2$J$ K ³´µ?¶1PA QèP²ÇÝfgVh FPP æOha/3¾PQæ0Vh©GÝôTÝ Þ ®íî ®õ$ö Â÷ ün ^: GÇ£3\ í?"c(Pd ³´©µP¶ Â

(116) a1ø QGç3GÛÝA? B a h© Q9=&?3?æG Ý ?Þ ®õhö æ=è 0Qh(Cn G Gh£ ø ®Á½ Q³Óµ¶a· 100 ®1 Û?æÝ Þ 0.1 ä(? ?³´Mµ¶· 500 ®1 ÛæÝ 3Þ 0.05 ä(P 9VO ® ®9&Ç?ç FPP vU ¹(âã1ä Ýù Mn (G 3h£ Ä$ ÆÇ ®P½=¾P³G ç= Ý3Þ ®õö Gó?éUú Ý3û 3hO£³´Mµ¶a· 150 ® Û?æ

(117) ®M ®P½=¾P³9 A$G çÇ¹(âaã9ä ®ú æ(A Ò Uýü ô 3ó' Ä ®?5¸Æ©Q³´Mµ¶a· 500 ®1 Ûhæ G ®P½a¾P³P1 ú Ý9ó?QU ÷ ü:Cn (G 3h£&è æG

(118) 1® 2 à9á3â?ã ®5»Q·Ýh :` ¼c d ³Óµ¶ Â

(119) 'CP Ý0Qh(Cn Ä ÷ J$K Æ Ä MhÝ1 1éU9þ º?

(120) è²C1£. ÿ. 3~ ÔQæc(d³´©µ¶

(121) C i¶jP9 5O9?1©Q?5QQ5?Q Æ £ PM35QÂ GENERAL QæO a9CÜ1º

(122) ©º9¢P 9®3³ÓµP¶1óôýH W®Ù L Â Y ú9 û ` Ä ôG Ä ÷énM®cd³Óµ¶ Â

(123) C

(124)

(125) Ö$i3¶j3?æ5?'n> & ÆO£ \3í~1Ôaþ1ÿÆ Ä =& Q GRID ?æGhMha

(126) ²QÆ© Mh Â

(127) º

(128) ?è²GVnM®cd³Óµ¶ Â

(129) 'C

(130)

(131) Ö$i3¶j? ~1tç©QÔô aþ1 ÿ#£ n Æ & º5&©£ H9 2 à1áGâ9?ã æG®5h»1M·hÝ21® hð OGºQæ²5ü1c$d1³hÓµPO¶9h® òP®õ(ö ºÂ ó?QVè²CU 0é h n JK

(132) Â Â J$K Ä Â Ö9?Mh 3h£#Æ©«óõèÆÇa²¹$ç©âa$ ½ãäaÝ GRID ÂAP0Qh(² 'nºb Ä £÷93Ò æGM

(133) h ð MJ$hK #h9æÜ M_ hºMÚ?reqÛ hAP µ??'M® ½Â ý ×ôjº Â J Ä Â ðØ?ÙQº?è²Ý=$è D(E A Ä ÷ ðGØQÙÐU1hMhG Â ØQÙQºç u ú t ô £ ø è51~ Ôaþ1ÿÆ Ä ²è ô® ²O®5$¹ âaãä9® =èÐ Ý Ã(#® S ²QÆ© ô £. 6. ! 7+~8 ,' .Ä Â#Æ " Ò 9;:=<?>. ÷?G$A ºa£ Ä. %$&QÞP U. Ä ü Ò Æ Ä ÷('÷!)$÷!)+*. , ) ,'.-, !í .-/(0!1234!5 à-6 -1 2. ±². [1] T. Ibaraki and T. Kameda. A theory of coteries: Mutual exclusion in distributed systems. IEEE Trans. Prallel and Distributed Systems, Vol. 4, No. 7, pp. 779–794, 1993. [2] H. Kakugawa, S. Fujita, M. Yamashita, and T. Ae. A distributed k-mutual exclusion algorithm using kcoterie. Information Processing Letters, Vol. 49, No. 2, pp. 213–218, 1994. [3] L. Lamport. Time, clocks and ordering of events in a distributed system. Communication of ACM, Vol. 21, No. 7, pp. 558–564, 1978. −83−.

(134) TT MNKOMPMPMM m l SSR MNKOKOMPMPMPMMM hij k RIQMNKOMPMPMM ILMNKOMPMPMM M. @BADCFEHGJILKNM. xzyD{F|~}OP. L PPNN rttrnpoqsasauu ovvPR L P PPPNNN trtr sasauu vNvPTw PN PPNN. W W W ZWJW Z]W ZWW aWW bWJW b]W bWW ]W eg. UWV UW UXUWV UZYW[\UWV UZ[]UÛWV UZ_W[XceUWdgV àUWXf UWV `bYW[XUWV `b[]UXUWV `b_W[\UWV Y]UW . ¢z£¥¤~¦H§¨ª©N«. ÃÁÂ ±²° ©¯ ® ¾¿½À ¬ «¨ ³W´ ³W ³µ³W´ ³Z¶W·µ³W´ ³Z·]³µ³W´ ³Z¸W·µ³W´ ¹a³Wµ³W´ ¹b¶W·X³W´ ¹b·]³³W´ ¹b¸W·^³W´ ¶]³W º%»e¼. ¹(â'ãä. 2:. ËzÌDÍFÎ~ÏÐOÑPÑ. ÇÇÄÆÅÈbÈbÉÉ ÅÊÊP¬ ÇÇÈbÈbÉÉ ÊNÊP®± . 3:. paa ¡¡N aa ¡O¡N . æäå. áâàã. ÖQÖ Õ ÖLÖ ÓÔ Ö ÑÒÕ ÓÔ ÑÒ ×WØ ×W ×e×WØ ×ZÙWÚ×WØ ×ZÚ]×e×WØ ×ZÛWÚ×WØ Üa×]%×WØ ÜbÙWÚe×WØ ÜbÚ]×%×WØ ÜbÛWÚe×WØ Ù]×W ÝeÞgß. ééçpèqêaêaëë èìì ééêaêaëë ìOìNÓÒÕ. ¹(âaãä2í î. [4] S.D. Lang and L.J. Mao. A torus quorum protocol for distributed mutual exclusion. In Proceedings of the 10th IASTED International Conference on Parallel and Distributed Computing and Systems,, pp. 635–638, 1998. [5] G. Le Lann. Distributed system – towards a formal approach. Information Processing ’77, pp. 155–160, 1977. [6] W.S. Luk and T.T. Wong. Two new quorum based algorithms for distributed mutual exclusion. In Proceedings of the 17th International Conference on Distributed Computer Systems, pp. 100–106, 1997. √ [7] M. Maekawa. A n algorithm for mutual exclusion in decentralized systems. ACM Transaction on Computer Systems, Vol. 3, No. 2, pp. 145–159, 1985. [8] D. Peleg and A. Wool. How to be an efficient snoop, or the probe complexity of quorum systems. SIAM Journal on Discrete Mathematics, Vol. 15, No. 3, pp. 416–433, 2002. [9] B. A. Sanders. The information structure of distributed mutual exclusion algorithms. ACM Transaction on Distributed Systems, Vol. 5, No. 3, 1987.. íïî ð!ñ ò 7 ó

(135) ô =õ? õ!ö , )-÷. [10] J. H. van Lint and R. M. Wilson. A Course in Combinatorics. Cambridge University Press, 1992. [11]. ,. .. .. , 1994.. −84−.

(136)