If public IPs are pinned to a single AS, how does BGP anycast work?
Solution 1:
An AS doesn't need to necessarily be constrained to a single physical location.
When anycasting, you run routers in many physical locations, each peering with different ISPs as the same AS, advertising a route to the anycasted IP addresses.
From BGP's perspective, it's not terribly dissimilar to what you'd do for redundancy with multiple ISPs from an AS in one site; in the "one site, multiple ISP" situation, one router's sending "I'm AS X, and I have IP range Y!" to multiple ISPs; in anycast, you're just instructing geographically disparate routers to all advertise their own nearly identical "I'm AS X, and I have IP range Y!" message to their own ISPs, claiming your AS and your anycast range and letting BGP select the best ISP to send the traffic to.
The ISPs don't know any different; the internet has no sense that the various available paths aren't just leading to the same highly-redundant site.
Solution 2:
There is no requirement that IP addresses or Internet routes for a prefix come from a single AS. ASNs are assigned to organizations, and addresses are also assigned to organizations. Registrars like ARIN don't link my address allocation to my ASN allocation. Even in new systems like Resource Public Key Infrastructure it still allows for multiple ASs to originate a route to a network. The Team Cymru page says this in the FAQs:
In some cases a network prefix will be announced by multiple, but disparate, networks or autonomous systems. The most likely reason for this is something known as "multihoming". This is perfectly normal. Depending on your view of the Internet topology and the originating network's policies, one of those originating networks will be the preferred path for sending and receiving traffic with the netblock in question.
Here's a (long) list of networks that are currently advertised from multiple ASs.
As to how it gets to where it's going: Routes are selected using a BGP path selection algorithm that chooses a path based on the information each router the traffic passes through knows about. Each router on the Internet has it's own view of the routing table, so traffic in one part of the Internet can end up in a different place and AS than traffic in another part of the Internet. There's not even a requirement to have every packet in a flow go to the same place, which can obviously make things interesting in the case of anycasting or multihoming.
Solution 3:
This (and resources like this page) seems to imply a mapping of 1 public IP to 1 AS.
Yes. That is true.
However, anycast seems to work by advertising the same public ip address from multiple locations,
Simply exactly by "just doing it". An AS is the entity that defines it's own routing internationally. It can connect the same IP address to multiple locations - as long as the routing does not change in the middle of a connection, that is ok.
Just be ignorant for a moment (because here ignorance works).
If you ask for IP x in USA, you go to a datacenter in the USA as per AS BGP rules. If you do so in Australia, you end up in a datacenter in australia. Finished. There is nothing that says that an IP can not be reused AS LONG AS THE ROUTING IS STABLE.
This is not a BGP hack as much as a normal use of BGP.