If witnesses are changing their votes then yes you can get two different irreversible head blocks. I would suggest that witnesses not ever change their votes. Of course, you can't literally prevent it, but if it is discouraged, you can probably rely on "enough" witnesses not changing their votes to prevent the problem.
I'm not sure this is actually sufficient when there are forks.
Yes, he's talking about the case of a fork switch. And originally I was also thinking that we had implemented it so that a block producer would cast a new vote for a block during a fork switch (which I think would be ok).
But I was wrong, instead each node keeps track of the last block number it voted for, so it won't cast another vote at the same or earlier block height. While this latter optimization isn't IMO necessary to prevent an irreversible fork, it does reduce the number of votes that get generated during a fork.
I'm not sure it would be okay if multiple votes were cast. You can't be sure that every producer sees every vote. So half may see one vote as part of a 3/4 majority (therefore declaring one fork as immutable) and another half may see the other vote as part of a different 3/4 majority (declaring the other fork as such). This will never resolve because each half will be permanently stuck on their own "immutable" fork.
Yes, its true that it makes it "worse" if multiple votes are cast and that was one of the considerations for avoiding it. But it would still take 50% of them doing so to get a 3/4ths majority on both sides.
In the general case of intentionally bad nodes, they can always cast different votes to different nodes and 50% bad nodes can cause an irreversible fork (that's the term I'm using for what you're calling an immutable one, figured it's best if we stick to just one term for it).
But avoiding two votes by good nodes prevents them from ever inadvertently behaving like a bad node, so practically speaking it is much better if they don't.
Intentionally bad I'm not concerned about here. I'm thinking of a "good" node that changes its votes but then the votes propagate differently. But if good nodes don't change their votes this can't happen.
I'm still not 100% sure about different situations with fork resolution. I'd feel better if there were a more detailed mathematical analysis, or clear reduction to a well-known consensus algorithm, but even without it may work "well enough".
When we did the initial napkin design, we wanted a protocol that would allow for anything less than 1/2 of the witness to be behaving badly. So, the obvious worst case here would be 1/2 bad witnesses voting on two sides of a fork. In such a case, both forks would have 1/4 good witnesses + 1/2 bad witnesses and a 3/4ths majority would be achieved on both sides of the fork.
I wasn't necessarily viewing it as "bad" unless it is defined that way, which wasn't clear to me. The comment about changing votes many times suggested it might be considered as legitimate behavior, but if not then it seems fine that "some" threshold of bad witnesses can break it. That's essentially unavoidable.