Given two computers attached to the Internet that know nothing about each other before hand, is it possible for one computer to be able to broadcast a message so that the second computer could receive it and respond?
I know UDP broadcast exsits, but I believe that those are generally filtered by the ISP before it reaches the true Internet. Is this true?
No, you can't broadcast like that over the internet. You need to know which address you want your packets to go to.
You need an intermediate third party that they both know, that could distribute messages directed towards it in a broadcast-like fashion.
The current best way to achieve a multinode network without centralized coordination is through the use of Distributed Hash Tables. That link explains a bit and links to various implementations you can leverage.
That said, you still need each machine to coordinate with at least some peers. It's just that you don't need it to coordinate with a central server. A solution using a central server that know both (all) participating machines will also work, but imposes further restrictions on anonymity and scalability, just remember what happened to Napster.
A solution for this problem (where none of your peers know the final address of the other) could be relying on IM protocols.
In particular, the XMPP protocol is extensible, open and used by many providers such as Google Talk. Libraries exist for most languages and it has the plus of being able to work (slowly and going through a 3rd party server) even if both hosts are behind a NAT-box.
If communication must use another channel, you can use XMPP to exchange IP address and then proceed with the standard socket route (but if you encrypt your messages, there should be no problem even going through a 3rd party server - to be true all packets go through untrusted 3rd party routers so you should encrypt anyway if you have sensitive data..).
Hope this helps.
UDP is a dead end - its just a protocol where the order the packets are received is less important and there are issues routing over WANS. You said that you want to connect two computer on the "internet" presumably with the end points moving around etc. The only way is to use a central server as a register/directory. If each end point allso a web service or something and registeres its current IP address and name periodically then the other end point can look up the IP address of the other using this service. (could host your own DNS server and code your end point to register on this DNS?)
One of the problems is that even if you have the IP address what is one or more nodes are behind a firewall or NAT router ? You will need to host a server to proxy traffic. The best example is SKYPE - look into how it works it is documented, very interesting.
The simplist answer might be to jump on the back on an existing service such as messanger, skype, bit torrent, etc.
Simon
A possible solution for you is to use a dynamic DNS service.
Your application would need to know in advance which hostname the other host will be using, but this service would at least get around the fact that you don't know exactly which IP address the other computer is on.
Note that this won't solve the potential issue of firewalls between the two hosts blocking your packets. The only practical way around that is for both hosts to open an outbound connection to a central host which can then relay data between them.
Multicasting is also a possible solution. It's certainly feasible in a corporate network
If the computers are running Windows, I'd look at using PNRP.
Look at the chord or pastry algorithm. It is an overlay network (DHT based) which has a discovery mechanism involved. It's a P2P (Peer 2 Peer) routing algorithm.