Byzantine generals: N generals wish to coordinate their attack on a defending army. The attack will succeed if a majority attack at the same time, so you send messages to the other N-1 generals saying "attack tomorrow at dawn".
But wait: Some of those messages may have been captured by the enemy, and some generals may simply not agree with your strategy. If enough generals don't attack, but you still attack, you will fail. So the new plan is to send a message to the other N-1 generals saying "attack tomorrow at dawn, please reply with confirmation that you will be participate", and then if you get confirmation from at least (N/2 - 1) generals, you can attack with confidence.
But wait: Your fellow generals know that the enemy is potentially capturing messengers, and they won't want to attack if nobody else is attacking, and they know nobody will attack if they don't get the confirmation, so they need confirmation that everyone got their confirmation.
But wait: You'll need confirmation of their confirmation, and so down the rabbit hole we go.
What we end up with is a network of messengers, where every general keeps broadcasting a planned attack date to all the others, but it never able to be certain that the others heard and agreed to it. What's needed to solve this problem is a way of sending a message who's mere existence proves that a majority of generals are committed to the attack, and thus you don't have to reply to the message asking for confirmation that everyone still agrees.
Enter proof of work. What if each general would, upon receipt of the proposed attack date, perform some complex and time consuming calculation; maybe have some poets write a poem in iambic pentameter about the proposed date, and then the first one to finish attachs the poem to the message, and rebroadcasts it? Each time a general receives a new message, they'll take the one with the most poems attached, and start writing a new poem that references the attack date and all previous poems. Fairly soon you'll have a massive chain of dozens of epic poems about the proposed attack date. This tells you a couple of things:
1. All those poems are too much work for one rogue general (or the defending army) to have done. This took the finest minds of the most of the Byzantine general staff to create.
2. And that means that most of the generals must be okay with this plan, because they've spent all week writing poems about it.
3. And most of them must be aware that everyone else is okay with it too, since they've all seen all the poems everyone else saw.
The mere existence of this attack plan, with all of it's self-referentials poems attached, is proof that a consensus attack date exists, and means you're safe to attack, without needing to communicate further.
(For another, much shorter attempt at explaining the link, see: https://bitcointalk.org/oldSiteFiles/byzantine.html)