೔ຊιϑτ΢ΣΞՊֶձୈ 30 ճେձ (2013 ೥౓) ߨԋ࿦จूେ‫ن‬໛ͳϊʔυ‫ނ‬ো΍ωοτϫʔΫ෼அʹର͢ΔՄ༻ੑΛ࣋ͭडಈతෳ੡ख๏੢ాɹঘ࢙ɹ௕୩෦ɹߒೋɹՃ౻ɹ࿨඙ΠϯλʔωοταʔϏεͷՄ༻ੑΛ޲্ͤ͞ΔͨΊͷํ๏ͷҰͭͱͯ͠ɼडಈతෳ੡ख๏͕஌ΒΕ͍ͯΔɽ͜ͷख๏Ͱ͸ɼ͠͹͠͹ Paxos ͳͲͷա൒਺߹ҙΞϧΰϦζϜ͕༻͍ΒΕ͖ͯͨɽ͜͏ͨ͠ख๏Λ‫ͨ͠ʹج‬෼ࢄγεςϜͰ͸ɼαʔϏεͷҰ؏ੑ͕อূ͞ΕΔҰํͰɼա൒਺ͷϊʔυͷಉ࣌‫ނ‬ো΍ωοτϫʔΫ෼அͳͲͱ͍ͬͨେ‫ن‬໛ͳো֐ൃੜ࣌ʹɼαʔϏεશମ͕ఀࢭͯ͠͠·͏ͱ͍͏੍໿͕ੜ͡Δɽͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼ‫ͳ֨ݫ‬Ұ؏ੑΛඞཁͱ͠ͳ͍Web ‫ࣔܝ‬൘ͳͲͷαʔϏεΛର৅ʹɼେ‫ن‬໛ͳো֐ʹରͯ͠΋αʔϏεͷ‫ܧ‬ଓΛՄೳʹ͢Δडಈతෳ੡ͷͨΊͷΞϧΰϦζϜΛఏҊ͢Δɽ͞Βʹɼ͜ͷΞϧΰϦζϜΛ‫ʹج‬ɼෳ਺ͷαʔϏεΛఏ‫͢ڙ‬ΔͨΊͷ޿Ҭ෼ࢄγεςϜΛఏҊ͢Δɽ͜ͷγεςϜͰ͸ɼ֤αʔϏεͷෳ੡͕ߦΘΕΔͱͱ΋ʹɼϊʔυؒͷࣗ཯తͳ‫ڠ‬ௐಈ࡞ʹΑΓɼෛՙ෼ࢄ΍ɼෛՙͷू໿ʹΑΔলిྗԽ͕࣮‫͞ݱ‬ΕΔɽϓϥΠϚϦϊʔυʹؔ͢Δ߹ҙͰ͋Δɽ͢ͳΘͪɼϓ

1 ͸͡ΊʹϥΠϚϦ͕‫ނ‬োͨ͠ࡍʹɼͲͷόοΫΞοϓϊʔυ͕Web ‫ࣔܝ‬൘ͳͲͷΠϯλʔωοταʔϏεΛఏ‫ڙ‬୅ସ͢Δͷ͔ʹ͍ͭͯͷ৘ใΛશͯͷϊʔυͰҰக͢ΔγεςϜʹ͸ɼՄ༻ੑ΍Ԡ౴ੑ͋Δ͍͸ӡ༻ίͤ͞ͳ͚Ε͹ͳΒͳ͍ͱ͍͏໰୊Ͱ͋Δɽ͜ͷ߹ҙετͷ࡟‫ٻ͕Ͳͳݮ‬ΊΒΕ͍ͯΔɽͱΓΘ͚ɼ‫ܧ‬ଓ͠໰୊͕ղܾͰ͖ͳ͍ͱɼϓϥΠϚϦ͕‫ނ‬োͨ͠ࡍʹɼͯఏ‫͚ͳ͠ڙ‬Ε͹ͳΒͳ͍αʔϏεʹରͯ͠͸ɼߴෳ਺ͷϊʔυ͕ϓϥΠϚϦͷ୅ସʹͳΖ͏ͱ͢Δ͍ͨՄ༻ੑ͕‫ٻ‬ΊΒΕΔɽ͜͏ͨ͠γεςϜͷՄ༻ੑΊɼਖ਼͘͠αʔϏεΛ‫ܧ‬ଓ͢Δ͜ͱ͕Ͱ͖ͳ͍ɽ͜͏ΛߴΊΔํ๏ͷҰͭͱͯ͠ɼडಈతෳ੡ख๏ [2] ͕஌ͨ͠߹ҙ໰୊Λղܾ͢ΔͨΊͷ෼ࢄΞϧΰϦζϜ͸ɼΒΕ͍ͯΔɽ͜ͷख๏͸ɼ͋ΔαʔϏεΛఏ‫͢ڙ‬Δͨ߹ҙΞϧΰϦζϜͱ‫ݺ‬͹Εɼͦͷ୅දతͳ΋ͷͱ͠Ίʹɼෳ਺ͷϊʔυʢಠཱͨ͠‫ػࢉܭ‬ʣΛ༻͍ͯαʔͯ Paxos [5] ͕Α͘஌ΒΕ͍ͯΔɽPaxos ͷ‫ج‬ຊతͳόͷ৑௕ԽΛߦ͏΋ͷͰ͋ΔɽΑΓ۩ମతʹ͸ɼϓϥΞΠσΞ͸ɼ֤ϊʔυ͔Β߹ҙ஋ͷީิͱͯ͠ఏҊ͞ΠϚϦϊʔυͱ‫ݺ‬͹ΕΔ 1 ୆ͷ‫͕ػࢉܭ‬ΫϥΠΞϯΕͨ஋ͷ͏ͪɼա൒਺ͷϊʔυ͔Βडཧ͞Εͨ஋Λτ͔ΒͷϦΫΤετΛॲཧ͠ɼ·࣮ͨߦ‫ޙ‬ͷ݁ՌΛ࠷ऴతͳ߹ҙ஋ͱ͢Δͱ͍͏΋ͷͰ͋ΔɽͦͷͨΊɼόοΫΞοϓϊʔυͱ‫ݺ‬͹ΕΔʢҰൠʹෳ਺ͷʣ‫ࢉܭ‬Paxos ͷΑ͏ͳա൒਺߹ҙʹΑΔΞϧΰϦζϜΛ༻‫ૹʹػ‬৴ͯ͠ϓϥΠϚϦϊʔυͱಉ͡ঢ়ଶʹอ͍ͭͯ͜डಈతෳ੡Λ࣮‫͢ݱ‬Δ৔߹ɼա൒਺ͷϊʔυ͕‫ނ‬ͱͰෳ੡Λߦ͏ख๏Ͱ͋Δɽ͜ΕʹΑΓɼϓϥΠϚϦোΛ͠ͳ͍ͱ͍͏લఏ͕ඞཁͱͳΔɽҎ্ͷ͜ͱ͔ϊʔυ͕‫ނ‬োͯ͠΋ɼόοΫΞοϓϊʔυͷҰ͕ͭϓΒɼա൒਺ͷϊʔυͷ‫ނ‬োͱ͍ͬͨେ‫ن‬໛ͳো֐ʹରϥΠϚϦͱͳͬͯαʔϏεΛ‫ܧ‬ଓ͠ଓ͚Δ͜ͱ͕Ͱͯ͠΋αʔϏεΛ‫ܧ‬ଓͤ͞ΔͨΊʹ͸ɼա൒਺߹ҙʹ͖Δɽ͜ͷख๏Λ࣮‫͢ݱ‬Δ্Ͱ࠷΋ॏཁͱͳΔͷ͕ɼΑΒͳ͍ෳ੡ख๏Λߟ͑ͳ͚Ε͹ͳΒͳ͍ɽ

