Distributed Data and Structures Records of the 1st International Meeting Introduction This volume contains the records of the research meeting on Distributed Data and Structures. Currently, the research on distributed data structures is carried out in many fields, from parallel systems to distributed computing, from AI to GIS. Their systematic design and analysis has just started: in the database literature, dynamic file structures for distributed object management have attracted some attention, and in the algorithms literature, data structures have been studied from a complexity oriented point of view. However, this research is mostly ``hidden,'' relegated to the side of each field, obscured by the weight of the application domain, especially in databases but also in the algorithms community. In fact, there is not even a definitive acceptance of its existence as a research field. This is surprising, especially in the light of the following two important developments. As databases are growing steadily, applications become more and more demanding, and distributed computer systems are becoming rather easily available, the problem of how to efficiently maintain large datasets gains importance. An important aspect of this problem is the design, implementation, and operation of a data structure in a distributed system. At the same time, in the constantly expanding net-centric universe, an increasing amount of data is available, distributed among sites. The structuring of the data for accessing, manipulation and processing is a crucial task which can ultimately affect the performance, integrity and usefulness of the entire system. These two developments bring the research on distributed data and structures at the forefront. The absence of a specific focus on this subject is an anomaly in the status of the current research efforts; at the same time, this situation opens an exceptional opportunity for researchers. The meeting on Distributed Data and Structures was held in Orlando, Florida, in conjunction with IPPS/SPDP. The purpose of this meeting has been to bring together application-oriented developers and theoretical researchers concerned with the maintenance of distributed data and the organization of the interaction among computing nodes, as well as researchers from different but related backgrounds. The goal has been to ``define'' the field across all the application areas, to assess and characterize the common elements in all the uncoordinated research efforts which have been carried out in so many different domains, to ``visualize'' the field with respect to new computing paradigms (e.g., mobile, wireless, etc.). The meeting has been successful in both respects. It comprised both formal presentations, whose goal was to give a picture of some aspects of the field, and open time and space to discuss, analyze, and characterize the many facets of the field. The topics covered include: design, implementation, and operation of distributed data structures efficiency measures for distributed data structures; complexity analysis (lower and upper bounds) for distributed data structures; analysis of distributed structures (distributed token, mutual exclusion, counter); processing and manipulation of distributed data; connection between communication structure and data maintenance; mobile data maintenance. This volume is based entirely on the talks, discussions, and results of the meeting. Its small size is due to the fact that most of the contributions came as discussion and have not yet found their form as a written text. Still, we hope this volume will convey to the reader at least part of the interest, excitement and visions experienced by the participants. We are confident it will provide useful tools for a unified view of this emerging research area, so important from both an applicative and a theoretical viewpoint. We would like to thank: all the participants to the meeting for their enthusiasm and contributions; all the researchers who, although unable to attend, have expressed their strong support for the meetings goals and future; Konrad Schlude for the excellent organizational work; the IPPS/SPDP Workshop Chair, Jose Rolim, for inviting our meeting to come to life, and providing us with the IEEE organizational support; and Steve Izma of Carleton Scientific for the unusual editorial effort. We also gratefully acknowledge the support of the two parent institutions: Carleton University and ETH Zurich. Nicola Santoro and Peter Widmayer Table of Contents Elena Lodi, Linda Pagli, and Nicola Santoro Introduction Aviezri S.\ Fraenkel Heap Games, Numeration Systems and Sequences A. Daurat, Y. Gérard, and M. Nivat The Chords' Problem R. Fleischer FUN with Implementing Algorithms S. Seiden Making the Analysis of Complicated Algorithms Fun:\\ A Manifesto for the Computational Method Ronald Becker, Bruno Simeone, and Yen-I Chiang How to Make a Polynomial Movie from Pseudopolynomially Many\\ Frames: A Continuous Shifting Algorithm for Tree Partitioning H. Shachnai, T. Tamir Noah's Bagels - Combinatorial Aspects A. Blum, P. Raghavan A Theory of Computing Symposia D. Merlini, R. Sprugnoli, M. C. Verri A Strip-like Tiling Algorithm P. Boldi, M. Santini, and S. Vigna Measuring With Jugs M. Bern, E. Demaine, D. Eppstein, and B. Hayes A Disk-Packing Algorithm for an Origami Magic Trick E. Sutinen, W. Szpankowski On the Collapse of the $q$-Gram Filtration Joseph Culberson Sokoban is PSPACE-complete A. Pedrotti Searching with a Constant Rate of Malicious Lies A. L. Rosenberg A Model for Cycle-Stealing in Networks of Workstations:\\ Progress and Problems David Peleg Algorithmic Aspects of Dynamic Coalitions and Monopolies in Graphs