Hachage cohérent

Résumé

Le hachage cohérent est un type particulier de hachage. Lorsque la table de hachage change de taille et que le hachage cohérent est employé, seulement K/n clés ont besoin d’être redistribuées en moyenne, où K est le nombre de clés et n est le nombre d'éléments dans la table de hachage. En comparaison, dans une table de hachage classique, un changement dans le nombre d'éléments de la table a pour conséquence la réorganisation de l'ensemble ou presque des clés. Historique À l'origine conçue par Karger et coll. au Massachusetts Institute of Technology, afin d’être utilisée dans un système de cache distribué, cette notion est apparue dans d'autres domaines. Une publication dans un article de 1997 introduit le terme hachage cohérent comme un moyen de répartir les requêtes sur un ensemble de serveurs web en constante évolution. Chaque emplacement est représenté par un nœud d'un système réparti. L'ajout (arrivée), ou la suppression (départ

Source officielle

https://fr.wikipedia.org/wiki/Hachage_coh%C3%A9rent

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (12)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (4)

Une table de hachage distribuée (ou DHT pour Distributed Hash Table), est une technique permettant la mise en place d’une table de hachage dans un système réparti. Une table de hachage est une struc

Le pair-à-pair ou système pair à pair (en anglais peer-to-peer, souvent abrégé « P2P ») est un modèle d'échange en réseau où chaque entité est à la fois client et serveur, contrairement au modèle c

Quand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise un

Afficher plus

Concepts associés

Chargement

Cours associés (7)

Cours associés

Chargement

Séances de cours associées (12)

Séances de cours associées

Chargement

The Weakest Failure Detector for Eventual Consistency

Rachid Guerraoui, Pierre Sens

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. Assuming a message-passing environment with a majority of correct processes, the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the ω failure detector. This paper shows that in such a message-passing environment, ω is also the weakest failure detector to implement an eventually consistent replicated service, where replicas are expected to agree on the evolution of the service state only after some (a priori unknown) time. In fact, we show that ω is the weakest to implement eventual consistency in any message-passing environment, i.e., under any assumption on when and where failures might occur. Ensuring (strong) consistency in any environment requires, in addition to ω, the quorum failure detector Σ. Our paper thus captures, for the first time, an exact computational difference between building a replicated state machine that ensures consistency and one that only ensures eventual consistency. © Copyright 2015 ACM.

ACM Press2015

Chargement

The weakest failure detector for eventual consistency

Rachid Guerraoui, Pierre Sens

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. If we consider an asynchronous messagepassing environment in which processes might fail by crashing, and assume that a majority of processes are correct, then the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the Omega failure detector. This paper shows that in such a message-passing environment, Omega is also the weakest failure detector to implement an eventually consistent replicated service, where replicas are expected to agree on the evolution of the service state only after some (a priori unknown) time. In fact, we show that Omega is the weakest to implement eventual consistency in any message-passing environment, i.e., under any assumption on when and where failures might occur. Ensuring (strong) consistency in any environment requires, in addition to Omega, the quorum failure detector S. Our paper thus captures, for the first time, an exact computational difference between building a replicated state machine that ensures consistency and one that only ensures eventual consistency.

2019

Chargement

Orbe: Scalable Causal Consistency Using Dependency Matrices and Physical Clocks

Jiaqing Du, Sameh Mohamed Elnikety, Amitabha Roy, Willy Zwaenepoel

We propose two protocols that provide scalable causal consistency for both partitioned and replicated data stores using dependency matrices (DM) and physical clocks. The DM protocol supports basic read and update operations and uses two-dimensional dependency matrices to track dependencies in a client session. It utilizes the transitivity of causality and sparse matrix encoding to keep dependency metadata small and bounded. The DM-Clock protocol extends the DM protocol to support read-only transactions using loosely synchronized physical clocks. We implement the two protocols in Orbe, a distributed key-value store, and valuate them experimentally. Orbe scales out well, incurs relatively small verhead over an eventually consistent key-value store, and outperforms an existing system that uses explicit dependency tracking to provide scalable causal consistency.

2013

Chargement