Data Replication Support for Collaboration in Mobile and Ubiquitous Computing Environments

Introduction

Consider a team of co-workers that wishes to write a report in a collaborative fashion. For such a purpose, they create a document file, replicate it across the (possibly mobile) personal computers each colleague holds, and occasionally synchronize replicas to ensure consistency. Using a text editor, each worker is then able to read and modify her replica, adding her contributions asynchronously with the remaining colleagues. One may envision interesting scenarios of productive collaboration. A user may modify the report even while out of her office, replicated in a laptop or hand-held computer she carries while disconnected from the corporate wired network. Further, such a worker may meet other colleagues carrying their laptops with report replicas and, in an ad-hoc fashion, establish a short term work group to collaboratively work on the report.

Besides the shared document editing application, one may consider a wide range of other applications and systems; examples include asynchronous groupware applications (Wilson, 1991; Carstensen & Schmidt, 1999) such as cooperative engineering or software development (Cederqvist et al, 1993; Fitzpatrick et al., 2004; Chou, 2006), collaborative wikis (Leuf & Cunningham, 2001; Ignat et al., 2007), shared project and time management (Kawell et al., 1988; Byrne, 1999), and distributed file (Nowicki, 1989; Morris et al., 1986) or database systems (Thomas et al., 1990).

The previous example illustrates the potential collaborative scenarios that the emerging environments of ubiquitous and mobile computing (Weser, 1991; Forman & Zahorjan, 1994) allow. One may even conceive more extreme scenarios, where the fixed network infrastructure is even less likely to be present. For example, data acquisition in field work, emergency search-and-rescue operations, or war scenarios (Royer & Chai-Keong, 1999). In all these scenarios, collaboration through data sharing is often crucial to the activities the teams on the field carry out.

Optimistic replication is especially interesting in all previous scenarios, due to their inherent weak connectivity. They are based on mobile networks, whose bandwidth is lower than in local-area wired networks, and where network partitions and intermittent links are frequent. Further, mobile nodes reduce their up-time due to battery limitations. Moreover, a fixed network infrastructure, such as a corporate local area network, may not always compensate for the limitations of mobile networks. In fact, access to such an infrastructure is often supported by wireless connections such as IEEE 802.11 (IEEE, 1997), UMTS (3GP) or GPRS (Ericsson AB, 1998); these are typically costly in terms of price and battery consumption, and are seldom poor or intermittent due to low signal. Hence, access to the fixed infrastructure is often minimized to occasional connections. Furthermore, access to the fixed network infrastructure is often established along a path on a wide-area network, such as the Internet; these remain slow and unreliable (Zhang, Paxson & Shenker, 2000; Dahlin et al., 2003).

Optimistic replication, in contrast to traditional replication (i.e., pessimistic replication), enables access to a replica without a priori synchronization with the other replicas. Hence, it offers highly available access to replicas in spite of the above limitations (among other advantages over traditional replication (Saito & Shapiro, 2005). As collaboration in ubiquitous and mobile computing environments becomes popular, the importance of optimistic replication increases.

Inevitably, however, consistency in optimistic replication is challenging (Fox & Brewer, 1999; Yu & Vahdat, 2001; Pedone, 2001). Since one may update a replica at any time and under any circumstance, the work of some user or application at some replica may conflict with concurrent work at other replicas. Hence, consistency is not immediately ensured. A replication protocol is responsible for disseminating updates among replicas and eventually scheduling them consistently at each of them, according to some consistency criterion. The last step of such a process is called update commitment. Possibly, it may involve rolling back or aborting updates, in order to resolve conflicts.