関数の保存を目的とした故障ノード修復可能な 分散ストレージ方式における 修復帯域幅を最小とする再生成符号の一構成法

11 商　　大　　論　　集

1　はじめに

　分散ストレージ方式とは重要な情報であ るオリジナル情報を

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable) ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ 個のノードに分散さ せて保管し，必要なときに

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable) ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ 個

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ の ノードの分散情報からオリジナル情報が復 元できる方式である．よって，故障等によっ て一部のノードの分散情報が利用できなく なった場合でも，正常なノードが k 個以上 存在していれば，それらのノードの分散情 報からオリジナル情報が復元できるため信 頼性が確保できる．このような方式は，リー ド・ソロモン符号のような最大距離分離 （MDS:Maximmum Distance Separable）

符号 [1] を利用することで実現できる．具 体 的 に は， 情 報 長

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ ， 符 号 長

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ と し た

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable) ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ MDS 符号によってオリジナル情報を 長さ

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ の符号語に符号化し，その符号語の 各シンボルを各ノードの分散情報とするこ とで，任意の

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ 個の分散情報からオリジナ ル情報を復元可能な分散ストレージ方式が 実現できる． 　また，信頼性の観点から故障ノードを修 復できる方がより望ましいため，分散スト レージ方式における故障ノードの修復に関 する研究が近年盛んに行われている．修復 可能な分散ストレージ方式の自明な構成法 として，故障していない任意の

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable) ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ 個のノー ドの分散情報からオリジナル情報を復元 し，故障ノードが記憶していた分散情報を 再生成することが考えられるが，再生成し たい分散情報の

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ 倍の大きさの情報を利用 するため効率的ではない．この問題に対し て，

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ を満たす任意の

࿦จ

ؔ਺ͷอଘΛ໨తͱͨ͠ނোϊʔυम෮Մೳͳ෼ࢄετϨʔδํࣜʹ͓͚Δ

म෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ූ߸ͷҰߏ੒๏

٢ɹాɹོɹ߂

1

͸͡Ίʹ

