On consistency of data in structured overlay networks
2008 (English)In: GRID COMPUTING: ACHIEVEMENTS AND PROSPECTS / [ed] Gorlatch, S; Fragopoulou, P; Priol, T, NEW YORK: SPRINGER , 2008, 249-260 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
NEW YORK: SPRINGER , 2008. 249-260 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-38655DOI: 10.1007/978-0-387-09457-1_21ISI: 000258329500021ISBN: 978-0-387-09456-4OAI: oai:DiVA.org:kth-38655DiVA: diva2:450228
CoreGRID Integration Workshop 2008, Hersonissos, GREECE, APR 02-04, 2008
QC 201110202011-10-202011-08-312011-10-20Bibliographically approved