Using promoteHint with a READ Reply

While DEMOTE uses an additional bandwidth-intensive operation (DEMOTE: similar to a page WRITE), PROMOTE uses a boolean bit, called $promoteHint$, that is passed along with every READ reply, and helps to decide which cache should own the page. The $promoteHint$ is set to true when a READ reply is first formed (cache hit or disk read) and set to false in the READ reply when some cache decides to keep (own) it. A READ reply with a false $promoteHint$ implies that a lower cache has already decided to own the page and the page should not be cached at the higher levels. When a cache receives a READ reply with a true $promoteHint$, the cache gets to decide whether to keep (own) the page locally or ``promote" it upwards. At each cache level PROMOTE maintains a separate $probPromote$ value, which is the probability with which that cache will promote a page upwards. If a cache decides to own the page (Lines 18-22), it changes the $promoteHint$ to false in the reply and maintains a copy of the page locally. In all other cases, a READ reply is simply forwarded to the higher cache with the $promoteHint$ value unchanged, and any local copy of the data is deleted from the cache. The highest cache has $probPromote = 0$, implying that it always owns a page that it receives with a true $promoteHint$. A page received with a false $promoteHint$, implying that the page is already owned by a lower cache, is merely discarded upon returning it to the application.