Vis enkel innførsel

dc.contributor.advisorBratsberg, Svein Eriknb_NO
dc.contributor.authorJohnsen, Stein Eldarnb_NO
dc.date.accessioned2014-12-19T13:33:17Z
dc.date.available2014-12-19T13:33:17Z
dc.date.created2010-09-03nb_NO
dc.date.issued2005nb_NO
dc.identifier348139nb_NO
dc.identifierntnudaim:1096nb_NO
dc.identifier.urihttp://hdl.handle.net/11250/251038
dc.description.abstractThis thesis was written by Stein Eldar Johnsen beginning 15th August 2003 and delivered by 1st September 2005 with Svein Erik Bratsberg as mentor. The main topics are consistency and distributed hash tables. One unsolved problem with distributed hash tables is consistent lookup. Various DHTs can show acceptable consistency ratings, but no DHT can show no lookup inconsistency during churn. We chose to use a structural prevention strategy to remove inconsistent lookup on the basis that inconsistent lookups are a result of inconsistency in routing tables. We define consistent lookup as a lookup that returns a correct membership state from some time during lookup. Churn and especially unplanned membership changes may cause series of inconsistency problems if not handled carefully. The combination of a planned membership change (e.g. join) and an unplanned membership change (e.g. node crash causing a node to leave) can cause problems needing careful repairing in the systems routing tables. Table changes are necessary done in an order that guarantees a consistent view over index ownership, and makes the possibility of consistent termination at any point during execution. Other novel solutions include fail-fast disconnected-detection, locking membership protocols and pre-join knowledge propagation. All these solutions are shown to improve consistency through analysis, and are easily adapted for ring geometry DHTs. Accord was design to test many of the proposals made in the analysis. We built a distributed hash table infrastructure (with no hash table functionality), that used membership protocols based on the analysis results. The two main membership protocols were based on a 2-level 2-phase commit protocol for join, and simple 2-phase commit with distributed operations from a single coordinator for the leave protocol. The solutions proposed in this thesis are fit for all ring geometry DHTs, and some may be adapted for tree geometry DHTs, and some for all DHTs. All of Chord, Bamboo andPastry are good DHTs that can be used for testing the proposals, where all or most solutions are shown to be possible. Future work includes more testing, simulations and analysis of adaptations for different geometries.nb_NO
dc.languageengnb_NO
dc.publisherInstitutt for datateknikk og informasjonsvitenskapnb_NO
dc.subjectntnudaimno_NO
dc.subjectMIT informatikkno_NO
dc.subjectSystemarbeid og menneske-maskin-interaksjonno_NO
dc.titleConsistent Lookup during Churn in Distributed Hash Tablesnb_NO
dc.typeMaster thesisnb_NO
dc.source.pagenumber57nb_NO
dc.contributor.departmentNorges teknisk-naturvitenskapelige universitet, Fakultet for informasjonsteknologi, matematikk og elektroteknikk, Institutt for datateknikk og informasjonsvitenskapnb_NO


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel