O assincronismo pode ser obtido através de uma máquina de estados já que ele precisa apenas garantir que não ocorra espera enquanto está fazendo algo potencialmente demorado, então ele precisa trocar o contexto de execução entre mais de uma parte da aplicação.
Esta é uma técnica antiga e bem conhecida usada em diversos problemas. Ela vai trocando um ou mais determinados estados de acordo com o que vai acontecendo em algo relacionado com o que ela está controlando.
Mesmo este mecanismo tem diversas formas de implementá-lo. A forma como a entrada que provoca troca de estado pode ser obtida de diversas maneiras. Um sistema de eventos que indica a mudança de estado é bem comum.
A imagem lá na pergunta é bem ilustrativa como é complicado controlar o fluxo de execução. Siga a guerra de índio.
Artigo da Wikipedia.
Uma implementação em C#.
Explicação detalhada de como O async/await
do C# funciona. Ali tem exemplos mais ou menos de como o código fica na verdade quando este mecanismo é usado. Tudo ali é uma máquina de estados, sendo que o que está esperando é o responsável por mudar o estado dessa máquina. Quando não houver mais espera um processamento diferente é executado encerrando o que começou, mas não bloqueia a execução de outras coisas. Há um controle se ainda pode executar alguma outra coisa, ou se deve retomar o processamento do que está em espera.
Um exemplo de código real que é gerado pelo compilador. Simples, não?
ainda vou melhorar.