handshaking.txt

Suppose Alice and Bob need a protocol for agreeing to perform an action.

The communication delay is T seconds (which we assume to be symmetric).

A standard handshaking protocol is request/acknowledgement. Alice raises her hand
to signal a request. Bob sees the signal T seconds later. When Bob is ready to perform
the action, he raises his hand to signal acknowledgement. So, from when Alice sent the
request, it's at least 2T seconds before she sees Bob's acknowledgement and can perform
the action.

Compare that to an alternative protocol based on preemptive readiness. When either
Alice or Bob is ready to perform the action, they preemptively signal their readiness
by raising their hand, which takes T seconds to be seen by the other party. If Alice
is ready and she sees Bob's hand raised, she can initiate the action. Thus the
latency from when the last person is ready is at most T seconds before the action
can be executed.

An important subtlety is that Alice's readiness can't be based on her perception of
Bob's readiness, or vice versa. Otherwise you can end up in a deadlock where both
parties are waiting for the other party to take the first step. Even without such a
deadlock, if Bob's readiness depends on Alice's readiness, you end up with a round-trip
delay of 2T seconds, which is what we were trying to avoid.

As stated, the readiness handshaking protocol only allows one action to ever be
performed since there is no mechanism for resetting the state: once you raise your
hand, you can never lower your hand again. By introducing a synchronized clock
between Alice and Bob, we can address this problem. When the clock ticks and
Alice has her hand raised and sees Bob's hand raised, she lowers her hand to reset.
Similarly, when the clock ticks and Bob has his hand raised and sees Alice's hand
raised, he lowers his hand. Actually, they're _allowed_ to lower their hands under
those conditions--if they're ready for another action immediately, they would keep
their hands raised. 

An important caveat with this clocked reset protocol is that you're not allowed to
raise your hand within T seconds of the next clock tick. Otherwise you may have a
race condition where Alice lowers her hand at the tick but Bob keeps his hand raised
because he hasn't yet seen Alice raise her hand. So, if you're ready but you're within
T seconds of the next tick, you have to wait until after the tick to raise your hand
to signal your readiness.

Note that the clocked protocol supports maximum throughput. E.g. if Alice and Bob are
always ready, they just keep their hands permanently raised after every clock tick, which
lets one action execute per tick.

To optimize efficiency, you would choose your clock period to be only a bit longer than T
itself since the time to reset is based on the clock period and that's ultimately what
limits the throughput.

Indeed. It's so-called valid/ready handshaking. You see it in AXI and other protocols.