Abstract

The prevailing model for digital preservation is that archives should be similar to a “fortress”: a large, protective infrastructure built to defend a relatively small collection of data from attack by external forces. Such projects are a luxury, suitable only for limited collections of known importance and requiring significant institutional commitment for sustainability. In previous research, we have shown the web infrastructure (i.e., search engine caches, web archives) refreshes and migrates web content in bulk as side-effects of their user-services, and these results can be mined as a useful, but passive preservation service. Our current research involves a number of questions resulting from removing the implicit assumption that web-based data objects must passively await curatorial services: What if data objects were not tethered to repositories? What are the implications if the content were actively seeking out and injecting itself into the web infrastructure (i.e., search engine caches, web archives)? All of this leads to our primary research question: Can we create objects that preserve themselves more effectively than repositories or web infrastructure can?

H.3.7 Digital Libraries Algorithms, Design, Experimentation

1 Introduction

In previous research, we have investigated alternative models for preservation, including how the web infrastructure (search engine caches, web archives, and other projects that refresh and migrate web resources) can be used to reconstruct “lost” web sites [20] as well as discover new and similar web pages [15], and how web servers could play a role in preparing “preservation-ready” resources [30]. In the attempt to explore additional models, we are currently researching the technologies necessary to create web-based digital objects that can be imbued with the capability to outlast their individual or organizational stewards. While conventional repository and preservation techniques will continue to be appropriate for collections of objects of known value, we are interested in techniques that can be applied for the large mass of web content that may become valuable in the future, or even content that a third party can deem valuable and worthy of preservation.

This work builds on our earlier research of “buckets” [22], which are based on the digital objects (DOs) first introduced in the Kahn Wilensky Framework [14], but with the internal capability to perform functions normally reserved for repositories. While the original implementations were based on server-side web programs, we envision future implementations taking advantage of client-side technologies such as JavaScript or Adobe Flash. In addition, the OAI-ORE project [18] has introduced Resource Maps, which are suitable for defining the boundaries of DOs. The combination of client-side scripting and Resource Maps has been explored; we will build on some of the concepts introduced in client-side preservation research [21]. Our interest in self-preserving DOs is spurred by the emergence of these technologies as well as the proliferation of free storage in the web infrastructure. This paper introduces the motivation for and scenarios describing how self-preserving DOs could be deployed as well as some preliminary discussions about how the DOs can arrange themselves, without archivist intervention, into small-world graphs in the web.

2 Related Work

2.1 Repositories

There are a number of repositories that range from theoretical to ready-to-download. Some are frameworks or architectural proposals such as aDORe [32] and SAV [6]. Some, like Fedora [25], are middleware systems, ready to be the core repository technology in a local deployment. Some are complete systems, ready to deploy. These include DSpace [31], sponsored by MIT and HP Laboratories, and LOCKSS [19], sponsored by the Stanford University Libraries. All are widely implemented and enjoy a large user community. DSpace is an institutional repository, intended to archive the intellectual output of a university’s faculty and students. LOCKSS allows libraries to create “dark archives” of publishers’ websites. As long as the publishers’ websites are available, all web traffic goes to those sites. But if the publishers’ contents are lost, the dark archives are activated and the content is available again. Risk is mitigated through many sites archiving content of their own choosing. Depending on an institution’s requirements, the systems described above can be quite attractive. But there is an implicit assumption on any repository system: that there is a person, community or institution that exists to tend to the repository. What happens when the responsible organization no longer exists? There are repository trading and synchronization provisions (e.g., [7]), but most are specific to a particular repository architecture.

Moving away from institution-centric repositories, several generic network storage systems and APIs have also been proposed, including Cooperative File Systems (CFS) [8], Internet Backplane Protocol (IBP) [3], Storage Resource Broker (SRB) [26] and OceanStore [29]. Systems such as CFS and OceanStore rely on distributed hash tables and an overlay network to locate content in the Internet. Such additional levels of shared infrastructure have not been widely deployed, and are not in use in any institutional repository. IBP and SRB are more traditional in their repository design and have enjoyed greater deployment. SRB (and its follow-on, iRODs) in particular has a user community similar in size to LOCKSS and Fedora.

2.2 Graph construction

Our approach for the construction of networks of DOs contrasts with others [24] where connections to other nodes are proportional to the destination’s degree count. We can use preferential attachment only to select the first node when starting to consider connecting to any nodes as compared with algorithms that starts with a graph (or lattice) and then grows a “small world” by the addition of new links [10, 12, 9, 16]. Or, by connecting a node to a fixed number of vertices based on their degree [4], or even creating a small world graph from a random one [11], whereas we construct a small world one from the beginning. Some approaches grow a graph based on preferential attachment (or “fitness”) [17, 2]. A survey of small world graph construction techniques and analysis is given [23], but none discuss the creation of small world graphs based on locally gleaned knowledge in a manner that we demonstrate.

3 Self-Preserving Digital Objects

3.1 Flocking for Preservation

We are motivated by Reynolds’s seminal paper on “boids” [28], in which he demonstrated that three simple rules were sufficient to simulate the complex behaviors of schools of fish, flocks of birds, herds of animals and the like. The rules themselves are simple, but the behaviors that emerge from the rules are complex and realistic. The salient feature is that these rules are scale-free: only the neighbors are accounted for in the computation; knowing the entire size of the network is not required. We believe these simple rules can be adapted to create self-preserving digital objects with similar complex emergent behaviors. Table 1 lists the rules that Reynolds proposed for boids (his term for bird-like objects) and our interpretation for DOs.

Table 1: Original Flocking Rules and DOs Flocking Rules.

