Mercury

Consider, for instance, a laptop user that becomes disconnected from his corporate file server after leaving his office. If necessary, he expects to be able to modify a report that is currently replicated at his laptop, even if tentatively. Furthermore, such worker may meet other colleagues carrying their laptops with replicas of that report and, in an ad-hoc fashion, establish a short term work group to collaboratively work on it. A set of tentative updates will result from such activity. Hopefully, if no update is concurrently issued from outside the group, such tentative work will be eventually committed by the underlying system by means of a consistency protocol. There are many other scenarios where users are willing to work with tentative data, provided that a commitment agreement regarding such data will eventually be reached.

Optimistic replication is especially interesting in such scenarios. It is a well known technique to improve both availability and performance of application-level or system-level software in distributed systems. In one hand, having data and or code local to the hardware being used allows its users to keep on working even with no network access, thus increasing availability. On the other hand, the co-location of data and code, instead of accessing data remotely, improves applications and system performance.

As collaboration through mobile networks or large-scale networks becomes popular (e.g. asynchronous groupware applications, distributed file or database systems, collaborative wikis), the importance of optimistic replication increases. However, when compared to pessimistic replication, optimistic replication suffers from a well-known disadvantage: replica inconsistency. This results from the fact that, for availability and performance, replicas are allowed to be updated at any time and circumstance; thus, updates may conflict if issued concurrently at distinct replicas.

The usefulness of an optimistic approach strongly depends on the effectiveness of the underlying consistency protocol to achieve consistency. Such effectiveness may be decomposed into two vectors, which an optimistically replicated system should pursue: conflict minimization and rapid update commitment. In other words, replica inconsistency can be solved either using techniques to prevent concurrent updates from happenning or, while allowing such updates to occur, using protocols to ensure fast replicas convergence.

Current solutions have unacceptable disadvantages. In one hand, preventing concurrent updates from occurring using a "less-optimistic" approach has a strong negative impact on availability, which is one of the main advantages of using optimistic replication. On the other hand, current consistency protocols (e.g. Bayou, Pastiche, Venti, Haddock-FS, IceCube, Rumor, Roam, Deno, etc.) either consume a large amount of network bandwidth and memory to transmit and store replicas updates or impose a long time for replicas convergence. Such resource usage is at odds with the environments in which optimistic replication is most useful: mobile networks and large-scale networks. As a matter of fact, mobile hardware is clearly a resource constrained platform when compared to desktop computers thus suggesting solutions which minimize network bandwidth and memory usage. In addition, mobile devices (e.g. laptops, PDAs), when compared to desktop computers, are clearly resource constrained devices requiring system and application software to make good use of network bandwidth and memory. Regarding large-scale networks, network bandwidth is also an important resource that must be used wisely both by system and application software.

Although much research has been done, while providing very good ideas, they do not address the issues of conflict minimization and rapid update commitment while minimizing resource usage in constrained devices. Thus, the goal of this project is twofold: i) to improve the speed at which (concurrently updated) replicas become consistent, and ii) while not preventing concurrent updates from occurring, inform the application when such updates will most likely lead to a conflict (or not). This goal must be attained while minimizing both the amount of data exchanged between replicas, and the amount of memory being used. These requirements are fundamental for resource constrained mobile devices and large-scale networks. To achieve the goal mentioned above, while respecting the requirements, in this project we envisage to develop solutions along the following axes: i) decoupling consistency information from data propagation, ii) designing voting-based update protocols allowing rapid commitment in the presence of failures or partitions, and iii) using content-based indexing for structuring the data allowing the use of similarities between data for reducing memory usage.

The high-level overall goal of this project is to improve users’ productivity by supporting data access with high availability and performance. Optimistic replication is a well known technique to attain such goal but its usefulness strongly depends on the underlying consistency protocol to ensure fast and reliable replica consistency. This project will develop new algorithms, protocols, and system architectures running in prototypes that will ensure conflict minimization and rapid update convergence appropriate for resource-constrained devices. The contributions will be in the area of consistency of replicated data. In particular: i) a consistency protocol that decouples consistency information from data propagation, thus minimizing network bandwidth, ii) voting-based update protocols allowing rapid commitment in the presence of failures or partitions, and iii) content-based indexing for structuring the data allowing the use of similarities between data, thus reducing memory usage.

Sponsoring bodies: FCT

Coordinator: Paulo Ferreira

Partners: INESC-ID

Homepage: N/A