» Download Article
A “Flows Consistency” Model for Message Ordering in Collaborative Distributed Systems
Information Control Problems in Manufacturing, Volume # 13 | Part# 1
Authors
Dobrescu, Radu; Dobrescu, Matei
Identifier
10.3182/20090603-3-RU-2001.00276
Index Terms
Inter-Organizational Workflow Management; PLM Systems; Formalisms and Modeling Techniques
Abstract
The major contribution presented in this paper is an algorithm, which exploits the “flow concept” and selection policy to assure the delivery of strong operations with minimum delay for CSCW (Computer Supported Collaborative Work). The distributed algorithm guarantees the delivery of strong operation messages to the application in the same global order. Timestamps are used to enforce global ordering on the strong operations. The execution of any strong operation is postponed until the timestamp of that operation is smaller than all the estimated timestamp counters of the system. Then we define the flows concept that ensures a causal dependency relation among messages in order to preserve the context in which a message is sent. We prove that the flows concept and the global ordering algorithm together capture the requirements of the “flows consistency” model and we present execution examples that show how inconsistencies can appear if the system does not ensure causal synchronization. Finally, we demonstrate that the implementation of our message based distributed system assures causal consistency.
References
REFERENCES Arons, T (2001). Using Timestamping and History Variables to Verify Sequential Consistency, Proceedings of the 13th International Conference on Computer Aided Verification, p.423-435 Attiya, H and R. Friedman (1998) A correctness condition for high performance multiprocessors, SIAM Journal on Computing, 27(6), pp.1637-1670 Chennareddy, V. and J.K. Deka (2006). Formally Verifying the Distributed Shared Memory Weak Consistency Models, International Conference on Advanced Computing and Communications, ADCOM 2006, pp.455 – 460 Dobrescu, R. and M. Rothenberg (2005). A method for inferencing of network characteristics based on traffic similarities Bul. UPB, vol.67, C series. Electrical Eng., nr.1, pp.23-32 Galli, R. and Y. Luo (2000). Mu3D: A Causal Consistency Protocol for a Collaborative VRML Editor, Proceeding of the VRML’2000 Symposium, ACM SIGGRAPH, pp.53-62 Graham, S and P. R. Kumar (2004). Time in General-Purpose Control systems: The Control Time Protocol and an experimental evaluation, Proceedings of the 43rd IEEE Conference on Decision and Control, Bahamas, pp. 4004-4009 Gu, N., J. Yang, and Q. Zhang (2005). Consistency maintenance based on the mark & retrace technique in groupware systems. Proceedings of the ACM Conference on SIGGROUP, pp. 264–273 Qadeer, S., (2003). Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking, IEEE Transactions on Parallel and Distributed Systems, 14, issue 8, pp. 730-741 Saito, Y. and M. Shapiro (2005) Optimistic replication. ACM Computing Surveys, 37(1), pp. 42–81 Win, K., W. Ng, Q. Liu, and E. Lim (2003). XStamps: A multiversion timestamps concurrency control protocol for XMLData. In The Fourth International Conference on ICICS/PCM Yang, J., Q. Zhang and N. Gu (2006) A Consistency Maintenance Approach in Replicated Services, Proc. of the Sixth IEEE International Conference on Computer and Information Technology, pp. 248 – 258 Zhang, W., M.S. Branicky and S.M. Phillips (2001). Stability of networked control systems. IEEE Control Systems Magazine, 21(1), pp. 84-99