At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a read given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are performed.

There are lots of different consistency models, as indicated in the wiki article. Informally each of them defines a partial order over the operations. One of the common implementation methods is to utilize broadcast service. Not surprisingly, there are various broadcast service with different ordering (what you are probably interested in) and reliability (concerning fault tolerance) requirements. The following description is quoted from Chapter 8 "Broadcast and Multicast" of the book "Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Edition) By Hagit Attiya and Jennifer Welch. 2004.":

Ordering: Do processes see all messages in the same order or just see the messages from a single process in the order they were sent? Does the order in which messages are received by the broadcast service preserve the happens-before relation?

 

Reliability: Do all processes see the same set of messages even if failures occur in the underlying system? Do all processes see all the messages broadcast by a nonfaulty process?

This Technical Report: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems; 1994 gives a more comprehensive formal framework of broadcast service. It has also related the consensus problem with atomic broadcast. Consensus is also popular in distributed data storage systems, by implementing a replicated state machine.

As for your comment:

I would also be interested in any implementations of these which are in production or used by large scale companies?

Most distributed storage systems have considered such consistency models issues and their implementations. Again, different storage systems are targeted for different application scenarios, and thus adopt different consistency models and implement different ordering strategies.

I will name a few keywords and it is not difficult for you to find papers or articles about them: Amazon's Dynamo, Yahoo!'s PNUTS, Google's Bigtable, ZooKeeper, COPS@SOSP'11, Cassandra, HBase, ...

At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a read given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are performed.

There are lots of different consistency models, as indicated in the wiki article. Informally each of them defines a partial order over the operations. One of the common implementation methods is to utilize broadcast service. Not surprisingly, there are various broadcast service with different ordering (what you are probably interested in) and reliability (concerning fault tolerance) requirements. The following description is quoted from Chapter 8 "Broadcast and Multicast" of the book "Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Edition) By Hagit Attiya and Jennifer Welch. 2004.":

Ordering: Do processes see all messages in the same order or just see the messages from a single process in the order they were sent? Does the order in which messages are received by the broadcast service preserve the happens-before relation?

Reliability: Do all processes see the same set of messages even if failures occur in the underlying system? Do all processes see all the messages broadcast by a nonfaulty process?

This Technical Report: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems; 1994 gives a more comprehensive formal framework of broadcast service. It has also related the consensus problem with atomic broadcast. Consensus is also popular in distributed data storage systems, by implementing a replicated state machine.

As for your comment:

I would also be interested in any implementations of these which are in production or used by large scale companies?

Most distributed storage systems have considered such consistency models issues and their implementations. Again, different storage systems are targeted for different application scenarios, and thus adopt different consistency models and implement different ordering strategies.

I will name a few keywords and it is not difficult for you to find papers or articles about them: Amazon's Dynamo, Yahoo!'s PNUTS, Google's Bigtable, ZooKeeper, COPS@SOSP'11, Cassandra, HBase, ...