University of Houston

The context of this research is a communication model based on Put/Get calls to an abstract global space to support communicating applications on a volunteer PC grid. Parallel applications need replication as well checkpointing to make continuous progress in such a heterogeneous and unreliable computation environment. Since different instances of the same process can execute in the same logical state at different clock times, communicated data objects must be logged to ensure consistent execution of process replicas. Logging to support redundancy can be the source of a significant overhead in execution time and storage. In this thesis we develop, implement, and evaluate pessimistic and optimistic logging schemes to support redundant communication. Pessimistic schemes log a copy of the data object returned to a Read/Get request, creating a copy of the data object on every call. On the other hand, optimistic schemes log the old data object when a put request is overwriting a data object. This avoids redundant copying, but identifying the correct data object to return to a Read/Get request is complex. A Virtual Time Stamp (VTS) that captures global execution state is logged along with the data object to make this possible. We develop an optimized pessimistic scheme that minimizes redundancy and an optimized optimistic scheme that reduces the VTS size and overhead. Our experimental results show that optimizations are effective in terms of storage and time overhead and an optimized pessimistic scheme presents the best tradeoffs for execution in a volunteer computing environment.