Passive replication technique with availability to network partitions and large scale node failure.
Naofumi Nishita, Koji Hasebe, Kazuhiko Kato, ஜ೾େֶγεςϜ৘ใ޻ֶ‫ڀݚ‬Պ, Dept. of Systems and Information Engineering, The University of Tsukuba.

·ͨɼडಈతෳ੡ख๏ʹΑΔՄ༻ੑͷ޲্ΛਤΔͨΊͷํ๏ͱͯ͠ɼҰൠʹόοΫΞοϓϊʔυͷҰ෦Λԕִ஍ʹஔ͘͜ͱ͕ߟ͑ΒΕΔɽ͔͠͠ͳ͕Βɼ޿ҬʹόοΫΞοϓΛ഑ஔ͢ΔͱɼωοτϫʔΫ෼அͳͲͷ௨৴ো֐ͷӨ‫ڹ‬Λड͚΍͘͢ͳΔͱ͍͏໰୊͕ੜ͡Δɽडಈతෳ੡ʹ͓͍ͯɼ͜͏ͨ͠ωοτϫʔΫ෼2 ઌߦ‫ڀݚ‬அ͕ੜ͡Δͱɼա൒਺ͷϊʔυͷ‫ނ‬োͱಉ༷ʹɼαʔ͜Ε·ͰఏҊ͞Ε͖ͯͨෳ੡ख๏͸ɼओʹɼೳಈతϏεͷ‫ܧ‬ଓ͕೉͘͠ͳΔͨΊɼωοτϫʔΫ෼அ଱ੑෳ੡ख๏ [7] ͱɼຊ‫͍༻Ͱڀݚ‬ΒΕΔडಈతෳ੡ख๏ʹ͍ͭͯ΋ߟྀ͢Δඞཁ͕͋Δɽ

[2] ͷ̎ͭʹ෼ྨ͞ΕΔɽҎ্ͷ໰୊ʹର͠ɼຊ‫Ͱڀݚ‬͸ɼա൒਺ͷϊʔυ‫ނ‬ೳಈతෳ੡ख๏͸ɼෳ਺ͷαʔό͕ɼΫϥΠΞϯτো΍ωοτϫʔΫ෼அͱ͍ͬͨେ‫ن‬໛ͳো֐͕ൃੜ͔͠Βͷ֤ϦΫΤετʹରͯͦ͠ΕͧΕಉҰͷॲཧΛͯ΋αʔϏεΛ‫ܧ‬ଓ͢ΔͨΊͷ޿Ҭ෼ࢄγεςϜΛఏߦ͏͜ͱʹΑΓɼϊʔυؒͰৗʹαʔϏεͷঢ়ଶΛҰҊ͢Δɽ͜ͷγεςϜͷΞϧΰϦζϜΛఏҊ͢Δࡍɼ

கͤ͞Δͱ͍͏΋ͷͰ͋Δɽ͜ͷख๏͸ɼ‫ޙ‬ड़ͷडಈ

Paxos Λͦͷ··ར༻͢ΔͱɼαʔϏεͷ੔߹ੑ͸తෳ੡ख๏ʹൺ΂Ԡ౴͕࣌ؒ୹͍ͱ͍͏ར఺͕͋ΔอͨΕΔ΋ͷͷɼա൒਺ͷϊʔυ͕‫ނ‬োͨ͠ঢ়‫Ͱگ‬΋ͷͷɼߴ͍‫ٻ͕ݯࢿࢉܭ‬ΊΒΕΔ͜ͱͱɼඇܾఆత͸αʔϏεΛ‫ܧ‬ଓ͢Δ͜ͱ͕Ͱ͖ͳ͍Մೳੑ͕͋ΔɽͳॲཧΛߦ͏αʔϏεʹରԠͰ͖ͳ͍ͱ͍͏໰୊͕ͦ͜Ͱຊ‫Ͱڀݚ‬͸ɼ੔߹ੑΛ٘ਜ਼ʹ͢Δ୅ΘΓʹɼγ͋Δ͜ͱ͕஌ΒΕ͍ͯΔɽҰํɼઌʹઆ໌͍ͯͨ͠डεςϜͷՄ༻ੑΛߴΊΔͨΊʹɼPaxos ʹ͓͚Δաಈతෳ੡ख๏͸ɼ‫ݯࢿࢉܭ‬ͷ࢖༻͞ΕΔྔ͸গͳ͘ɼ൒਺ʹΑΔఏҊ஋ͷडཧͱ͍͏৚݅Λ؇࿨͢Δͱ͍֤ϊʔυͷಈ࡞͸ܾఆతͰͳͯ͘΋ྑ͍ɽ͔͠͠ɼϓ͏ΞϓϩʔνΛ࠾༻͢Δɽ͜ΕʹΑΓɼ߹ҙ஋ͷ੔߹ϥΠϚϦϊʔυ͕‫ނ‬োͨ͠৔߹ͷରԠ͸༰қͰͳ͘ɼੑΛ٘ਜ਼ʹ͢Δ୅ΘΓʹɼա൒਺ͷϊʔυ͕‫ނ‬োͨ͠Ͳͷϊʔυ͕࣍ͷϓϥΠϚϦͱͳΔͷ͔ʹ͍ͭͯ߹৔߹Ͱ΋ɼ࢒ΓͷϊʔυʹΑͬͯ߹ҙ͕औΓଓ͚ΒΕҙΛ‫ܗ‬੒͠ͳ͚Ε͹ͳΒͳ͍ɽ·ͨɼPaxos ͳͲͷաΔͨΊɼ݁Ռͱͯ͠αʔϏεΛ‫ܧ‬ଓͰ͖Δෳ੡ख๏൒਺߹ҙΛ‫߹ͨ͠ʹج‬ҙΞϧΰϦζϜͰ͸ɼա൒਺ͷΛఏҊ͢Δɽ·ͨɼলిྗͷ‫͔఺؍‬ΒɼΦʔόʔϩʔϊʔυ͕‫ނ‬ো͢Δͱ߹ҙ‫ܗ‬੒Ͱ͖ͳ͍ɽυ͠ͳ͍ൣғͰҰ෦ͷϊʔυʹෛՙΛूதͤ͞Δ [1]ɽ·ͨɼ͜ͷ̎ͭͷෳ੡ख๏ͷதؒͷଘࡏͱͯ͠ɼ४ͦͯ͠ɼҎ্ͷ͜ͱ͔ΒɼຊఏҊख๏͸ɼۜߦͷΦϯೳಈతෳ੡ख๏ [8] ΍४डಈతෳ੡ख๏ [3] ͳͲͷख๏ϥΠϯγεςϜͳͲͷ‫ͳີݫ‬੔߹ੑ͕‫ٻ‬ΊΒΕΔαʔ΋͋Δɽຊ‫Ͱڀݚ‬͸ɼ‫ݯࢿࢉܭ‬ͷ͜ͱ΍αʔϏεͷϏε΁ͷద༻͸೉͍͠ɽ͔͠͠ͳ͕Βɼࡂ֐࣌ͷ࿈བྷಈ࡞͕ඇܾఆతͰ͋ΔՄೳੑΛߟྀͯ͠ೳಈతෳ੡

