Carleton Scientific 2006-07-25 Carleton-Scientific home page How to reach us Ordering information

Distributed Data and Structures Records of the 6th International Meeting Introduction Since its inception in 1998, the Workshop on Distributed Data and Structures (WDAS) has brought together researchers from various areas of computer science to discuss and exchange ideas in this domain. The idea was to shed light on large-scale data structures and their use from different perspectives in computer science research to get a sharper view of the basic problems and thus to benefit from the synergies of different research efforts. It is interesting to note, that soon after WDAS was born, the huge success of peer-to-peer file sharing systems has shown the need for large scale-distributed data and structures and to a certain extent WDAS has played a bit of a precursor role here. While in the beginning the interdisciplinary research in P2P was not a central issue, it has by now become clear as a necessity which again affirms the original motivation of WDAS. This volume contains the post-proceedings of the sixth WDAS which was held at the Ecole Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland. Previous workshops took place in Orlando (1998), Princeton (1999), L’Aquilla (2000), Paris (2001), and Thessaloniki (2003). WDAS’04 again brought together researchers from various fields and gave them the opportunity to discuss the state-of-the-art. The workshop program was composed around the following areas: Semantics in peer-to-peer systems Distributed query processing Maintenance of peer-to-peer systems Content distribution Design and implementation of scalable distributed data structures Naturally, many of the presentations and discussions circulated around the peer-to-peer domain, as it is seen as a hot research topic at the moment. The workshop started with a day of presentations and offered plenty of opportunities for the attendees to discuss the presented work, ongoing work, and new ideas. The second day started with a keynote talk by Prof. Dahlia Malkhi (The Hebrew University of Jerusalem) on locality-aware network solutions in which she gave an overview of the fundamental principles, limitations, and practical deployment issues related to overlay networks and then focused on the specific problems of locality in large-scale distributed systems to provide optimal routing algorithms which take into account some notion of “proximity.” This volume is based on revised versions of the original papers presented at the workshop. The authors where given the opportunity to improve their work by taking into account the discussions and the feedback they received at the workshop. The selection of papers for this volume was based on anonymous feedback from the WDAS participants. We would like to thank all participants for their lively participation which resulted in interesting and high-quality discussions and the members of the Distributed Information Systems Lab of EPFL for their excellent work in providing administrative and organizational support to make WDAS’04 a successful and interesting event. Karl Aberer & Manfred Hauswirth, EPFL Program Committee Karl Aberer, EPFL Lausanne, Chair Luc Onana Alima, KTH Stockholm Panayiotis Bozanis, University of Thessaly Klemens Böhm, University of Magdeburg Yuri Breitbart, Bell Labs Pascal Felber, Eurecom Shahram Ghandeharizadeh, University of Southern California Manolis Koubarakis, TU Crete Witold Litwin, University Paris 9, Dauphine Dahlia Malkhi, The Hebrew University of Jerusalem Yannis Manolopoulos, Aristotle University Ethan Miller, University of California, Santa Cruz Enrico Nardelli, University of L’Aquila Beng Chin Ooi, University of Singapore Aris Ouksel, University of Chicago Jehan-Francois Pâris, University of Houston Evaggelia Pitoura, University of Ioannina Tore Risch, University of Uppsala Tomas Schwarz, Santa Clara University Ugo Vaccaro, University of Salerno Patrick Valduriez, University of Paris 6 Peter Widmayer, ETHZ Zürich Organizing Committee Manfred Hauswirth, EPFL Lausanne, Chair Chantal Menghini, EPFL Lausanne Magdalena Punceva, EPFL Lausanne Natascha Fontana, EPFL Lausanne Table of Contents Karl Aberer & Manfred Hauswirth Introduction Theodora Dariotaki & Alex Delis Detecting Reputation Variations in P2P Networks R. Akbarinia, V. Martins, E. Pacitti, & P. Valduriez Replication and Query Processing in the APPA Data Management System Kai-Uwe Sattler, Philipp Rösch, Erik Buchmann, & Klemens Böhm A Physical Query Algebra for DHT-based P2P Systems M. S. Manasse, C. A. Thekkath, A. Silverberg A Reed-Solomon Code for Disk Storage, and Efficient Recovery Computations for Erasure-Coded Disk Storage Q. Xin, T. Schwarz, & E. Miller Availability in Global Peer-To-Peer Storage Systems Karl Aberer, Anwitaman Datta, & Manfred Hauswirth Route Maintenance Overheads in DHT Overlays Danny Bickson, Dahlia Malkhi, & David Rabinowitz Efficient Large Scale Content Distribution Christos Tryfonopoulos & Manolis Koubarakis Publish/Subscribe Systems with Distributed Hash Tables and Languages from IR Adriano Di Pasquale, Enrico Nardelli, & Guido Proietti A Lower Bound for the DRT* with Complete Correction Technique T. Schwarz & J. Holliday A Signature-Based Concurrency Scheme for Scalable Distributed Data Structures S. Sahri, W. Litwin Implementing SD-SQL Server: a Scalable Distributed Database System R. Moussa & T. Schwarz Design and Implementation of LH*RS: A Highly Available Data Storage System