෼ࢄετϨʔδํࣜͱ͸ॏཁͳ৘ใͰ͋ΔΦϦδφ ϧ৘ใΛ n ݸͷϊʔυʹ෼ࢄͤͯ͞อ؅͠ɼඞཁͳ ͱ͖ʹ k ݸ (k ≤ n) ͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδ φϧ৘ใ͕෮ݩͰ͖ΔํࣜͰ͋ΔɽΑͬͯɼނো౳ʹ ΑͬͯҰ෦ͷϊʔυͷ෼ࢄ৘ใ͕ར༻Ͱ͖ͳ͘ͳͬͨ ৔߹Ͱ΋ɼਖ਼ৗͳϊʔυ͕ k ݸҎ্ଘࡏ͍ͯ͠Ε͹ɼ ͦΕΒͷϊʔυͷ෼ࢄ৘ใ͔ΒΦϦδφϧ৘ใ͕෮ݩ Ͱ͖ΔͨΊ৴པੑ͕֬อͰ͖Δɽ͜ͷΑ͏ͳํࣜ͸ɼ ϦʔυɾιϩϞϯූ߸ͷΑ͏ͳ࠷େڑ཭෼཭ (MDS: Maximmum Distance Separable)ූ߸ [1] Λར༻͢ Δ͜ͱͰ࣮ݱͰ͖Δɽ۩ମతʹ͸ɼ৘ใ௕ kɼූ߸௕ nͱͨ͠ [n, k] MDS ූ߸ʹΑͬͯΦϦδφϧ৘ใΛ ௕͞ n ͷූ߸ޠʹූ߸Խ͠ɼͦͷූ߸ޠͷ֤γϯϘϧ Λ֤ϊʔυͷ෼ࢄ৘ใͱ͢Δ͜ͱͰɼ೚ҙͷ k ݸͷ෼ ࢄ৘ใ͔ΒΦϦδφϧ৘ใΛ෮ݩՄೳͳ෼ࢄετϨʔ δํ͕࣮ࣜݱͰ͖Δɽ ·ͨɼ৴པੑͷ؍఺͔ΒނোϊʔυΛम෮Ͱ͖Δํ ͕ΑΓ๬·͍ͨ͠Ίɼ෼ࢄετϨʔδํࣜʹ͓͚Δނ োϊʔυͷम෮ʹؔ͢Δݚڀ͕ۙ೥੝ΜʹߦΘΕ͍ͯ Δɽम෮Մೳͳ෼ࢄετϨʔδํࣜͷࣗ໌ͳߏ੒๏ͱ ͯ͠ɼނো͍ͯ͠ͳ͍೚ҙͷ k ݸͷϊʔυͷ෼ࢄ৘ใ ͔ΒΦϦδφϧ৘ใΛ෮ݩ͠ɼނোϊʔυ͕هԱͯ͠ ͍ͨ෼ࢄ৘ใΛ࠶ੜ੒͢Δ͜ͱ͕ߟ͑ΒΕΔ͕ɼ࠶ੜ ੒͍ͨ͠෼ࢄ৘ใͷ k ഒͷେ͖͞ͷ৘ใΛར༻͢Δͨ Ίޮ཰తͰ͸ͳ͍ɽ͜ͷ໰୊ʹରͯ͠ɼk ≤ d Λຬͨ ͢೚ҙͷ d ݸͷނো͍ͯ͠ͳ͍ϊʔυ͕ੜ੒͢Δނো ϊʔυम෮༻ͷ৘ใΛूΊΔ͜ͱͰޮ཰తʹނোϊʔ υͷ෼ࢄ৘ใΛ࠶ੜ੒Ͱ͖Δ࠶ੜ੒ූ߸ͷ֓೦͕ࣔ͞ Εͨ [2]ɽߋʹɼ֤ϊʔυ͕هԱ͢Δ෼ࢄ৘ใͷهԱ ༰ྔʢҎԼͰ͸ɼ୯ʹهԱ༰ྔͱݺͿʣͱނোϊʔυ Λम෮͢ΔͨΊʹඞཁͳ࠶ੜ੒৘ใͷେ͖͞ʢҎԼͰ ͸ɼम෮ଳҬ෯ͱݺͿʣʹτϨʔυΦϑ͕͋Δ͜ͱ΋ ࣔ͞Ε͍ͯΔ [2]ɽ͜ͷτϨʔυΦϑʹ͓͍ͯɼهԱ༰ ྔ͕࠷খͱͳΔͱ͖ʹम෮ଳҬ෯Λ࠷খͱ͢Δ࠶ੜ੒ ූ߸ɼٴͼम෮ଳҬ෯͕࠷খͱͳΔͱ͖ʹهԱ༰ྔΛ ࠷খͱ͢Δ࠶ੜ੒ූ߸͕ఏҊ͞Ε͍ͯΔ [3, 4, 5, 6]ɽ Ұํɼؔ਺Λൿີ৘ใͱͯ͠෼ࢄ͢Δൿີؔ਺෼ࢄ ๏͕ఏҊ͞Ε͍ͯΔ [7, 8, 9]ɽ͜ͷํࣜ͸͖͍͠஋ൿ ີ෼ࢄ๏ [10] ʹ͓͚Δൿີ৘ใΛؔ਺ʹ֦ுͨ͠ํࣜ Ͱɼ·ͣؔ਺ φ(·) Λ n ݸͷ෼ࢄ৘ใʹූ߸Խ͠ɼͦ ΕΒΛ֤ϊʔυ͕هԱ͢Δɽೖྗ஋ x ʹର͢Δؔ਺஋ φ(x)Λ஌Γ͍ͨར༻ऀ͸ɼೖྗ஋ x Λ೚ҙͷ k ݸͷ ϊʔυ΁ૹ৴͠ɼ֤ϊʔυ͸ x ͱࣗ਎͕هԱ͍ͯ͠Δ ෼ࢄ৘ใ͔Β φ(x) ʹର͢Δؔ਺஋෮ݩ৘ใΛੜ੒͠ ͯར༻ऀ΁ૹ৴͢Δɽར༻ऀ͸ k ݸͷؔ਺஋෮ݩ৘ใ ͔Βɼؔ਺஋ φ(x) Λ෮ݩ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷΑ ͏ͳؔ਺ͷൿີ෼ࢄ๏Λར༻͢Δ͜ͱͰ Kerberos ౳ ͷݤ഑ૹํࣜʹ͓͚Δݤ഑ૹηϯλʔͷػೳΛ෼ࢄ͠ɼ Ұ෦ͷݤ഑ૹηϯλʔͷػೳఀࢭ΍ෆਖ਼ʹର͢ΔϦε ΫΛܰݮͰ͖Δ [9]ɽ͔͠͠ɼϊʔυͷނোʹΑͬͯ ഁଛɾফࣦͨ͠෼ࢄ৘ใΛޮ཰తʹ࠶ੜ੒͢Δํࣜʹ ͍ͭͯ͸ߟ͑ΒΕ͍ͯͳ͍ɽ ͦ͜Ͱຊ࿦จͰ͸ɼൿີؔ਺෼ࢄ๏ͱಉ༷ʹɼؔ਺ ͷอଘΛ໨తͱ͢Δނোϊʔυ͕म෮Մೳͳ෼ࢄετ ϨʔδํࣜΛ৽ͨʹఆٛ͢Δɽ࣍ʹɼఏҊͨ͠ํࣜΛ ࣮ݱ͢Δ࠶ੜ੒ූ߸ΛఏҊ͠ɼͦͷ࠶ੜ੒ූ߸ͷੑ࣭ Λࣔ͢ɽ ຊ࿦จͷߏ੒͸ҎԼͷͱ͓ΓͰ͋Δɽ2 ষͰ͸ैདྷ ͷम෮Մೳͳ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λઆ໌ ͢Δɽ3 ষͰ͸ɼؔ਺ͷอଘΛ໨తͱ͢Δम෮Մೳͳ ෼ࢄετϨʔδํࣜͱ࠶ੜ੒ූ߸Λ৽ͨʹఆٛ͠ɼ4 ষͰؔ਺ͷอଘΛ໨తͱ͢Δ࠶ੜ੒ූ߸ͷ۩ମతߏ੒ ๏ΛఏҊ͢Δɽ࠷ޙʹ 5 ষͰ·ͱΊΔɽ

2

ैདྷݚڀ

2.1 म෮Մೳͳ෼ࢄετϨʔδํࣜ म෮Մೳͳ෼ࢄετϨʔδํࣜ͸ɼn ݸͷϊʔυ ψ1, ψ2, . . . , ψn ͱσʔλίϨΫλʔ DC ʹΑͬͯߏ 個の故障して いないノードが生成する故障ノード修復用 の情報を集めることで効率的に故障ノード の分散情報を再生成できる再生成符号の概 念が示された [2]．更に，各ノードが記憶 する分散情報の記憶容量（以下では，単に 記憶容量と呼ぶ）と故障ノードを修復する ために必要な再生成情報の大きさ（以下で は，修復帯域幅と呼ぶ）にトレードオフが あることも示されている [2]．このトレー ドオフにおいて，記憶容量が最小となると きに修復帯域幅を最小とする再生成符号， 及び修復帯域幅が最小となるときに記憶容 量を最小とする再生成符号が提案されてい る [3, 4, 5, 6]．

関数の保存を目的とした故障ノード修復可能な

分散ストレージ方式における

修復帯域幅を最小とする再生成符号の一構成法

吉　田　隆　弘