༻ web ‫ࣔܝ‬൘ͳͲΛయ‫͢ͱྫܕ‬Δɼඞͣ͠΋‫ͳີݫ‬ख๏Ͱͳ͘डಈతෳ੡ख๏Λར༻ͯ͠γεςϜͷߏ੔߹ੑΛඞཁͱ͠ͳ͍୅ΘΓʹߴ͍Մ༻ੑ͕‫ٻ‬ΊΒΕஙΛ໨ࢦ͢ɽ·ͨɼຊ‫Ͱڀݚ‬͸ɼҎલͷ Paxos ΛडΔαʔϏεͷӡ༻ʹରͯ͠༗༻Ͱ͋Δͱߟ͑ΒΕΔɽಈతෳ੡ख๏ʹར༻ͨ͠γεςϜ [6] ͳͲͱ͸ҟͳΓɼຊߘͰ͸ɼҎ্Ͱड़΂ͨՄ༻ੑΛॏࢹͨ͠ෳ੡ख๏‫׬‬શͳ੔߹ੑ͸ຬͨͤͳ͍͕ɼΑΓߴ͍Մ༻ੑΛ࣋ͭͷΞϧΰϦζϜͱɼ͜ͷΞϧΰϦζϜʹΑͬͯ੒ΓཱγεςϜΛఏҊ͢ΔɽͭՄ༻ੑʹؔ͢Δॾੑ࣭Λࣔ͢ɽ͜ΕΒͷੑ࣭ʹ͍ͭͯ͸ɼࠓ‫ޙ‬ΞϧΰϦζϜͷϓϩτλΠϓ࣮૷Λߦͬͨ

3 ఏҊख๏ͷ֓ཁ্Ͱɼա൒਺Ҏ্ͷϊʔυͷ‫ނ‬ো΍ɼωοτϫʔΫ෼ຊ‫Ͱڀݚ‬ఏ‫͢ڙ‬ΔγεςϜͷ֓ཁΛઆ໌͢Δɽ͜ͷஅɼ͞ΒʹγεςϜ಺Ͱͷෛՙͷ૿‫ʹݮ‬ର͢Δ࣮૷‫؀‬γεςϜ͸ਤ̍ͷΑ͏ͳෳ਺ͷϊʔυ͕޿Ҭʹ഑ஔ‫ڥ‬ͷಈ࡞֬ೝʹΑͬͯ‫͢ূݕ‬Δ༧ఆͰ͋Δɽ͞Ε͍ͯΔ‫ڥ؀‬Լʹߏங͞Εɼෳ਺ͷΠϯλʔωοτҎԼɼຊߘͰ͸ɼ·ͣ̎ষͰઌߦ‫঺͍ͯͭʹڀݚ‬αʔϏεΛఏ‫͢ڙ‬ΔɽγεςϜʹ͋Δϊʔυͷू߹Λհ͢Δɽ࣍ʹఏҊख๏ͷ֓ཁʹ͍ͭͯ̏ষͰड़΂Δɽ

N = {n1 , . . . , nk } ͱ͢Δɽ·ͨਤ̍Ͱ͸ɼn1 ͳͲͷ࣍ʹ̐ষͰɼγεςϜͷΞϧΰϦζϜʹ͍ͭͯઆ໌ϊʔυ൪߸ͷԼʹ͋Δ s1 [P ] ͳͲͷ‫ه‬ड़͕ɼͦͷϊʔ͢Δɽ̑ষͰ͸γεςϜ͕ຬͨ͢΂͖ੑ࣭Λड़΂Δɽυʹ͓͍ͯ‫ى‬ಈ͍ͯ͠ΔαʔϏεͷ൪߸ͱ໾ׂΛද࠷‫̒ʹޙ‬ষͰ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ʹ͍ͭͯड़΂Δɽ

͍ͯ͠Δɽྫ͑͹ɼs1 [P ] Ͱ͋Ε͹αʔϏε̍ͷϓϥΠϚϦͰ͋Δ͜ͱΛද͓ͯ͠Γɼs2 [B] Ͱ͋Ε͹αʔϏε̎ͷόοΫΞοϓͰ͋Δ͜ͱΛද͍ͯ͠ΔɽຊγεςϜͰ͸֤αʔϏεΛडಈతෳ੡ख๏Ͱఏ

