On consistency of data in structured overlay networks

QC 20111020
Data consistency can be violated in Distributed Hash Tables (DHTs) due to inconsistent lookups. In this paper, we identify the events leading to inconsistent lookups and inconsistent responsibilities for a key. We find the inaccuracy of failure detectors as the main reason for inconsistencies. By simulations with inaccurate failure detectors, we study the probability of reaching a system configuration which may lead to inconsistent data. We analyze majority-based algorithms for operations on replicated data. To ensure that concurrent operations do not violate consistency, they have to use non-disjoint sets of replicas. We analytically derive the probability of concurrent operations including disjoint replica sets. By combining the simulation and analytical results, we show that the probability for a violation of data consistency is negligibly low for majority-based algorithms in DHTs.

Moser, Monika (författare)
Ghodsi, Ali (författare)
Schuett, Thorsten (författare)
Haridi, SeifKTH,Programvaru- och datorsystem, SCS(Swepub:kth)u1j6y2uf (författare)
Reinefeld, Alexander (författare)
KTHElektronik- och datorsystem, ECS (creator_code:org_t)

Av författaren/redakt...: Shafaat, Tallat ...; Moser, Monika; Ghodsi, Ali; Schuett, Thorste ...; Haridi, Seif; Reinefeld, Alexa ...

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.