In the same way that flocks self-navigate to new locations that have the resources they need, we envision collections of archival data objects self-preserving, using a loose confederation of cooperating archives with varying levels of resources and availability. Making copies of oneself in new repositories is performed in an opportunistic model, within the guidelines imbued in the DOs at creation time. Also, the entire collection (or parts of it) may be steered from time to time by an archivist, but for the most part the data objects replicate themselves.

Collision avoidance is perhaps the easiest rule to visualize the transcription from boids to DOs. DOs flocking to a new repository cannot overwrite each other (collide in physical storage), nor collide in namespaces (have the same URI). This is orthogonal to the naming mechanism used: URN implementations such as handles or DOIs, globally unique identifiers (GUIDS) or content addressable naming schemes [27].

With boids, the concept of velocity matching is to travel the same speed as your neighbors. This is perhaps the most difficult rule transformation. However, interpreting velocity as resource consumption (i.e., storage space) makes this rule more intuitive. Specifically, a DO should try to consume as much, and only as much, storage as everyone else. In resource-rich environments, making as many copies of yourself as you would like is easy. When storage becomes scarce, this becomes more difficult. So there must be a provision for DOs to delete copies of themselves from different archives to make room for late arriving DOs in low-storage situations. DOs will never delete the last copy of themselves to make room for new DOs, but they will delete copies of themselves to come down from a soft threshold (e.g., 10 copies) down to a hard threshold (e.g., 3). When resources become plentiful again, new copies can be made.

For boids, flock centering means staying near (but not colliding with) other flockmates. We interpret this similarly, with DOs attempting to stay near other DOs as they make copies of themselves at new repositories. In essence, when a DOs learns of a new repository and makes a copy of itself there, it should tell the other DOs it knows so they will have the opportunity to make copies of themselves at the new location if they wish. Announcing the location of a new repository will thus cause DOs at other repositories that have not reached their upper limit on creating copies to flow to the new repository.

3.2 Unsupervised Small-World Graph Creation

We introduce some terminology to discuss how DOs can self-arrange. Friends are DOs are within a graph. The nodes are directly connected to particular DO are considered its friends. A Family is all DOs that are replicas of each other. A Parent is the family member that was first inserted into the graph and is responsible for ensuring that enough family members are created to meet its preservation goals.

Based on a review of graph structures, their characteristics and attributes, small world graphs appear to be the most practical choice for minimizing a graph’s size, communication costs and construction effort. Small world graphs also emulate natural processes and occur often in nature and human endeavors, where regular and random graphs are relatively infrequent.

A “wandering” node is introduced to an existing node in the web. The wanderer gets a list of friends from the node it is introduced to. If the wandering node does not form a friendship link with the initial node, it will select another candidate node that it has learned of from all its conversations with other nodes it has encountered. When the wandering node finally makes a friendship link, it will then look back at all the nodes that it did not connect with as well as some that it was intending to communicate with and make friendship links with some of them.

Friendship links are separate from HTML navigation links (i.e., link instead of a HTML elements). These links serve as a way for DOs to send messages from one to another, such as when new storage locations are available or message concerning the scope and migration of file formats (cf. the semi-automated alert system described in Panic [13]). Friendship links are used to support the replication process. If a DO needs to replicate itself and it has a friend that lives on a different host and if there is room on that host for an additional DO then the DO can replicate itself onto the new host. Replication is how a family grows from a single copy (a parent) to multiple copies (a family). The friendship links, family links and how family members are spread across various hosts are shown in Figure 1.

(a) DO friends and friendship links are shown as solid black lines.
(b) DO friends and hosts. Hosts are shown as solid blue ovals.
(c) DO friends, families and hosts. Family links are shown as dashed red lines.
Figure 1: A layering of DO friends, hosts and families. A DO has many friends and lives on a host. Each family member lives on a different host.

4 Future Work and Conclusions

Our investigations to date have focused on developing the concept of constructing a small-world graph for preservation purposes based on locally available data. One of the next areas that we will focus on is the error and attack tolerance (cf. [1]) of the USW. An error is an unintended failure of a network component, where an attack is an intended failure:

Loss of a parental DO: A parental DO has special responsibilities with regard to the creating and distributing preservation copies and so is important to the well being of the family. When a parental DO is lost, a replacement must be selected from all remaining family members. There are a number of distributed election algorithms, including bullying and ring, that could be used to elect a new parent that would assume all parental duties.

Loss of a host: This would probably result in the loss of several nodes and preservation copies from the graph. For those families that lost a parental DO, the general approach from the previous bullet would apply. Loss of preservation copies would be resolved during routine family maintenance.

Disconnection of the graph: This is a major event and could be the result of the failure of a underlying hardware infrastructure or a concerted attack and can be characterized as the loss of many hosts simultaneously. Parental election would occur to replace lost parental DOs, concurrently with the creation of replacement preservation copies to bring the remaining families up to their directed levels.

Reconnection of the graph: Reconnection could bring multiple copies of the same family (one in each of the previously disconnected graphs) back into contact. As these families make contact, they could engage in an election process to select the truest parental node. The newly elected parent would then set about managing its preservation copies.

We have run extensive simulations to determine the parameters needed for DOs to create a “small world” graph based on purely locally derived information and without any global knowledge, guidance or direction using our unsupervised small world (USW) algorithm in a simulation environment (the algorithm and results are detailed in [5]). Next, we will implement the USW using client-side approaches such as JavaScript or Adobe Flash, combined with ORE Resource Maps to define the boundaries of the DO.

5 Acknowledgements

This work supported in part by the NSF, Project 370161.

References