3. άϧʔϓ‫ܗ‬੒ϓϩηε
4. ϓϥΠϚϦόοΫΞοϓ௨৴ϓϩηε‫͢ڙ‬Δɽͭ·Γɼ֤αʔϏε͝ͱʹϓϥΠϚϦͱόο5. αʔϏεάϧʔϓ౷߹ϓϩηεΫΞοϓͷϊʔυׂ͕Γ౰ͯΒΕΔɽ͜ͷϓϥΠϚϦ͜͜Ͱ͸ɼ͜ΕΒͷϓϩηε͕ͲͷΑ͏ʹ‫ڠ‬ௐ͠ͱόοΫΞοϓͷϊʔυͷू߹Λάϧʔϓͱ‫ͼݺ‬ɼάͯɼୈ̏ষͰड़΂ͨγεςϜͷ‫ػ‬ೳΛ࣮‫͢ݱ‬Δͷ͔ड़ϧʔϓΛ G = {g1 , . . . , gk } ͱ͢Δɽਤ̍ʹ͓͍ͯ͸ɼ΂Δɽn1 ͕αʔϏε̍ͷϓϥΠϚϦɼn4 ͱ n5 ͕αʔϏε·ͣɼάϧʔϓ‫ܗ‬੒ϓϩηεʹΑΓɼ৽͍͠άϧʔ̍ͷόοΫΞοϓͱͳΓɼn1 ͱ n4 ͱ n5 ͕Ұͭͷάϓʹ͍ͭͯͷఏҊ஋͕‫ܗ‬੒͞ΕΔɽͦͯ͠ɼͦͷఏҊϧʔϓͱͳ͍ͬͯΔɽಉ༷ʹɼn1 ͱ n3 ͱ n8 ͕αʔ஋͕߹ҙΞϧΰϦζϜʹΑΓ‫ڞ‬௨ͷ߹ҙʹୡͯ͠ɼҰϏε̎ͷάϧʔϓΛߏங͍ͯ͠Δɽ͜͜Ͱɼn1 ͷΑͭͷάϧʔϓ͕Ͱ͖Δɽ͜͏ͯ͠࡞ΒΕͨάϧʔϓͷ͏ʹɼ֤ϊʔυ͸ෳ਺ͷαʔϏεͷϓϥΠϚϦ·ͨ͸தͷϊʔυ͕‫ނ‬োͨ͠Βɼ‫ނ‬ো‫ݕ‬ग़‫ݕ͕ث‬஌ͯ͠ɼάόοΫΞοϓʹͳΔ͜ͱ͕ՄೳͰ͋Δɽ·ͨɼάϧʔϧʔϓ‫ܗ‬੒ϓϩηεʹͦͷ‫ނ‬ো৘ใΛ఻͑Δ͜ͱͰɼϓ಺ͷϊʔυ͕‫ނ‬োͨ͠৔߹ɼ৽ͨʹϊʔυΛάϧʔ‫ނ‬োͨ͠ϊʔυΛ֎ͨ͠৽ͨͳάϧʔϓΛ࡞Γग़͢ɽϓʹՃ͑ͯάϧʔϓͷ࠶ߏஙΛߦ͏ɽ·ͨɼ‫ނ‬োঢ়‫͘ͳͰ͚ͩگ‬ɼϊʔυͷෛՙͷঢ়‫گ‬΋఻͞Βʹɼάϧʔϓͷ࠶ߏங͸ϊʔυͷ‫ނ‬ো͚࣌ͩ͑Δ͜ͱͰɼάϧʔϓ‫ܗ‬੒ͷࡍʹෛՙͷ෼ࢄͱू໿Ͱͳ͘ɼϊʔυͷෛՙʹԠͯ͡ɼෛՙ͕ΩϟύγςΟ͕ͳ͞ΕΔɽάϧʔϓͷ֤ϊʔυ͸ϓϥΠϚϦόοΫΛ௒͑ͳ͍ൣғͰՔಈ͢ΔϊʔυΛ࠷খԽͤ͞ΔΑΞοϓ௨৴ϓϩηεʹΑΓɼΫϥΠΞϯτ͔ΒͷϦΫ͏ʹߦΘΕΔɽͦͷͨΊʹɼ̎ͭͷෛՙͷᮢ஋ upperΤετΛॲཧͯ͠ɼϓϥΠϚϦͱόοΫΞοϓͷαʔͱ lower Λ༻ҙ͢Δɽ·ͣɼෛՙ͕ upper Λ௒͑ͨϏεͷঢ়ଶͷ੔߹ੑΛอͭɽ΋͠ɼ௨৴ঢ়ଶ͕ෆ҆ఆϊʔυ͸ɼෛՙ͕ upper ΛԼճΔ·Ͱάϧʔϓ͔ΒʹͳΓɼಉҰαʔϏεʹؔͯ͠ϓϥΠϚϦ͕ෳ਺ଘࡏൈ͚Δɽ͜ΕʹΑΓɼෛՙ͕ΩϟύγςΟΛ௒͑ͳ͘͢ΔΑ͏ʹͳͬͨΒɼαʔϏεάϧʔϓ౷߹ϓϩηεͳΓɼෛՙ෼ࢄ͕ୡ੒͞ΕΔɽ࣍ʹɼෛՙ͕ lower ΛʹΑΓϓϥΠϚϦΛҰͭʹ౷߹͢Δɽ

Լճͬͨϊʔυ͸ɼΑΓෛՙ͕ߴ͍ϊʔυʹ໾ׂΛ೚ͤΔɽ͜ΕʹΑΓɼෛՙ͕௿͍ϊʔυ͸໾ׂ͕ͳ͘ͳ

ҎԼ 4.1 અ͔Β 4.5 અͰ֤ϓϩηεʹ͍ͭͯΞϧΰϦζϜΛॱ൪ʹઆ໌͢ΔɽΓɼෛՙͷू໿͕ୡ੒͞ΕΔɽ·ͨɼ͍ۙ৔ॴͰͷେ‫ن‬໛ͳ‫ނ‬োʹରԠ͢ΔͨΊ

4. 1 ߹ҙΞϧΰϦζϜʹɼϊʔυ͸޿Ҭʹ഑ஔ͞Ε͓ͯΓɼ֤‫఺ڌ‬ΛΤϦΞຊγεςϜͰ͸߹ҙΞϧΰϦζϜΛར༻ͯ͠ɼϓϥA = {a1 , . . . , ak } ͱ‫Ϳݺ‬ɽ͞ΒʹɼΤϦΞ͸؅ཧऀΠϚϦͱόοΫΞοϓͷάϧʔϓΛ‫ܗ‬੒͢Δɽ߹ҙΞ͕ࣗ༝ʹઃఆՄೳͰ͋Γɼ͋Δϊʔυ ni ͕ෳ਺ͷΤϧΰϦζϜ͸ Paxos ʹमਖ਼ΛՃ͑ͨ΋ͷͰ͋Δɽ·ϦΞʹ‫·ؚ‬Ε͍ͯͯ΋Α͍ɽάϧʔϓ‫ܗ‬੒ͷࡍɼόο

ͣɼPaxos ʹ͍ͭͯઆ໌͢ΔɽΫΞοϓϊʔυ͸ෳ਺ͷΤϦΞʹ഑ஔ͞ΕΔΑ͏ʹ

4. 1. 1 Paxos ͷ֓ཁͳ͍ͬͯΔͨΊɼ͍ۙ৔ॴͰͷେ‫ن‬໛ͳ‫ނ‬ো͕ൃੜ͠

Paxos Ͱ͸ϊʔυͷத͔Βௐఀऀͱ͍͏໾ׂͷϊʔͯ΋ɼҰͭͷόοΫΞοϓϊʔυ͸‫ނ‬োͤͣαʔϏευ͕બ͹Εɼௐఀऀ͸४උཁ‫ͱٻ‬डཧཁ‫̎͏͍ͱٻ‬Λ‫ܧ‬ଓͰ͖Δɽ

ͭͷϝοηʔδʹؔͯ͠ա൒਺ͷϊʔυ͔Β Ack Λड৴ͯ͠ɼ࠷ऴతͳܾఆ஋Λશϊʔυʹૹ৴͢Δɽ4 γεςϜͷΞϧΰϦζϜ֤ϊʔυ i ͸ॏෳ͠ͳ͍൪߸ׂ͕Γ౰ͯΒΕ͓ͯΓຊ‫Ͱڀݚ‬ఏ‫͢ڙ‬ΔγεςϜͰ͸֤ϊʔυ͕ҎԼͷ

ʢ1 ≤ i ≤ nʣɼͦΕͧΕ͕ϥ΢ϯυͱ͍͏Ұ࿈ͷॲཧ͔̍Β̑ͷϓϩηεΛՔಈͤ͞ΔɽΛ‫܁‬Γฦ࣮͠ߦ͢Δ͜ͱͰɼܾఆ·ͰͨͲΓͭ͘ɽϥ1. ߹ҙΞϧΰϦζϜ΢ϯυʹ΋൪߸͕෇͚ΒΕ͓ͯΓɼҰճͷϥ΢ϯυ

