A framework and protocols for reliable, timely, and ordered message delivery in distributed collaborating group applications.

摘要

In this thesis, we consider the problem of Reliable, Timely, and Ordered (RTO) delivery of messages in collaborating group applications. We develop a formal framework for defining the RTO constraints, with particular emphasis on capturing application semantics. We also develop protocols to meet the RTO constraints.; Reliability and ordering constraints in the RTO framework are based on a novel object-centric formulation of the reliable group multicast problem, which we refer to as the Group State Synchronization Problem (GSSP). This formulation allows us to capture and represent reliability and ordering semantics at the object level. Reliability in the GSSP formulation is defined by relating message delivery to predicates defined on the state of the processes. This approach is closer to the application's semantics, and leads to protocols that are less costly. Further, ordering is an integral part of the GSSP formulation. The use of conflict sets allows specification of ordering constraints at finer levels of granularity, again allowing a better way to capture application semantics. The GSSP formulation also allows the use of application semantics for failure detection. By exploiting application semantics, we are able to reduce the occurrence of incorrect and costly failure detections. Process joins are also a lightweight operation in the GSSP formulation.; We next develop a formal framework for the timeliness constraints. We consider two timeliness constraints: jitter and playback delay. We refer to the problem of defining and meeting these timeliness constraints as Playback Synchronization. The playback synchronization framework allows different messages to have different playback durations. The framework also allows situations where the playback duration of a message can be different (in particular, larger) than the inter-generation time for that message. The framework is designed such that the source and destination clocks can have non-zero clock skew without impacting the protocols.; Finally, we discuss how the GSSP and Playback synchronization frameworks can be integrated with each other and describe the architecture of a java-based implementation of the framework.