0
$\begingroup$

Can someone explain to me how clean chains work in this paper?

Here's the paper: Competitive caching with machine learned advice by Lykouris & Vassilvitskii

I'm trying to implement the predictive marker algorithm as described on page 13, but I can't seem to understand how the "clean chains" are constructed. I'm trying to implement them using a digraph.

All I (mis?)understand is the following:

  1. Clean chains are used to construct a blame graph (digraph), which explains why some element e got evicted.

  2. e is evicted for one of two reasons: a) a clean element c arrived, or b) a stale element s arrived

2.a) A new clean chain is added when a clean element c arrives, meaning a node, c, is added (should I then add an edge from c to e?)

2.b) the arriving element s (which is stale) is the "representative" (described as lead node, couldn't the representative also be the end node?) of some clean chain c. The length of the clean chain is incremented (s -> e?)

Sorry about my understanding being so all over the place, and probably mostly, if not entirely incorrect. Could anyone discuss with me to clarify my (mis)understandings?

I attempted to use ChatGPT to help explain it, but the answers were subpar and only served to confuse me more.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Solved it (I think)

In the implementation, the end of the chain within the digraph is treated as the representative. The chain is retrieved by getting the "in_edges" (using networkx) from this representative all the way up to the actual root.

I will have to verify if my implementation functions appropriately, but at least it appears to be running correctly.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.