2. ো֐‫ݕ‬ग़‫ث‬͕ऴྃ͢Δͱϥ΢ϯυ൪߸͸ n ૿Ճ͢Δɽॳ‫ظ‬஋͕ਤ1γεςϜͷ‫ڥ؀‬

N ull Ͱ͋Δਪఆ஋ͱॳ‫ظ‬஋͕ೖྗ஋ʢྫ͑͹ɼ࣍ͷ৴͢ΔɽϓϥΠϚϦϊʔυͷ IDʣͰ͋ΔఏҊ஋ͱ͍͏ม਺͕͜ͷΑ͏ʹௐఀऀ͸ա൒਺ͷϊʔυ͔Β Ack Λඞ͋Γɼϥ΢ϯυʹΑͬͯ͜ͷม਺ΛมԽͤͯ͞߹ҙ‫ܗ‬ཁͱ͢ΔͨΊɼPaxos Ͱ͸੔߹ੑ͸อͨΕΔ͕ɼա൒੒͢ΔɽҎԼʹ Paxos ͷखॱΛਤ̎ͱ‫ʹڞ‬આ໌͢Δɽ਺ͷϊʔυ‫ނ‬োʹରԠͰ͖ͳ͍ɽ

ͳ͓ɼPaxos ͷ۩ମతͳϓϥΠϚϦόοΫΞοϓํࣜ

4. 1. 2 ຊγεςϜͷ߹ҙΞϧΰϦζϜͷෳ੡ख๏΁ͷಋೖํ๏͸ [6] Λࢀরɽલड़ͷ௨Γɼա൒਺ͷϊʔυ‫ނ‬ো͕ൃੜ͢Δͱ

1. ௐఀऀ͕४උཁ‫ٻ‬Λҙຯ͢Δϝοηʔδʹϥ΢

Paxos Ͱ͸߹ҙ‫ܗ‬੒͕ߦΘΕͳ͍ɽͦ͜Ͱɼௐఀऀ͸ϯυ൪߸ r Λ෇Ճͯ͠ɼશϊʔυʹૹ৴͢Δɽ

λΠϜΞ΢τ͢Δ·Ͱ Ack Λ଴ͪɼͦͷ݁Ռͱͯ͠

2. ४උཁ‫ٻ‬Λड৴ͨ͠ϊʔυ͸ɼ‫ ʹط‬r ΑΓେ͖ա൒਺ͷ Ack ΛಘΒΕͳͯ͘΋ϥ΢ϯυΛऴ͍ྃͤͣϥ΢ϯυ൪߸ͷ४උཁ‫ͨ·ٻ‬͸डཧཁ‫ ʹٻ‬Ackʹ࣍ͷεςοϓʹਐΉΑ͏ʹ͢ΔʢN ack ͕͋Ε͹ϥΛฦ͍ͯ͠ΔͳΒ͹ N ack Λௐఀऀʹฦ͢ɽͦ͏΢ϯυΛऴྃͤ͞Δʣɽ͜ΕʹΑΓա൒਺ͷϊʔυ͕Ͱͳ͚Ε͹ɼAck ʹ " ਪఆ஋, डཧΛ࠷‫ͬߦʹޙ‬‫ނ‬োͯ͠΋αʔϏεΛ‫ܧ‬ଓͰ͖ΔͨΊɼ੔߹ੑ͸٘ਜ਼ͨϥ΢ϯυ൪߸ # Λ෇Ճͯ͠ௐఀऀʹฦ͢ɽʹͳΔ͕ɼՄ༻ੑ͸ߴ͘ͳΔ͜ͱʹͳΔɽ·ͨɼա൒

3. ௐఀऀ͸ա൒਺ͷϊʔυ͔Βฦ৴Λ଴ͭɽҰͭ਺ͷϊʔυͱ҆ఆతʹ௨৴͕Ͱ͖Δঢ়‫Ͱگ‬͸ɼPaxosͰ΋ N ack ͕͋Ε͹ϥ΢ϯυΛऴྃͤ͞Δɽશͱಉ͡ಈ࡞Λ͢ΔͨΊɼಉҰͷܾఆ͕ߦΘΕɼ੔߹ੑͯ Ack ͳΒडཧཁ‫ٻ‬Λҙຯ͢Δϝοηʔδʹ "r,͸อূ͞ΕΔɽఏҊ஋ # Λ෇Ճͯ͠ɼશϊʔυʹૹ৴͢Δɽ͜ͷ࣌ɼಘΒΕͨਪఆ஋ʹ N ull Ͱͳ͍΋ͷ͕͋Ε

4. 2 ো֐‫ݕ‬ग़‫ث‬͹ɼϥ΢ϯυ൪߸͕࠷େͷ΋ͷΛਪఆ஋ͱ͢ΔɽຊγεςϜͰ͸ɼ‫ࡏݱ‬ͷάϧʔϓͷதͷϊʔυ͕

4. डཧཁ‫ٻ‬Λड৴ͨ͠ϊʔυ͸ɼ‫ ʹط‬r ΑΓେ͖‫ނ‬ো͍ͯ͠Δ͔Λ‫ࠪ͢ݕ‬ΔͨΊʹো֐‫ݕ‬ग़‫ث‬Λ༻ҙ͍ϥ΢ϯυ൪߸ͷ४උཁ‫ͨ·ٻ‬͸डཧཁ‫ ʹٻ‬Ack͢Δɽ֤ϊʔυ͸ಉҰαʔϏεͷάϧʔϓͷϊʔυΛฦ͍ͯ͠ΔͳΒ͹ N ack Λௐఀऀʹฦ͢ɽͦͱϋʔτϏʔτύέοτΛૹΓ͋͏ɽ͋Δϊʔυ͔Β͏Ͱͳ͚Ε͹ɼఏҊ஋Λਪఆ஋ͱ͠ Ack ΛௐఀҰఆ࣌ؒϋʔτϏʔτύέοτ͕ૹΒΕͳ͚Ε͹ɼͦऀʹฦ͢ɽͷϊʔυ͕‫ނ‬ো͍ͯ͠Δͱ൑அͯ͠άϧʔϓ‫ܗ‬੒ϓ

5. ௐఀऀ͸ա൒਺ͷϊʔυ͔Βฦ৴Λ଴ͭɽҰͭϩηεʹ‫ނ‬োঢ়‫گ‬Λ఻͑ΔɽωοτϫʔΫো֐ʹΑΓͰ΋ N ack ͕͋Ε͹ϥ΢ϯυΛऴྃͤ͞ΔɽશϋʔτϏʔτύέοτ͕ૹ৴͞Εͳ͍͜ͱ΋ߟ͑Βͯ Ack ͳΒఏҊ஋Λܾఆ஋ͱͯ͠શϊʔυʹૹΕΔ͕ɼ‫ނ‬োͨ͠ϊʔυ͸ύέοτΛૹ৴Ͱ͖ͳ͍ͷਤ2Paxos ͷखॱͰɼ͜ΕʹΑΓ‫ނ‬ো‫ݕ‬ग़Λߦ͏͜ͱ͕Ͱ͖Δɽ۩ମతʹ͸֤ϊʔυ͸֤αʔϏεʹ͍ͭͯҎԼͷ

