I think you're actually confusing the concepts. They talks about a more general concept of consistency that is per se unrelated to graph algorithms. The examp

I think you're actually confusing the concepts. They talks about a more general concept of consistency that is per se unrelated to graph algorithms. The examples they have use to illustrate the idea are deadlock detection and garbage collection in a distributed setting, which are two very distinct problems, in that the former will eventually converge, while the other does not necessarily due to the 2 generals problem (you could try to move all the information to a single node, and you can do so in practice, but because of the 2 generals problem you can't once your connections have a chance of being lossy).