Now we discuss how to keep multistamps small and also how to
keep the VQ and PSTAMP tables small.
All of our optimizations rely on time: we remove ``old''
tuples from multistamps.
To account for removed tuples, a multistamp _m_
also contains a timestamp _m.threshold_; _m.threshold_ is
greater than or equal to timestamps of all tuples that have been removed
from _m_.
The threshold allows us to compute an _effective multistamp_
EFF(_m_)
containing a tuple 
for every client/server pair, where
_ts_ is the timestamp in the tuple for C/S in _m_ if one exists and
otherwise, _ts_ is _m.threshold_.
As mentioned in Section 4, clients receive invalidation information from servers within the timeout period of when it was generated. This communication implies that tuples containing a timestamp _ts_ that is older than a server's current time by more than this period are not useful, since by now those old invalidations will almost certainly have been propagated. Therefore, such old entries are _aged_, i.e., automatically removed from multistamps.
Simple aging of tuples may not be enough to keep multistamps small, so we also _prune_ the multistamp by removing tuples that are not old. The system bounds the size of multistamps: whenever a multistamp _m_ exceeding this size is generated, it is immediately pruned by removing some tuples. Pruning occurs in two steps: First, if there is more than some number of tuples concerning a particular server, these tuples are removed and replaced by a _server stamp_. Then, if the multistamp is still too large, the oldest entries are removed and the threshold is updated. A server stamp is a pair <_server, timestamp_>; EFF(_m_) expands a server stamp into a tuple for each client for that server and timestamp.
The VQ and PSTAMP are also truncated. Retaining information in the VQ about transactions that committed longer ago than the timeout period is also not useful. Whenever the multistamp of a transaction contains no tuples (i.e., it consists only of a threshold), it is dropped from the VQ. The VQ has an associated multistamp _VQ.m_ that is greater than or equal to the (effective) multistamps of all transactions dropped from VQ. Information is dropped from PSTAMP in the same way, with information about multistamps of dropped entries merged into PSTAMP._m_, a multistamp associated with PSTAMP. Note that for both the VQ and PSTAMP, we can remove entries earlier if we want; all that is needed is to update the associated multistamp properly. Thus, a server only maintains entries for recently committed transactions in the VQ and only information about recently modified pages in PSTAMP.
A server initializes the multistamp _m_ for a transaction to _VQ.m_. When a fetch request for page P arrives and PSTAMP contains no entry for P, the fetch response contains PSTAMP._m_.
When a client receives a multistamp _m_, it computes EFF(_m_) and proceeds as described in Section 5.2.
The result of these optimizations is a loss of precision in multistamps, which may in turn lead to more fetch stalls. For example, in pruning the multistamp, the server may have removed an entry <_D, S, ts_> concerning some client D different from C. When that multistamp arrives at C, C may block while waiting for invalidation information from S even though S has no invalidations for it.
When an invalidation request arrives at a server it might contain a timestamp _ts_ that is larger than what is stored in any entry in the ILIST for that client. To handle such a situation, the timestamp in the invalidation response will be the value of the server's current clock. If the current value of the clock is less than _ts_, the server will wait for it to advance. This situation is extremely unlikely, since it occurs only if clocks are out of synch.
Every message sent to the client contains a piggybacked invalidation message. This message is as described earlier except that if the whole ILIST is being sent, or if the ILIST is empty, the current clock value is sent as the timestamp. This timestamp allows the clients to avoid stalls.