Algorithm 2 ϋʔτϏʔτड৴ଆwhile true doม਺Λ༻ҙͯ͠ɼAlgorithm1 ͱ Algorithm2 Λ࣮ߦϋʔτϏʔτύέοτΛड৴͢Δ·Ͱ଴ͭ͢ΔɽϋʔτϏʔτύέοτΛૹͬͨϊʔυʹରͯ͠Ack Λฦ͢ม਺• N = {n1 , .., nk } : ϊʔυͷू߹

end while• V iews ∈ 2N : αʔϏε s ͷάϧʔϓʹ‫·ؚ‬Ε͍ͯΔϊʔυͷू߹• f ailedN ode ∈ 2N : ‫ނ‬ো͍ͯ͠Δͱ൑அ͞Εͨϊʔυͷू߹

Algorithm 1 ϋʔτϏʔτૹ৴ଆwhile true dowhile views ͷ֤ཁૉΛ n ͱ͢Δ doϋʔτϏʔτύέοτΛ n ʹૹ৴͢Δend while

4. 3 άϧʔϓ‫ܗ‬੒ϓϩηε͜ͷϓϩηεͰ͸αʔϏε͝ͱʹϓϥΠϚϦͱόοΫΞοϓͷάϧʔϓͷߏஙΛߦ͏ɽ·ͨɼՄ༻ੑͱলిྗͷ‫͔఺؍‬Β‫ނ‬ো΍ෛՙͷঢ়‫ʹگ‬Ԡͯ͡άϧʔϓͷ࠶ߏஙΛߦ͍ɼෛՙͷ෼ࢄͱू໿Λߦ͏ɽෛՙͷ෼ࢄͱू໿ͷͨΊʹɼෛՙͷᮢ஋ upper ͱ lower ΛͦΕͧΕͷϊʔυʹอ࣋ͤ͞ΔɽҎԼͷखॱͰάϧʔϓͷ‫ܗ‬੒Λߦ͏ɽҰఆ࣌ؒ଴ͭ

1. ߹ҙΞϧΰϦζϜΛ‫ى‬ಈ͢Δɽ

Ack Λड৴

2. ௐఀऀͱͳͬͨϊʔυ͸‫ࡏݱ‬ͷάϧʔϓΛ৽͠

Ack ͕དྷͳ͔ͬͨϊʔυΛϦετԽ͠ɼͦΕΛ͍άϧʔϓͷఏҊ஋ͱ͠ɼෛՙ͕ upper Λ௒͑f ailedN ode ͱ͢Δͨϊʔυͱ lower ΛԼճͬͨϊʔυͱ‫ނ‬োͱ൑

f ailedN ode Λάϧʔϓ‫ܗ‬੒ΞϧΰϦζϜʹ఻அ͞ΕͨϊʔυΛ৽͍͠άϧʔϓͷఏҊ஋͔Β

͑Δ

֎͢ɽ

end while

3. άϧʔϓ͔Β֎ͨ͠਺͚ͩɼ৽͍͠ϊʔυΛ৽͍͠άϧʔϓʹՃ͑Δɽͨͩ͠ɼ͜ͷ࣌୅ସϊʔυͷෛՙ͸ upper Λ௒͑ͯ͸͍͚ͳ͘ɼάϧʔϓ͔Β֎͢ϊʔυͷதͰෛՙ͕ lower ΛԼճͬͨϊʔυͷ୅ସʹؔͯ͠͸ɼͦͷϊʔυΑΓ΋ෛՙ͕ߴ͘ͳ͚Ε͹ͳΒͳ͍ɽ

4. ߹ҙΞϧΰϦζϜʹΑΓ߹ҙ‫ܗ‬੒͕ߦΘΕɼάϧʔϓ͕࠶ߏங͞ΕΔɽҎ্Ͱड़΂ͨϓϩηεʹΑΓɼ‫ނ‬ো΍ෛՙͷঢ়‫ʹگ‬Ԡͯ͡άϧʔϓΛมԽͤ͞Δɽͦͯ͠ɼ͜͏ͯ͠ߏங͞Εͨάϧʔϓ͕ϓϥΠϚϦόοΫΞοϓ௨৴ϓϩηεͰ௨৴͠߹͏ɽ4. 4 ϓϥΠϚϦόοΫΞοϓ௨৴ϓϩηε

Algorithm 3 ϓϥΠϚϦ
while true doαʔϏε s ͷϦΫΤετΛड৴͢Δ·Ͱ଴ͭϦΫΤετΛॲཧ͢ΔαʔϏε s ͷߋ৽σʔλΛ views ͷϩʔΧϧόοΫΞοϓʹରͯ͠ૹ৴͢Δա൒਺ͷ Ack Λड৴͢Δ·Ͱ଴ͭαʔϏεͷঢ়ଶΛߋ৽͢ΔϢʔβʔʹϨεϙϯεΛฦ͢end whileϓϥΠϚϦόοΫΞοϓ௨৴Ͱ͸ɼΫϥΠΞϯτ͔ΒͷϦΫΤετͷॲཧͱɼόοΫΞοϓΛ࠷৽ͷঢ়ଶʹߋ৽͢ΔॲཧΛ࣮ߦ͢ΔɽΫϥΠΞϯτ͔ΒͷϦΫΤετΛॲཧ͢Δͱ͖͸ɼάϧʔϓͷա൒਺ͷϊʔυΛߋ৽͔ͤͯ͞ΒΫϥΠΞϯτʹ݁ՌΛฦ͢Α͏ʹ͢Δɽͦ͏͢Δ͜ͱͰɼա൒਺ͷϊʔυͱ௨৴Ͱ͖Δঢ়ଶͰͷ੔߹ੑΛอͭ͜ͱ͕Ͱ͖Δɽ·ͨɼ޿ҬγεςϜͱ͍͏͜ͱͰҟͳΔΤϦΞͷϊʔυͱͷ௨৴ΑΓ΋ಉҰΤϦΞͷϊʔυͱͷ௨৴ͷ΄͏͕༰қͰ͋Δ͜ͱ͔ΒɼόοΫΞοϓΛϦϞʔτόοΫΞοϓͱϩʔΧϧόοΫΞοϓͷ̎छྨʹ෼ྨ͠ɼຖճͷϦΫΤετ͝ͱʹϩʔΧϧόοΫΞοϓΛߋ৽ͤ͞ɼϦϞʔτόοΫΞοϓ͸Ұఆ‫ʹͱؒ͝ظ‬Ұ‫ׅͯ͠‬ঢ়ଶͷߋ৽Λߦ͏Α͏ʹ͢Δɽ͜ͷॲཧͷखॱΛਤ̑ʹࣔ͢ɽΫϥΠΞϯτ͔Βϓ

