Title of paper: Model Checking Groupware Protocols

Abstract

The enormous improvements in the efficiency of model-checking techniques in recent years facilitates their application to ever more complex systems of concurrent and distributed nature. Many of the protocols underlying groupware systems need to deal with those aspects as well, which makes them notoriously hard to analyse on paper or by traditional means such as testing and simulation. Model checking allows for the automatic analysis of correctness and liveness properties in an exhaustive and time-efficient way, generating counterexamples in case certain properties are found not to be satisfied. In this paper we show how model checking can be used for the verification of protocols underlying groupware systems. To this aim, we present a case study of those protocols underlying the Clock toolkit [GUN96,UG99] that are responsible for its network communication, concurrency control, and distributed notification aspects. In particular, we address key issues related to concurrency control, data consistency, view consistency, and absence of (user) starvation. As a result, we contribute to the verification of Clock's underlying groupware protocols, which was attempted in [Urn98] with very limited success.


[GUN96] T.C.N. Graham, T. Urnes, and R. Nejabi, Efficient Distributed Implementation of Semi-Replicated Synchronous Groupware, Proceedings UIST'96, ACM Press, New York, NY, 1996, 1 - 10.
[UG99] T. Urnes and T.C.N. Graham, Flexibly Mapping Synchronous Groupware Architectures to Distributed Implementations, Proceedings DSVIS'99, Springer-Verlag, Wien, 1999, 133 - 148.
[Urn98] T. Urnes, Efficiently Implementing Synchronous Groupware, Ph.D. thesis, Department of Computer Science, York University, Toronto, 1998.