Paxos (computer science) (original) (raw)
En informatique distribuée, Paxos est une famille de protocoles permettant de résoudre le consensus dans un réseau de nœuds faillibles, c'est-à-dire susceptible d'avoir des pannes. Le consensus désigne ici le fait que les différents nœuds se mettent d'accord sur un résultat, et c'est une opération difficile quand les nœuds ou leurs moyens de communications ont des pannes.
| Property | Value |
|---|---|
| dbo:abstract | Paxos ist eine Gruppe von Protokollen mit dem Ziel, einen Konsensus in einem Netzwerk von unzuverlässigen Prozessoren zu erzielen. Konsensus bezeichnet hierbei die Übereinstimmung auf ein gemeinsames Ergebnis in einer Gruppe von Teilnehmern. Die Lösung dieses Problems kann erschwert werden, wenn bei den Teilnehmern oder ihrem Kommunikationsmedium Fehler auftreten. Konsensusprotokolle sind in Verteilten Systemen die Grundlage für die Herangehensweise mittels Zustandsmaschinen, vorgeschlagen von Leslie Lamport und begutachtet von . Das Paxos-Protokoll wurde erstmals im Jahr 1989 als Journalartikel veröffentlicht und nach einem fiktionalen legislativen Konsensussystem benannt, das auf der Insel Paxos in Griechenland verwendet wurde. Paxos geht verschiedene Kompromisse bezüglich der Anzahl an Prozessoren, der Anzahl an Nachrichtenverzögerungen vor dem Lernen des vereinbarten Wertes, des Aktivitätslevels der einzelnen Teilnehmer, der Anzahl an versandten Nachrichten und den Fehlertypen ein. Obwohl kein deterministisches fehlertolerantes Konsensusprotokoll Fortschritt in einem asynchronen Netzwerk garantieren kann (dies wurde in einem wissenschaftlichen Artikel von Fischer, Lynch und Paterson bewiesen), garantiert Paxos Konsistenz, und die Bedingungen, die einen Fortschritt verhindern könnten, sind schwierig herbeizuführen. Paxos wird üblicherweise wegen seiner Robustheit eingesetzt (zum Beispiel zur Replikation einer Datei oder einer Datenbank). Das Protokoll versucht sogar dann Fortschritt zu erzielen, wenn Phasen auftreten, in denen eine begrenzte Anzahl von Replikaten nicht ansprechbar sind. Außerdem besitzt Paxos einen Mechanismus, um permanent fehlerhafte Replikate zu entfernen oder neue hinzuzufügen. (de) El algoritmo de Paxos es un algoritmo para llegar a consensos en sistemas distribuidos con cierto grado de tolerancia a fallos. Entendemos consenso como el proceso de ponerse de acuerdo sobre uno de los resultados entre un grupo de participantes. Este problema se hace difícil cuando los participantes o su medio de comunicación puede experimentar fallos. El protocolo Paxos primero fue publicado en 1989 por Leslie Lamport aunque pasó desapercibido hasta 1998 cuando lo publicó en una revista especializada. Desde entonces se han publicado varias mejoras y adaptaciones. El algoritmo incluye una gama de soluciones de compensación entre el número de procesos, el número de mensajes con retraso antes de aprender el valor acordado, el nivel de actividad de los participantes, el número de mensajes enviados, y los tipos de fallos. Aunque un protocolo de consenso con tolerancia a fallos determinista no puede garantizar el progreso en una red asíncrona, Paxos garantiza la seguridad (libre de inconsistencia), y las condiciones que podrían hacer que no progrese son difíciles de ocurrir. Funciona en el modelo de paso de mensajes con asincronía y con menos n/2 fallos (pero no con fallos bizantinos). El algoritmo de Paxos garantiza que se llegará a un acuerdo y garantiza la finalización si hay un tiempo suficientemente largo sin que ningún proceso reinicie el protocolo. (es) Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors.Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures. Consensus protocols are the basis for the state machine replication approach to distributed computing, as suggested by Leslie Lamport and surveyed by Fred Schneider. State machine replication is a technique for converting an algorithm into a fault-tolerant, distributed implementation. Ad-hoc techniques may leave important cases of failures unresolved. The principled approach proposed by Lamport et al. ensures all cases are handled safely. The Paxos protocol was first submitted in 1989 and named after a fictional legislative consensus system used on the Paxos island in Greece, where Lamport wrote that the parliament had to function "even though legislators continually wandered in and out of the parliamentary Chamber". It was later published as a journal article in 1998. The Paxos family of protocols includes a spectrum of trade-offs between the number of processors, number of message delays before learning the agreed value, the activity level of individual participants, number of messages sent, and types of failures. Although no deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous network (a result proved in a paper by Fischer, Lynch and Paterson), Paxos guarantees safety (consistency), and the conditions that could prevent it from making progress are difficult to provoke. Paxos is usually used where durability is required (for example, to replicate a file or a database), in which the amount of durable state could be large. The protocol attempts to make progress even during periods when some bounded number of replicas are unresponsive. There is also a mechanism to drop a permanently failed replica or to add a new replica. (en) En informatique distribuée, Paxos est une famille de protocoles permettant de résoudre le consensus dans un réseau de nœuds faillibles, c'est-à-dire susceptible d'avoir des pannes. Le consensus désigne ici le fait que les différents nœuds se mettent d'accord sur un résultat, et c'est une opération difficile quand les nœuds ou leurs moyens de communications ont des pannes. (fr) Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる。 合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポートにより提案され、Fred Schneiderによってサーベイがなされている。 Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった。これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBarbara Liskovが発表したViewstampedレプリケーションにおける合意形成に使用されるプロトコルと非常に似ている。 状態機械アプローチとはアルゴリズムをフォールトトレラントな、分散した実装に変換する技法である。アドホックな技術では重要な障害ケースが未解決のままになる可能性がある。Lamport等によって定式化された手法では全てのケースが安全に処理されることを保証している。 Paxosプロトコル集合には次のものについてトレードオフを持っているような数種のものがある。 * プロセッサ数 * 合意された値を知るまでのメッセージ遅延 * 各ノードのアクティビティレベル * 送信されたメッセージ数 * 障害の種類 Paxosプロトコル集合の共通の特徴は、不整合な状態に陥らないということがある。 (ja) 팩소스(Paxos)는 신뢰할 수 없는 프로세서들의 네트워크에서 합의 문제를 해결하기 위한 프로토콜 그룹이다. 합의 문제는 구성원이나 구성원 간의 통신 매체에 장애가 발생할 수 있는 경우 어려워진다. 합의 프로토콜은 레슬리 램포트 에 의해 제안되고 에 의해 검증된 분산 컴퓨팅을 위한 상태 기계 접근법 기초이다. 상태 기계 접근법은 알고리즘을 장애 허용 분산 시스템에서 구현되도록 변환하는 기술이다. 애드혹 기법은 예상치 못한 중요한 실패 케이스를 남길 수 있다. 램포트와 그의 동료들에 의해 제안된 원칙적인 방법은 모든 경우가 안전하게 처리되는 것을 보장한다. 팩소스 프로토콜은 1989년에 처음으로 공개되었으며 그리스의 팩소스 섬에서 가상의 입법 합의 시스템에 사용된 후 이름지어졌다. 이후에 1998년에 저널 기사로 게재되었다. 팩소스 계열 프로토콜은 프로세서 수, 합의 값 (agreed value), 합의 값 학습 전까지의 메시지 지연, 개별 참여자의 활동 수준, 메시지 전송 횟수, 실패 종류 등을 트레이드 오프하는 것을 포함한다. Fischer, Lynch와 Paterson의 논문에 따르면 결정적 장애 허용 합의 프로토콜이 비동기 네트워크에선 진행을 보장하진 않지만, 팩소스는 안정성(consistency)을 보장하며 진행을 방해할 수 있는 조건이 발생하기 어렵다. 팩소스는 일반적으로 내구성이 요구되는 곳(예 : 파일 또는 데이터 베이스 복제하는 경우)에 쓰인다. 팩소스 프로토콜은 일정 수 이하의 복제본이 응답하지 않는 동안에도 진행을 시도한다. 또한 영구적으로 실패한 복제본을 제거하거나 새로운 복제본을 추가하는 메커니즘도 있다. (ko) Паксос (англ. Paxos) — семейство протоколов для решения задачи консенсуса в сети ненадёжных вычислителей. Консенсус — процесс получения согласованного результата группой участников, основная проблема — наличие помех в среде передачи данных. Данная задача используется, например, для утверждения транзакций в распределённых системах. Протоколы решения задачи консенсуса — базовый элемент автоматного подхода в распределённых вычислениях, предложенного Лесли Лампортом и исследованного далее Ф. Шнайдером. Автоматный подход — метод реализации алгоритма на распределённой системе, сохраняющий устойчивость к отказам. Это системный подход, не допускающий неосознанного внесения ошибок. Принципиальный подход Лампорта рассматривает все возможные случаи. Семейство протоколов Паксос было создано и описано в 1990 г., но было опубликовано в научной литературе только в 1998 г. Однако, исследования на данную тематику начались задолго до реализации протокола. Например, , подход к программированию на основе модели , предложенной в 1985 г. Семейство протоколов Паксос рассматривает варианты решения задачи консенсуса в зависимости от количества вычислителей, количества задержек для получения результата, активности участников, количества отправленных сообщений и типов отказов. Результат отказоустойчивого консенсуса не определён (то есть, при определённых условиях вычислители не смогут прийти к согласию), однако, гарантируется безопасность (консистентность), а условия, при которых консенсус невозможен, очень редки. (ru) Paxos算法是莱斯利·兰伯特（英語：Leslie Lamport，LaTeX中的「La」）于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。 需要注意的是，Paxos常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念。Paxos是一个共识（consensus）算法。 (zh) Паксос (англ. Paxos) — це набір протоколів, призначених для консенсусу в мережі ненадійних процесорів. Консенсус — процес отримання узгодженого результату групою учасників. Вирішити цю проблему складно, якщо в учасників або в засобах їх комунікації виникають помилки. Протоколи рішення задачі консенсусу є базовим елементом у розподілених обчисленнях, що запропонував Леслі Лампорт і дослідив далі Ф. Шнайдер. Протокол Паксос був вперше опублікований у 1989 році та був названий на честь вигаданої законодавчої системи, що застосовувалася на острові Паксос у Греції. Пізніше був опублікований в науковій літературі в 1998 році. Сімейство протоколів Паксос включає спектр компромісів між кількістю процесорів, кількістю затримок повідомлень, рівня активності окремих учасників та кількістю відправлених повідомлень. Результат відмовостійкого узгодження не визначений, однак умови, при яких консенсус неможливий, дуже рідкісні. Паксос зазвичай використовується, для копіювання файлу чи бази даних. Протокол намагається досягти прогресу навіть у періоди, коли деяка обмежена кількість вузлів не відповідає. Існує також механізм видалення або додавання нового вузла. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Basic_Paxos_without_failures.svg?width=300 |
| dbo:wikiPageExternalLink | http://GitHub.com/Derecho-Project http://www.wandisco.com/ http://research.google.com/archive/bigtable.html http://docs.clustrix.com/display/CLXDOC/Consistency,+Fault+Tolerance,+and+Availability http://libpaxos.sourceforge.net/ http://mpaxos.com/ http://www.fractalscape.org/2007/10/01/paxos-family.html http://www.lamport.org/ http://www.navigators.di.fc.ul.pt/software/jitt/jbp.html https://paxos.systems/ https://www.datastax.com/dev/blog/lightweight-transactions-in-cassandra-2-0 https://github.com/Tencent/paxosstore https://github.com/cocagne/paxos/ https://github.com/ha/doozerd https://github.com/solatis/libpaxos-cpp https://www.youtube.com/watch%3Fv=d7nAGI_NZPk http://citeseer.ist.psu.edu/viewdoc/summary%3Fdoi=10.1.1.44.5607 http://de.slideshare.net/jexp/new-neo4j-auto-ha-cluster%7CHA https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf https://www.allthingsdistributed.com/2015/07/under-the-hood-of-the-amazon-ec2-container-service.html http://isis2.codeplex.com http://research.microsoft.com/pubs/64604/osr2007.pdf http://research.microsoft.com/users/lamport/pubs/pubs.html%23paxos-commit http://research.microsoft.com/users/lamport/pubs/pubs.html%23paxos-simple https://arxiv.org/abs/1407.1237 https://web.archive.org/web/20160303212934/http:/ftfile.rodia.pl/ https://web.archive.org/web/20180809051426/http:/openreplica.org/ http://www.usenix.org/event/osdi08/tech/full_papers/mao/mao.pdf http://code.google.com/p/erlpaxos/ http://research.google.com/archive/chubby.html |
| dbo:wikiPageID | 5722488 (xsd:integer) |
| dbo:wikiPageLength | 68324 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120605099 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bigtable dbr:Paxi dbr:Byzantine_fault_tolerance dbr:Lorenzo_Alvisi dbr:Commutative dbr:Gbcast dbr:Mike_Paterson dbr:Virtual_synchrony dbr:Clustrix dbr:Fred_B._Schneider dbr:Nancy_Lynch dbr:Consensus_(computer_science) dbr:Apache_Cassandra dbr:Apache_ZooKeeper dbr:Leslie_Lamport dbr:Storage_virtualization dbr:Paxos_(computer_science) dbr:Barbara_Liskov dbc:Fault-tolerant_computer_systems dbr:Ceph_(software) dbr:WANdisco dbr:Distributed_computing dbr:Distributed_lock_manager dbr:Larry_Stockmeyer dbr:Cynthia_Dwork dbr:Dahlia_Malkhi dbr:Database dbr:Michael_J._Fischer dbr:Remote_direct_memory_access dbr:State_machine dbc:Distributed_algorithms dbr:Ken_Birman dbr:Lease_(computer_science) dbr:IBM_SAN_Volume_Controller dbr:If_and_only_if dbr:Neo4j dbr:Raft_(computer_science) dbr:Chandra–Toueg_consensus_algorithm dbr:XtreemFS dbr:State_machine_replication dbr:NAK_(protocol_message) dbr:Google_Spanner dbr:File:Dark_Red_x.svg dbr:File:Basic_Paxos_without_failures.svg |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Cquote dbt:How dbt:Mono dbt:Na dbt:Reflist dbt:Sources |
| dct:subject | dbc:Fault-tolerant_computer_systems dbc:Distributed_algorithms |
| gold:hypernym | dbr:Family |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatDistributedAlgorithms |
| rdfs:comment | En informatique distribuée, Paxos est une famille de protocoles permettant de résoudre le consensus dans un réseau de nœuds faillibles, c'est-à-dire susceptible d'avoir des pannes. Le consensus désigne ici le fait que les différents nœuds se mettent d'accord sur un résultat, et c'est une opération difficile quand les nœuds ou leurs moyens de communications ont des pannes. (fr) Paxos算法是莱斯利·兰伯特（英語：Leslie Lamport，LaTeX中的「La」）于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。 需要注意的是，Paxos常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念。Paxos是一个共识（consensus）算法。 (zh) Paxos ist eine Gruppe von Protokollen mit dem Ziel, einen Konsensus in einem Netzwerk von unzuverlässigen Prozessoren zu erzielen. Konsensus bezeichnet hierbei die Übereinstimmung auf ein gemeinsames Ergebnis in einer Gruppe von Teilnehmern. Die Lösung dieses Problems kann erschwert werden, wenn bei den Teilnehmern oder ihrem Kommunikationsmedium Fehler auftreten. Konsensusprotokolle sind in Verteilten Systemen die Grundlage für die Herangehensweise mittels Zustandsmaschinen, vorgeschlagen von Leslie Lamport und begutachtet von . (de) El algoritmo de Paxos es un algoritmo para llegar a consensos en sistemas distribuidos con cierto grado de tolerancia a fallos. Entendemos consenso como el proceso de ponerse de acuerdo sobre uno de los resultados entre un grupo de participantes. Este problema se hace difícil cuando los participantes o su medio de comunicación puede experimentar fallos. El protocolo Paxos primero fue publicado en 1989 por Leslie Lamport aunque pasó desapercibido hasta 1998 cuando lo publicó en una revista especializada. Desde entonces se han publicado varias mejoras y adaptaciones. (es) Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors.Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures. (en) 팩소스(Paxos)는 신뢰할 수 없는 프로세서들의 네트워크에서 합의 문제를 해결하기 위한 프로토콜 그룹이다. 합의 문제는 구성원이나 구성원 간의 통신 매체에 장애가 발생할 수 있는 경우 어려워진다. 합의 프로토콜은 레슬리 램포트 에 의해 제안되고 에 의해 검증된 분산 컴퓨팅을 위한 상태 기계 접근법 기초이다. 상태 기계 접근법은 알고리즘을 장애 허용 분산 시스템에서 구현되도록 변환하는 기술이다. 애드혹 기법은 예상치 못한 중요한 실패 케이스를 남길 수 있다. 램포트와 그의 동료들에 의해 제안된 원칙적인 방법은 모든 경우가 안전하게 처리되는 것을 보장한다. 팩소스 프로토콜은 1989년에 처음으로 공개되었으며 그리스의 팩소스 섬에서 가상의 입법 합의 시스템에 사용된 후 이름지어졌다. 이후에 1998년에 저널 기사로 게재되었다. 팩소스는 일반적으로 내구성이 요구되는 곳(예 : 파일 또는 데이터 베이스 복제하는 경우)에 쓰인다. 팩소스 프로토콜은 일정 수 이하의 복제본이 응답하지 않는 동안에도 진행을 시도한다. 또한 영구적으로 실패한 복제본을 제거하거나 새로운 복제본을 추가하는 메커니즘도 있다. (ko) Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる。 合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポートにより提案され、Fred Schneiderによってサーベイがなされている。 Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった。これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBarbara Liskovが発表したViewstampedレプリケーションにおける合意形成に使用されるプロトコルと非常に似ている。 状態機械アプローチとはアルゴリズムをフォールトトレラントな、分散した実装に変換する技法である。アドホックな技術では重要な障害ケースが未解決のままになる可能性がある。Lamport等によって定式化された手法では全てのケースが安全に処理されることを保証している。 (ja) Паксос (англ. Paxos) — семейство протоколов для решения задачи консенсуса в сети ненадёжных вычислителей. Консенсус — процесс получения согласованного результата группой участников, основная проблема — наличие помех в среде передачи данных. Данная задача используется, например, для утверждения транзакций в распределённых системах. Протоколы решения задачи консенсуса — базовый элемент автоматного подхода в распределённых вычислениях, предложенного Лесли Лампортом и исследованного далее Ф. Шнайдером. (ru) Паксос (англ. Paxos) — це набір протоколів, призначених для консенсусу в мережі ненадійних процесорів. Консенсус — процес отримання узгодженого результату групою учасників. Вирішити цю проблему складно, якщо в учасників або в засобах їх комунікації виникають помилки. Протоколи рішення задачі консенсусу є базовим елементом у розподілених обчисленнях, що запропонував Леслі Лампорт і дослідив далі Ф. Шнайдер. (uk) |
| rdfs:label | Paxos (Informatik) (de) Algoritmo de Paxos (es) Paxos (informatique) (fr) 팩소스 (컴퓨터 과학) (ko) Paxosアルゴリズム (ja) Paxos (computer science) (en) Алгоритм Паксос (ru) Алгоритм Паксос (uk) Paxos算法 (zh) |
| owl:sameAs | freebase:Paxos (computer science) yago-res:Paxos (computer science) wikidata:Paxos (computer science) dbpedia-de:Paxos (computer science) dbpedia-es:Paxos (computer science) dbpedia-fr:Paxos (computer science) dbpedia-ja:Paxos (computer science) dbpedia-ko:Paxos (computer science) dbpedia-ru:Paxos (computer science) dbpedia-uk:Paxos (computer science) dbpedia-zh:Paxos (computer science) https://global.dbpedia.org/id/57aMS |
| prov:wasDerivedFrom | wikipedia-en:Paxos_(computer_science)?oldid=1120605099&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Basic_Paxos_without_failures.svg wiki-commons:Special:FilePath/Dark_Red_x.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Paxos_(computer_science) |
| is dbo:wikiPageDisambiguates of | dbr:Paxos_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Paxos_algorithm dbr:Paxos_distributed_consensus_algorithm dbr:Paxos_protocol |
| is dbo:wikiPageWikiLink of | dbr:Bigtable dbr:Gbcast dbr:Rachid_Guerraoui dbr:Raft_(algorithm) dbr:Timeline_of_algorithms dbr:Consensus_(computer_science) dbr:Apache_Cassandra dbr:Paxos_(computer_science) dbr:Paxos_(disambiguation) dbr:Data_synchronization dbr:WANdisco dbr:Distributed_SQL dbr:Aerospike_(database) dbr:Amazon_DynamoDB dbr:Brooks–Iyengar_algorithm dbr:Blockchain-based_database dbr:TLA+ dbr:Avalanche_(blockchain_platform) dbr:Byzantine_fault dbr:CAP_theorem dbr:Oracle_NoSQL_Database dbr:XtreemFS dbr:Shard_(database_architecture) dbr:NewSQL dbr:PACELC_theorem dbr:Vsync_(computing) dbr:YDB_(database) dbr:Paxos_algorithm dbr:Paxos_distributed_consensus_algorithm dbr:Paxos_protocol |
| is foaf:primaryTopic of | wikipedia-en:Paxos_(computer_science) |
