One way to define consistency for a particular datum A is to say that during each clock cycle all copies of A have the same value. While this definition is adequate and easy to understand, it is hard to implement efficiently when the potential number of copies is large. Fortunately, there is a weaker definition that is still adequate for correctness, but is much easier to implement in a large system. It is based on the notion of serializability.

To define serializability, consider the abstract model of a shared memory multiprocessor shown in Figure xx. There are some number of processors connected to a shared memory. Each processor has a private line to shared memory; over this line the processor issues the commands Fetch(A) and Store(A, D), where A is an address and D is data. For Fetch(A) the memory returns the value currently stored at A; for Store(A, D) it writes the value D into A and returns an indication that the write has completed. Let the starting time of an operation be the moment the request is sent over the line and the ending time be the moment either the return value or an indication of completion is received by the processor.

Let S be the state of the shared memory before the start of some computation C, and F be the state after C has completed. The Fetches and Stores of C are said to be serializable if there exists some serial order such that if these operations were performed in this order, without overlap, the same final state F would be reached starting from the initial state S. Two operations are said to overlap if the starting time of one is before the ending time of the other and the starting of the other is before the ending time of the one.

For the purposes of explaining the consistency algorithm, a single level system consists of one or more processors connected to the DynaBus through caches, and a single main memory. The first thing to note about this configuration is that it is sufficient to maintain consistency between cached copies. Since processors have no way to access data except through their caches, the main memory copy can be stale without causing incorrect behavior.

The algorithm requires that for each block of data a cache keep two additional bits, shared and owner. For a given block, the shared bit indicates whether there are multiple copies of that block or not. This indication is not accurate, but conservative: if there is more than one copy then the bit is TRUE; if there is only one copy then the bit is probably FALSE, but may be TRUE. We will see later that this conservative indication is sufficient. The owner bit is set in a given cache if and only if the cache's processor wrote into the block last; thus at most one copy of a datum can have owner set. A cache is also required to keep a single state bit called sharedAccumulator, and a register rqstAdrs. The bit is used in computing the value to be put into the shared bit for some block during certain transactions, while the register is used to hold the address for a request packet for which a reply hasn't yet been received. In addition to this state, the algorithm requires two lines on the DynaBus, BShared and BOwner.

Generally, a cache initiates a ReadBlock transaction when its processor does a Fetch or Store to a block and the block is not in the cache; it initiates a WriteBlock when a block needs to get kicked out of the cache to make room for another one (only blocks with owner set are written out); and it initiates a WriteSingle when its processor does a write to a block that has the shared bit set. Caches do a match only they see one of the following packet types: RBRqst, RBRply, WSRqst, WSRply. In particular, note that no match is done either for a WQRqst or a WQRply.

When a cache issues a RBRqst or WSRqst, all other caches match the block address to see if they have the block. Each cache that matches, asserts BShared to signal that the block is shared and also sets its own copy of the shared bit for that block. The requesting cache on the other hand first clears sharedAccumulator, initializes rqstAdrs to the block address, and then waits. A fixed number of cycles later, it reads BShared and OR's it into sharedAccumulator. In between the request packet and its reply, the requesting cache watches all packets on the bus just like other caches. If the address on any of these packets matches rqstAdrs, the cache sets sharedAccumulator. When the requesting cache sees its reply packet, it OR's the sharedAccumulator and the shared bit from the packet and puts the result into the shared bit for the block. This ensures that the shared bit is set for a block only if there are multiple copies, and that the shared bit is cleared eventually if there is only one copy. The clearing happens when only one copy is left and that copy's processor does a store. The store turns into a WSRqst, no one asserts BShared, and so the value the requestor computes for the shared bit is zero.

The manipulation of the owner bit is simpler. The owner bit is set each time a processor stores into one of the words of the block; it is cleared each time a WSRply arrives on the bus. There are two cases to consider when a processor does a store. If the shared bit for the block is zero, then the cache updates the appropriate word and sets the owner bit right away. If the shared bit is set, the cache puts out a WSRqst. When the memory sees the WSRqst, it immediately turns it around as a WSRply with the same address and data, making sure that the shared bit in the reply is set to zero. When the requestor sees the WSRply, it updates the word and also sets owner. Other caches that match on the WSRply update the word and clear owner. This guarantees that at most one copy of a block can ever have owner set. Owner may not be set at all, of course, if the block has not been written into since it was read from memory.