Algorithm 4 ϩʔΧϧόοΫΞοϓ
count = 0updateData = N U LL
while true doϓϥΠϚϦ͔Βߋ৽σʔλΛड৴͢Δ·Ͱ଴ͭߋ৽σʔλΛ newData ͱ͢Δ
if views ͷϩʔΧϧόοΫΞοϓͷதͰࣗ෼͕࠷΋௿͍ ID thencount = count + 1
updateData = updateData + newData
if count == ೚ҙͷఆ਺ thenશͯͷϦϞʔτόοΫΞοϓʹରͯ͠ updateDataΛૹ৴͢ΔupdateData = N U LL
count = 0
end ifend ifend whileϥΠϚϦ͕ϦΫΤετΛड͚෇͚ͯόοΫΞοϓΛߋ৽‫ޙ‬ɼΫϥΠΞϯτʹϨεϙϯεΛฦ͢Ұ࿈ͷखॱΛ͍ࣔͯ͠Δɽ

Algorithm 5 ϦϞʔτόοΫΞοϓ

ม਺Λ༻ҙͯ͠ɼAlgorithm3ɼAlgorithm4ɼAlgo-while true doόοΫΞοϓ͔Β updateData Λड৴͢ΔupdateData Λ࢖͍ɼαʔϏεΛߋ৽͢Δrithm5 ͷΞϧΰϦζϜΛ࣮ߦ͢Δɽ

end while۩ମతʹ͸֤ϊʔυ͸֤αʔϏεʹ͍ͭͯҎԼͷม਺• count : Χ΢ϯλ• newData : ϦΫΤετͷॲཧʹΑΓੜ·ΕͨαʔϏεͷࠩ෼σʔλ• updateData : ࠩ෼σʔλͷू߹

4. 5 αʔϏεάϧʔϓ౷߹ϓϩηεຊγεςϜͰ͸ɼωοτϫʔΫ෼அ͕ൃੜ͠ϊʔυؒͰਖ਼ৗʹ௨৴͕Ͱ͖ͳ͘ͳͬͨ‫ޙ‬ɼಉ͡αʔϏεʹؔͯ͠ෳ਺ͷϓϥΠϚϦ΍όοΫΞοϓͷάϧʔϓ͕ੜ͡Δ͜ͱ͕͋Δɽ͕ͨͬͯ͠ɼωοτϫʔΫ෼அ͕ճ෮͠ɼͦΕͧΕͷϓϥΠϚϦಉ͕࢜௨৴Ͱ͖ΔΑ͏ʹͳͬͨ‫ޙ‬ɼෳ਺ͱͳͬͨάϧʔϓΛҰͭʹ౷߹͠ͳ͚Ε͹ͳΒͳ͍ɽͦͷͨΊɼ֤ϊʔυ͸γεςϜ಺ͷશϊʔυ৘ใͰਤ3ϓϥΠϚϦόοΫΞοϓ௨৴ͷखॱ͋ΔϊʔυϦετΛ࢖͍ɼఆ‫ظ‬తʹશϊʔυʹରͯ͠ɼࣗ෼ͱಉ͡αʔϏεͷϓϥΠϚϦͰ͋Δ͔ௐ΂Δ

5 γεςϜͷੑ࣭ͨΊͷϝοηʔδΛૹ৴͢Δɽ૬खͷϊʔυ͕ಉҰͷຊγεςϜͰՄ༻ੑͱলిྗʹؔͯ͠ຬͨ͢΂͖ੑαʔϏεͷϓϥΠϚϦΛՔಈ͍ͤͯͨ͞Βɼ૬खͷ࣭ͱͯ͠ɼҎԼͷ͕̐ͭߟ͑ΒΕΔɽ࣮૷‫ޙ‬ͷ࣮‫Ͱݧ‬ϊʔυ͔ΒαʔϏεͷσʔλΛड৴ͯ͠ɼαʔϏεঢ়͸ɼҎԼͷੑ࣭͔̍Β͕̐੒Γཱͭ͜ͱΛ֬ೝ͢ΔɽଶΛߋ৽͢Δɽͦͷ‫ޙ‬ɼ૬खͷϊʔυͷϓϥΠϚϦͷ

ੑ࣭ 1 ωοτϫʔΫ෼அ΁ͷՄ༻ੑɿ೚ҙͷά໾ׂΛऴྃͤ͞Δ͜ͱͰɼϓϥΠϚϦΛҰͭʹ͢Δɽϧʔϓ gi = {n1 ...nl } ʹ͓͍ͯɼgi1 + gi2 = gi͞ΒʹɼͦͷϓϥΠϚϦ͕όοΫΞοϓʹରͯ͠΋ऴྃཁ‫ٻ‬Λग़͢͜ͱͰɼάϧʔϓΛҰͭʹ౷߹͢Δɽ۩ମతʹ͸֤ϊʔυ͸֤αʔϏεʹ͍ͭͯҎԼͷม਺Λ༻ҙͯ͠ɼAlgorithm6 Λ࣮ߦ͢ΔɽͱͳΔ೚ҙͷ ni ∈ gi1 ͱ nj ∈ gi2 ͷؒͰ௨৴͕

Ͱ͖ͳ͘ͳΔͱɼgi1 ͱ gi2 ͰͦΕͧΕ̍ͭͷϓϥΠϚϦ͕ଘࡏͯ͠ಠཱʹಉҰͷαʔϏεΛఏ‫͖Ͱڙ‬Δɽ͞Βʹɼ͜ͷ௨৴ো֐͕෮‫͢چ‬Δͱɼ

gi ͰϓϥΠϚϦ͕̍ͭͱͳΔɽม਺N• nodeList ∈ 2 : ϊʔυϦετͰ͋ΓɼγεςϜ಺ͷશͯͷϊʔυͷ ID ͱΞυϨε͕‫·ؚ‬Ε͍ͯΔੑ࣭ 2 ա൒਺ͷϊʔυ‫ނ‬ো΁ͷՄ༻ੑɿ೚ҙͷάϧʔϓ gi = {n1 ...nl } ʹ͓͍ͯɼ͋Δϊʔυ niҎ֎ͷશͯͷϊʔυ͕‫ނ‬োͯ͠΋ ni ͕ϓϥΠϚϦͱͳΓαʔϏεΛఏ‫͠ڙ‬ଓ͚Δ͜ͱ͕Ͱ͖Δɽ

