Self-Maintaining Overlay Data Structures for Autonomic Distributed Computing

In our research, we developed a general framework to model and implement overlay data structures in dynamic network environments. Overlay data structures can be defined by means of a couple (C,P). The content C can be an arbitrary data structure representing the information carried on by the data structure. The propagation rule P determines how the overlay data structure should be distributed and propagated across the network. This includes determining the "scope" of the overlay (i.e. the distance at which it should be propagated and possibly the spatial direction of propagation) and how such propagation can be affected by the presence or the absence of other data structures in the system. In addition, the propagation rules can determine how the content should change while it is propagated. Overlay data structure are not necessarily distributed replicas: by assuming different values in different nodes, they can be effectively used to build a distributed overlay data structure expressing some kind of contextual information. In addition, we realized highly scalable, autonomic maintenance mechanisms to let the overlay data structures preserve its intended distribution (C,P) despite network contingencies