This is a common misunderstanding about the poorly named ‘Availability’ in CAP. Availability under CAP means that if your request reaches a non-failing node, that node still responds despite being unable to communicate with other nodes. This is distinct from SLA-style availability, which describes the uptime of the overall system.
I’m pretty sure the partition tolerance they’re referring to is the fact that the tailnet remains intact and continues to operate even when nodes can’t reach the coordination service.