Most distributed systems network models assume there is some kind of pre-established authenticated communication channel among a fixed set of participants, for example a PKI. Bitcoin is meant to work in a weaker model where there is no such assumption. Instead Bitcoin relies on a non-standard assumption about the allocation of computational resources - ignoring incentives for now, the assumption is that honest parties contribute more power in total than the adversary.
Some pre-established communication channel must still be assumed, just not an authenticated one. When formalizing Bitcoin things, I usually call it a "synchronous message diffusion" channel. Any honest party can publish a message, and that message is delivered to every other honest party within some time bound. A party that receives a message does not learn the identity of the sender (this essentially makes Sybil attacks possible). Additionally, the adversary can selectively deliver its own injected messages to some but not all parties (this makes it weaker than broadcast, an honest party that receives a message cannot assume that every other party has received it too).
This isn't the only possible model. You could argue that "message diffusion" is still too strong, it doesn't reflect eclipse attacks or DoS, for example, which are possible. Anyway, the point is that with the message diffusion channel alone, hardly anything is possible. With the diffusion channel and honest-hashpower-majority assumption, something approximating Byzantine agreement (aka, broadcast) is possible.
I say "approximating" because Bitcoin fails most formal definitions of Byzantine agreement. Deterministic consensus is out for sure. And there is never a point at which every party "decides" on a final value. For this reason, Stabilizing Consensus [Angluin2006] is probably the closest matching definition. Even this needs to be relaxed in some ways, for example computational security, and for pipelining agreement about multiple values in sequence - at any point, the adversary might revise a ton of history by breaking the hash function.
Anyway, the point is that Bitcoin achieves some form of public sequential broadcast, where any party can publish a message (for a fee) to be included in the public log, and every party receives and agrees on each message in the log in sequence. With this broadcast channel in place, it's possible to implement all sorts of useful protocols, especially ones involving accountability or (certificate) transparency. The basic example is a service contract. A service Provider signs (and publishes) a contract that says any Client can make a request for service by publishing a message to the public log, and the Provider will respond in a timely fashion, also by publishing a message to the log. If the Provider fails to respond to a valid request, then the Client obtains (publicly verifiable) evidence of this. And the Provider cannot be falsely accused or forced to breach its contract, since requests are only valid if they're published and the Provider receives every published message. This is why a broadcast channel is so strong. We (coauthors at Princeton and Concordia) call this approach in general "Warranties" (see our [Mixcoin] paper at FC'14). Green addresses are another example of an implied Warranty - you can accept a transaction immediately if it's signed from a Green address, since if there is a double spend, you will obtain publicly verifiable evidence that the address holder violated its agreement.
It's not clear if there are other reasonable ways of achieving public broadcast in other realistic models. Freenet, for example, is a public p2p network that lets any party publish messages in a sequence, like ssk://{pubkey}/4. However, if the sender is dishonest, she can fake the system (by connecting multiple instances to different peers) into displaying one message to one user and a different message to another user.
[Angluin2006] Stabilizing Consensus in Mobile Networks. Angluin, Fischer, and Jiang. Distributed Computing in Sensor Systems, 2006. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.1040&rep=rep1&type=pdf
[Mixcoin] Mixcoin: Anonymity for Bitcoin with accountable mixes. Arvind Narayanan, Joseph Bonneau, Andrew Miller, Jeremy Clark, Joshua Kroll. To appear, Financial Cryptography. March 2014. http://eprint.iacr.org/2014/077