I desire an algorithm in which Alice sends a block of data $X$ to Bob, with proof that the data was both sent and received. Ideally this would take the form of a public-key signature of the block $X$ by both Alice and Bob, so that each is in possession of (X + sign(X,A) + sign(X,B)).
Further let us assume that Alice and Bob both may have motivation to lie about having sent/received the communication. Bob may choose to lie depending on the contents of $X$ once he sees it, and Alice may lie to attempt to discredit Bob. Therefore the signatures or other proof of communication must be revealed simultaneously to both Alice and Bob. At no point may either be in possession of the proof while the other is not.
I'd put a bounty on this if I had any reputation, but hopefully people will just consider it an interesting challenge. Some notes that may help: This is closely related to the Two-Generals problem (for which there is no two-party solution), however due to cryptography orders may not be forged, so I hold hope that there may be a two-party solution. If not, a multi-party solution (using witnesses) is acceptable. An example of an algorithm which simultaneously reveals information is Diffie-Hellman, but the shared secret there cannot be chosen by either party, so cannot itself contain any information.