Data Reconciliation in DHT Networks

  • Vidal Martins PUCPR
  • Esther Pacitti University of Nantes

Resumo


Optimistic replication can provide high data availability for collaborative applications in large scale distributed systems (grid, P2P, and mobile systems). However, if data reconciliation is performed by a single node, data availability remains an important issue since the reconciler node can fail. Thus, reconciliation should also be distributed and reconciliation data should be replicated. We have previously proposed the DSR-cluster algorithm, a distributed version of the IceCube semantic reconciliation engine designed for cluster networks. However DSR-cluster is not suitable for P2P networks, which are usually built on top of the Internet. In this case, network costs must be considered. The main contribution of this paper is the DSR-P2P algorithm, a distributed reconciliation algorithm designed for P2P networks. We first propose a P2P-DHT cost model for computing communication costs in a DHT overlay network. Second, taking into account this model, we propose a cost model for computing the cost of each reconciliation step. Third, we propose an algorithm that dynamically selects the best nodes for each reconciliation step. Our algorithm yields high data availability with acceptable performance and limited overhead.

Referências

Aberer, K., Cudré-Mauroux, P., Datta, A., Despotovic, Z., Hauswirth, M., Punceva, M., and Schmidt, R. P-Grid: A Self-organizing Structured P2P System. ACM SIGMOD Record 32(3), 2003.

BRITE, http://www.cs.bu.edu/brite/.

Clarke, I., Miller, S., Hong, T.W., Sandberg, O., and Wiley, B. Protecting Free Expression Online with Freenet. IEEE Internet Computing, 6(1), 2002.

Howell, F. and McNab, R. SimJava: a discrete event simulation package for Java with applications in computer systems modeling. In Web-based Modeling and Simulation, 1998.

Huebsch, R., Hellerstein, J. M., Lanham, N., Stoica, I., Loo, B. T., and Shenker, S. Querying the Internet with PIER. Proc. of VLDB Conference, 2003.

Kermarrec, A-M, Rowstron, A, Shapiro, M and Druschel P. The IceCube approach to the reconciliation of diverging replicas. Proc. of ACM PODC, 2001.

Knezevic, P., Wombacher, A., and Risse, T. Enabling High Data Availability in a DHT. Proc. of GLOBE, 2005.

Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., Weimer, W., Wells, C., and Zhao, B. Ocean-Store: An Architecture for Global-Scale Persistent Storage. Proc. of ASPLOS, 2000.

Martins, V., Pacitti, E., and Valduriez, P. A Dynamic Distributed Algorithm for Semantic Reconciliation. Distributed Data & Structures 7 (WDAS), 2006.

Martins, V., Pacitti, E., and Valduriez, P. Distributed Semantic Reconciliation of Replicated Data. Proc of CDUR, 2005.

Pacitti, E. and Dedieu, O. Algorithms for optimistic replication on the Web. Journal of the Brazilian Computing Society, 8(2), 2002.

Pacitti, E. and Simon, E. Update propagation strategies to improve freshness in lazy master replicated databases. The VLDB Journal, 8(3-4), 2000.

Preguiça, N, Shapiro, M and Matheson, C. Semantics-based reconciliation for collaborative and mobile environments. Proc. of IFCIS CoopIS, 2003.

Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Shenker, S. A scalable content-addressable network. Proc. of ACM SIGCOMM, 2001.

Saito, Y. and Shapiro, M. Optimistic Replication. ACM Computing Surveys, 37(1), 2005.

Stoica, I, Morris, R, Karger, D. R, Kaashoek, M. F and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for internet applications. Proc. of ACM SIGCOMM, 2001.

Whittaker, S., Issacs, e., and O’Day, V. Widening the Net: Workshop report on the theory and practice of physical and network communities. ACM SIGCHI Bulletin, 29(3), 1997.
Publicado
29/05/2007
Como Citar

Selecione um Formato
MARTINS, Vidal; PACITTI, Esther. Data Reconciliation in DHT Networks. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 8. , 2007, Belém/PA. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2007 . p. 15-26. ISSN 2595-2684. DOI: https://doi.org/10.5753/wtf.2007.23236.