When an RBRqst appears on the bus, two distinct cases are possible. Either some cache has owner set for the block or none has. In the first case the owner (and possibly other caches) assert BShared. The owner also asserts BOwner, which prevents memory from responding, and then proceeds to supply the block via an RBRply. The second case breaks down into two subcases. In the first subcase no other cache has the block, BShared does not get asserted, and the block comes from memory. In the second subcase at least one other cache has the data, BShared does get asserted, but the block still comes from memory because no cache asserted BOwner. Because the bus is packet switched, it is possible for ownership of a block to shift in between the request and a reply. Suppose for instance that a cache does an RBRqst at a time when memory was owner of the block, and before memory could reply, some other cache issues a WSRqst which generates a WSRply which in turn makes the issuing cache the owner. Since BOwner wasn't asserted for the RBRqst, memory still believes it is owner, so it responds with the RBRply. To prevent this stale data from being taken by the cache that did the RBRqst, all caches match RBRply packets as well. If a cache gets a match and has owner set, it asserts BOwner to indicate stale data. The cache waiting for the RBRply sees BOwner, throws away this block and waits for another RBRply. This reply is generated by the cache that asserted BOwner (this explains one of the reasons why the number of reply packets may exceed the number of request packets).

For the purposes of the consistency algorithm, a two-level system consists of a number of one-level systems called clusters connected by a main that also has the system's main memory. Each cluster contains a single big cache, which connects the cluster to the main bus, and a private DynaBus, which connects the big cache to the small caches in the cluster. This private DynaBus is electrically and logically distinct from the DynaBuses of other clusters. From the standpoint of a private DynaBus, its big cache looks identical to the main memory in a single-level system. From the standpoint of the main DynaBus, a big cache looks and behaves very much like a small cache in a single-level system. Further, the design of the protocol and the consistency algorithm is such that a small cache cannot even discover whether it is in a one-level or a two-level system—the response from its environment is the same in either case. Thus the small cache's behavior is identical to what was described in the previous subsection.

The algorithm requires the big cache to keep all of the state bits a small cache maintains, plus some additional ones. These additional bits are the existsBelow bits, kept one bit per block of the big cache. The existsBelow bit for a block is set only if some small cache in that cluster also has a copy of the block. This bit allows a big cache to filter packets that appear on the main bus and put only those packets on the private bus for which the existsBelow bit is set. Without such filtration, all of the traffic on the main bus would appear on every private bus, defeating the purpose of a two-level organization.

We have already stated that the behavior of a small cache in a two-level system is identical to its behavior in a one-level system. We have also said that a big cache behaves like main memory at its private bus interface and a small cache at its main bus interface. What remains to be described is what the big cache does internally, and how packets on a private bus relate to those on the main bus and vice-versa.

When a big cache gets an RBRqst form its private bus, two cases are possible: either the block is there or its not. If its there, the cache simply returns the data via an RBRply, making sure that it sets the shared bit in the reply packet to its current state in the cache (recall that in the single-level system main memory always returned a zero for this bit). If the block is not in the cache, the cache puts out an RBRqst on the main bus. When the RBRply comes back the cache updates itself with the new data and its shared bit and puts the RBRply on the private bus. When a big cache gets a WSRqst on its private bus, it checks to see if the shared bit for the block is set. If it is not set, then it updates the data, sets owner, and puts a WSRply (with shared set to zero) on the private bus. If shared is set, then it puts out a WSRqst on the main bus. The memory responds some time later with a WSRply. At this time the big cache updates the word, clears the owner bit, and puts a WSRply on the private bus with shared set to one. When a big cache gets a WBRqst, it simply updates the block and sends back a WQRply.

When a big cache gets an RBRqst on its main bus, it matches the address to see if has the block. If there is a match and owner is set, then it responds with the data. However, there are two cases. If exists below is set, then the data must be retrieved from the private bus by placing a RBRqst. Else the copy of the block it has is current, and it can return it directly. When a big cache gets a WSRqst on the main bus, it matches the address to see if the block is there and asserts shared as usual, but takes no other action. When the WSRply comes by, however, and there is a match, it updates the data it has. In addition, if the existsBelow bit for that block happens to be set, it also puts WSRply on the private bus. Note that this WSRply appears out of the blue on the private bus; that is, it has no corresponding request packet. This is another reason why the number of reply packets on a bus may exceed the number of request packets.

This completes the description of the consistency algorithm. This description has been sketchy, but intentionally so since its meant to be an introduction rather than a rigorous definition. Such a definition is contained in Appendix B for those interested.