Algorithm 6 ౷߹ϓϩηε
while true dowhile nodeList ͷ֤ཁૉΛ n ͱ͢Δ doαʔϏεϋʔτϏʔτύέοτΛ n ʹૹ৴͢Δend whileαʔϏεϋʔτϏʔτύέοτͱϝοηʔδΛड৴if ಉҰͷαʔϏεΛ‫ى‬ಈ͍ͯ͠Δϊʔυ͕͋Δ thenif ‫ܧ‬ଓϝοηʔδΛड৴ thenσʔλΛૹ৴ऴྃϝοηʔδΛड৴αʔϏεΛऴྃelse‫ܧ‬ଓϝοηʔδΛૹ৴σʔλΛड৴σʔλΛ࢖͍ɼαʔϏεͷঢ়ଶΛߋ৽ऴྃϝοηʔδΛૹ৴
end ifend ifend whileੑ࣭ 3 ̍ΤϦΞͷେ‫ن‬໛ͳϊʔυ‫ނ‬ো΁ͷՄ༻ੑɿͲͷ̎ͭͷΤϦΞ ai ɼaj ʹ͓͍ͯ΋ nj ∈ ai

͔ͭ ni ∈ aj ͱͳΔϊʔυ ni ͕ଘࡏ͠ͳ͍৔߹ɼ
͋ΔΤϦΞ ak = {n1 ...nl } ʹ͓͍ͯɼͦͷશͯͷϊʔυ͕‫ނ‬োͨ͠ͱͯ͠΋ɼશͯͷαʔϏεͰগͳ͘ͱ΋Ұͭ͸ϓϥΠϚϦ·ͨ͸όοΫΞο
ϓ͕ଘࡏ͠ɼαʔϏεΛՔಈ͠ଓ͚Δ͜ͱ͕Ͱ͖Δɽ
ੑ࣭ 4 ϊʔυͷෛՙ෼ࢄɿ͋Δϊʔυ ni ͕ෳ਺ͷάϧʔϓ G = {g1 ...gl } ʹଐ͍ͯ͠Δͱ͢Δɽ͜ͷ࣌ʹɼni ͷෛՙ্͕ͷᮢ஋ upper Λ௒͑Δͱɼni ͸ෛՙ͕ upper ΛԼճΔ·Ͱ G ͔Β཭୤͢Δɽ·ͨɼni ͕཭୤ͨ͠ gj ʹ͓͍ͯ͸ɼni ͷ୅ΘΓͱͳΔϊʔυΛ৽ͨʹՃ͑ɼ৽͍͠άϧʔϓΛ࠶ߏங͢Δɽ͜ΕΒͷੑ࣭ͷ௚‫؍‬తͳҙຯ͸ɼͦΕͧΕҎԼͷ௨ΓͰ͋Δɽੑ࣭ 1 ͸͋ΔάϧʔϓͷதͰ௨৴͕Ͱ͖ͳ͘ͳͬͨ࣌ɼͦΕͧΕͷ෼ׂ͞Εͨάϧʔϓʹ͓͍ͯɼϓϥΠ͏ͳ‫ػ‬ೳΛγεςϜʹ෇Ճͨ͠ɽࠓ‫ޙ‬͸ɼ਺े୆ఔ౓ͷ‫ػࢉܭ‬Λ༻͍ͯຊఏҊख๏ͷϓϩτλΠϓΛ࣮૷͠ɼ͜ΕΛ༻͍ͯো֐΍ωοτϫʔΫ෼அʹର͢ΔՄ༻ੑ΍Ԡ౴ੑೳͳͲʹ͍ͭͯධՁΛߦ͏ɽϚϦ͕ੜͯ͡αʔϏεΛ‫ܧ‬ଓ͢Δ͜ͱΛද͍ͯ͠Δɽ·ͨɼ௨৴ো֐͕ճ෮ͨ͠‫ޙ‬ɼͦΕΒͷϓϥΠϚϦ͕ࢀ ߟ จ ‫ݙ‬Ұͭʹ౷߹͞ΕΔ͜ͱ΋ҙຯ͍ͯ͠Δɽੑ࣭ 2 ͸͋

[ 1 ] T. Bostoen, S. Mullender. Power-Reduction
Techniques for Data-Center Storage Systems, ACM
Computing Surveys, vol. 45 (3) 2013.
[ 2 ] N. Budhiraja, K. Marzullo, F. B. Schneider, S.
Toueg. The Primary-backup approach, Distributed
Systems (2nd ed.), ACM press/Addison − W esley
P ublishing Co., pp. 199-216 1993.
[ 3 ] X. Defago and A. Schiper. Semi-Passive Replication and Lazy Consensus, Journal of P arallel andDistributed Systems, vol. 64(12), pp. 1380-1398,
2004[ 4 ] R. Guerraoui, A. Schiper. Consensus Service: amodular approach for building agreement protocols
in distributed system. IEEE F T CS, 1996.
[ 5 ] L. Lamport. The Part-time Parliament, ACM
T OCS, vol.16 (2), pp.133-169, 1998.
[ 6 ] D. Mazieres. Paxos Made Practical. ACM
SIGACT N ews 32, 2001.
[ 7 ] F. B. Schneider. Implementing Fault-Tolerant
Services Using the State Machine Approach: A
Tutorial, ACM Computing Surveys, vol. 22 (4),pp.299-319, 1990.
[ 8 ] D. Stodden. Semi-Active Workload Replicationand Live Migration with Paravirtual Machines, Xen
Summit, Spring 2007.

Δάϧʔϓͷ΄΅શͯͷϊʔυ͕‫ނ‬োͯ͠΋ɼҰͭϊʔυ͕ਖ਼ৗͰ͋Ε͹αʔϏεΛ‫ܧ‬ଓͰ͖Δ͜ͱΛද͍ͯ͠Δɽੑ࣭ 3 ͸̍ͭͷΤϦΞͷશͯͷϊʔυ͕‫ނ‬োͯ͠΋ɼඞͣҰͭ͸ϊʔυ͕ੜ͖࢒ΓαʔϏεΛ‫ܧ‬ଓͰ͖Δ͜ͱΛද͍ͯ͠Δɽੑ࣭ 4 ͸͋Δϊʔυͷෛՙ͕ upper Λ௒͑ͨ৔߹ɼάϧʔϓ͔Β཭୤͢Δ͜ͱʹΑΓɼ͍ͣΕͦͷෛՙ͸ upper ΛԼճΔ͜ͱΛද͍ͯ͠Δɽ

6 ·ͱΊͱࠓ‫ޙ‬ͷ՝୊ैདྷͷ Paxos ༻͍ͨडಈతෳ੡ख๏Ͱ͸Ͱ͖ͳ͔ͬͨɼେ‫ن‬໛ͳ‫ނ‬ো΍ωοτϫʔΫ෼அʹରԠՄೳͳ޿Ҭ෼ࢄγεςϜΛఏҊͨ͠ɽͦͷͨΊʹɼ੔߹ੑΛ٘ਜ਼ʹ͢Δ͜ͱͰɼա൒਺ͷϊʔυ‫ނ‬োͰ΋߹ҙ‫ܗ‬੒ՄೳͳΑ͏ʹ Paxos Λमਖ਼ͯ͠ɼडಈతෳ੡ख๏ʹऔΓೖΕͨɽ·ͨɼγεςϜͷ҆ఆੑͱলిྗԽΛߟ͑ɼෛՙͷมಈʹ߹ΘͤͯɼάϧʔϓΛมԽͤ͞ΔΑ