Optimal propagation-based protocols implementing causal memories

Ensuring causal consistency in a Distributed Shared Memory (DSM) means all operations executed at each process will be compliant to a causality order relation. This paper first introduces an optimality criterion for a protocol P, based on a complete replication of variables at each process and propagation of write updates, that enforces causal consistency. This criterion measures the capability of a protocol to update the local copy as soon as possible while respecting causal consistency. Then we present an optimal protocol built on top of a reliable broadcast communication primitive and we show how previous protocols based on complete replication presented in the literature are not optimal. Interestingly, we prove that the optimal protocol embeds a system of vector clocks which captures the read/write semantics of a causal memory. From an operational point of view, an optimal protocol strongly reduces its message buffer overhead. Simulation studies show that the optimal protocol roughly buffers a number of messages of one order of magnitude lower than non-optimal ones based on the same communication primitive. R. Baldoni Roberto Baldoni is a Professor of Distributed Systems at the University of Rome “La Sapienza”. He published more than one hundred papers (from theory to practice) in the fields of distributed and mobile computing, middleware platforms and information systems. He is the founder of MIDdleware LABoratory <://www.dis.uniroma1.it/&dollar;∼midlab> textgreater (MIDLAB) whose members participate to national and european research projects. He regularly serves as an expert for the EU commission in the evaluation of EU projects. Roberto Baldoni chaired the program committee of the “distributed algorithms” track of the 19th IEEE International Conference on Distributed Computing Systems (ICDCS-99) and /he was PC Co-chair of the ACM International Workshop on Principles of Mobile Computing/ (POMC). He has been also involved in the organizing and program committee of many premiership international conferences and workshops. A. Milani Alessia Milani is currently involved in a joint research doctoral thesis between the Department of Computer and Systems Science of the University of Rome “La Sapienza” and the University of Rennes I, IRISA.She earned a Laurea degree in Computer Engineering at University of Rome “La Sapienza” on May 2003. Her research activity involves the area of distributed systems. Her current research interests include communication paradigms, in particular distributed shared memories, replication and consistency criterions. S. Tucci Piergiovanni Sara Tucci Piergiovanni is currently a Ph.D. Student at the Department of Computer and Systems Science of the University of Rome “La Sapienza”.She earned a Laurea degree in Computer Engineering at University of Rome “La Sapienza” on March 2002 with marks 108/110. Her laurea thesis has been awarded the italian national “Federcommin-AICA” prize 2002 for best laurea thesis in Information Technology. Her research activity involves the area of distributed systems. Early works involved the issue of fault-tolerance in asynchronous systems and software replication. Currently, her main focus is on communication paradigms that provide an “anonymous” communication as publish/subscribe and distributed shared memories. The core contributions are several papers published in international conferences and journals.