[astrange]

Sounds like you were using Internet Recovery. It's downloading the OS installer from the App Store - if you had install media it'd work fine.

[kstenerud]

It's a macbook air. There is no install media.

[stephenr]

You can make one if you choose (most people use a USB stick, I'm using an ExpressCard SSD) - this will remove the need for an AppleID and internet access to do the install.

For the vast majority of people this will never be an issue as the machine comes pre-installed and re-installing the OS is generally not required unless something major goes wrong.