著者

尾形 篤史 木村 昌臣

雑誌

研究報告データベースシステム(DBS)

巻号頁・発行日

vol.2013-DBS-158, no.7, pp.1-6, 2013-11-19

---

CAP 定理は,2000 年に Eric A. Brewer が提唱した定理である.CAP 定理では,分散システムが持つべき 3 つの性質 (一貫性・可用性・分断耐性) のうち,少なくとも 2 つしか同時に満たせないと述べている.2002 年に Seth Gilbert と Nancy Lynch が CAP 定理の証明を可用性が常に成り立つという前提で行った.しかし証明では CAP 定理の各性質が成り立つ状況を網羅的に示しておらず,様々な分散システムに対して CAP 定理が成り立つことを示していない。また,CAP 定理の各性質は論文によって定義が異なり,曖昧であるという問題がある.そこで,本研究では,CAP 定理の各性質を厳密に定義するため,各性質の条件式をグラフ理論の隣接行列を基に定式化する.そして,シミュレーションによって分散システムを網羅的に検証し,CAP 定理の各性質が成り立つ状況の検討を行い,CAP 定理の一貫性と可用性,一貫性と分断耐性,可用性と分断耐性が成り立つ分散システムの条件を検討する.

著者

尾形 篤史 木村 昌臣

出版者

一般社団法人情報処理学会

雑誌

研究報告データベースシステム(DBS)

巻号頁・発行日

vol.2013, no.7, pp.1-6, 2013-11-19

---

CAP 定理は,2000 年に Eric A. Brewer が提唱した定理である.CAP 定理では,分散システムが持つべき 3 つの性質 (一貫性・可用性・分断耐性) のうち,少なくとも 2 つしか同時に満たせないと述べている.2002 年に Seth Gilbert と Nancy Lynch が CAP 定理の証明を可用性が常に成り立つという前提で行った.しかし証明では CAP 定理の各性質が成り立つ状況を網羅的に示しておらず,様々な分散システムに対して CAP 定理が成り立つことを示していない。また,CAP 定理の各性質は論文によって定義が異なり,曖昧であるという問題がある.そこで,本研究では,CAP 定理の各性質を厳密に定義するため,各性質の条件式をグラフ理論の隣接行列を基に定式化する.そして,シミュレーションによって分散システムを網羅的に検証し,CAP 定理の各性質が成り立つ状況の検討を行い,CAP 定理の一貫性と可用性,一貫性と分断耐性,可用性と分断耐性が成り立つ分散システムの条件を検討する.CAP theorem proposed by Eric A. Brewer in 2000. CAP theorem tells that it is impossible for a distributed system to concurrently have the following three properties: consistency, availability, and partition-tolerance. In 2002, Seth Gilbert and Nancy Lynch proved this theorem. However, in their proof. they assumed as system always guarantee availability. Namely, they did not discuss that every distributed system held CAP theorem. Moreover, in many other studies, three properties were not given a clear definition and were discussed ambiguously. In this study, we gave these three properties mathematical definitions based on an adjacency matrix. Based on this, we conducted a simulation to verify whether CAP theorem holds in every distributed system. Finally, we discuss the requirement of a distributed system that satisfy CA, AP or CP.