Looking for two-way communication/consensus/contract algorithm for use in marriage proposal
If you're feeling up for something particularly geeky, you might enjoy a fair exchange protocol, either one based on gradual release (see e.g., this paper) or one based on Bitcoin (e.g., this).  The number of steps is very large though!  Probably not suitable to carry out by hand.

You could try a simpler protocol:


Alice picks a message $m_A$, computes a commitment $C(m_A)$ to  $m_A$, and reveals the commitment $C(m_A)$.  For instance, maybe Alice writes down $C(m_A)$ in view of Bob.
Bob picks a message $m_B$, computes a commitment $C(m_B)$ to  $m_B$, and reveals the commitment $C(m_B)$ -- say, writing it down too.  (Steps 1 and 2 can be done simultaneously or in any order.)
Alice opens her commitment to reveal $m_A$ (e.g., she writes $m_A$ down on the piece of paper).  Bob verifies that the message matches her commitment.
Bob opens his commitment to reveal $m_B$.  Alice verifies that the message matches his commitment.  (Steps 3 and 4 can be done in any order; but they shouldn't be started until both Steps 1 and 2 are complete.)


In your case, Alice could choose as her message "Bob, will you marry me?" or "Bob, let's not get married yet" and Bob could choose as his message "Alice, will you marry me?" or "Alice, let's not get married yet" and then you could compare at the end.

There are various ways to do a cryptographic commitment.  One way is with a cryptographic hash function (you could use a web site to compute it for you).  A simpler method is to secretly write down the message on a piece of paper, then put the paper in an envelope, seal the envelope, and place the envelope on the table in front of both of you.

See, e.g., https://keybase.io/blog/cryptographic-coin-flipping for a gentle introduction to related ideas.



Another idea is to execute a two-phase commit protocol.