A Thought Experiment Regarding Time.

- Van Warren May, 10, 2008

consider a radio capable of receiving and transmitting a simple signal indicating what time it is.

please ignore all the knowledge you might have about GPS and other time systems for this discussion.

consider two such radios that transmit to each other what time they think it is.

Each radio uses the other's notion of what time it is, to correct its own notion of what time it is.

provided that each radio's time differs from the true time by a random, and not systematic amount,

the time manifested by the radio's will become the true time, after sufficient exchanges.

-----

problem: the radios have to take turns transmitting and receiving. if somehow they were to transmit and receive in sync, they would never hear from each other and synchronization would be impossible.

this problem can be solved by having the radios tranmit and receive in a pattern that is guaranteed to overlap properly after some number of iterations.

it can also be solved by having the radios operate in full duplex mode, listening on one frequency and transmitting on another.

this solution assumes that the speed of light is not frequency dependent.

in fact, such pair of clocks define an experiment could be done to measure the frequency dependence of c, if such dependence exists.

-----

If the radios a relatively close, and sufficiently out of sync, the propagation time does not affect the time value held by the two clocks.

As the clocks are moved apart, and become more closely synchronized, propagation time starts to become significant.

because of the intended end-application and the above statement, we must therefore measure the propagation time.

-----

in the ideal case, the propagation time from radio A to radio B is the same as that from B to A.

however, because of multipath and propagation assymmetries, this is not always true.

so the first piece of data we get from the two radios is the distance from each other,

but since that depends on the accuracy of the clocks in the radio, we are left using uncertain rulers as the experiment proceeds.

we could take the smallest time to be the true propagation time, but that could be an artifact of a fast running clock.

--------------

besides all this preamble, what I really want to do is devise the simplest possible exchange of messages by which two clocks 
could come into synchronization with each other.

as a side effect of this I would also like to characterize the signal propagation time between the two clocks.

we could start initially by assuming that the two signals take two different paths.

as the clocks begin to sync up we could examine the results to see if this was in fact the case.

--------------

so lets start with a naive algorithm and see what issues crop up.

we will proceed in full duplex so we don' have to devise clever broadcast and listen strategies.

but by doing so, we have introduced an asymmetry into the problem, that one clock transmits at a higher frequency than the other.

since we cannot exclude a frequency dependence on either the speed of light, or propagation characteristics, this is unacceptable.

the clocks could take turns with who tranmits at the higher frequency, this would move the asymmetry to the beginning and return us to a situation that is similar to the half duplex case.

interesting limitation right off the bat.

so now we will come up with an artificial clock that transmits at the same frequency in receives and operates without blanking in full duplex.

now the clock cannot tell if the message it is receiving is itself, or another clock!

so the limitation persists...

i will call this, "the starting problem". it is fairly serious and i cannot see an immediate remedy, so I will return to the half-duplex case so I do not have to introduce a frequency asymmetry.

-----------------

so in the half duplex case both radios are broadcasting on the same frequency.
they transmit packets that contain a time stamp encoded as a binary number.
for now we will not worry about the specifics of the encoding, though they too can introduce asymmetries.
we will rather intially concern ourselves with the pattern of broadcast to see what statements we can make about
guaranteeing that a successful two way communication and synchronization occurs.

this is similar to the conversational problem that happens frequency where two people start to talk at the same moment and then stop.
it is rare for this deadlock to continue past two attempts. 

to study this we will come up with a bare minimum of notation that is a sequence of broadcast and listen intervals, timed in the local reference frame.
we will seek to guarantee that no matter how out of sync the clocks are, or how fast or slow they are, that we can accomplish an eventual synchronization event defined as follows:

a succesful synchronization event is one where one clock receives the time packet of another, then sends its own packet, then receives an acknowledgement. 

suddenly two packet types have emerged out of nothing!

one is the act of acknowledging, we will call this an ACK, the other is the timepacket itself, which we will call the timestamp for now.

before this let us label the transmit and receive sequences as follows:

T, R, T, R, T, R

now let us improve on this notation by using a sequence

1, 1, 1, 1 to indicate alternating periods of sending and receiving, talking and listening.

1, 2, 1, 2 indicates that we listen for twice as long as we talk

now if both parties engage in 1, 1, 1, 1 behavior, and their clocks are somehow perfectly synchronized, they will not be able to synchronize further. we could exploit this fact as a condition of synchronization, that if they can't talk and they are already synchronized and we are done, but we might have to wait an infinitely long time to discover this, and we would prefer to avoid such situations.

in fact for any pattern that both clocks commit to, the same situation holds true. This spells trouble because it show there is a limit to what we can know in the case of deterministic clock patterns. we are trying to synchronize two clocks but if they are already synchronized we may have to wait an infinite time to find that out.

to break this impasse we could start both clocks at the same time, but this requires that the clocks originate in the same location and we may not want to require that.

we could start in full duplex and then move to half duplex, or we could have a contract that says that the one clock is designated first sender and one clock is first receiver and that first receiver never broadcasts until first sender has been heard. this has the limitation that if for some reason the clocks are shielded from each other, that we have to wait an infinitely long time to discover this.

we could partition each clock into an always sending and always receving, but this degenerates to a full-duplex situation discussed above.

so now let us break the impass with a third radio, containing a third clock, whose sole purpose is to solve the starting problem.

We will call this third radio, with great originality simply, "C" for Creator. The job of C is to send out one starting pulse and then cease.

When A receives the start message from C, it broadcasts a timestamp to B.

When B receives the timestamp from A, it broadcasts a timestamp back to A.

Thus the timestamp and the ACK have been merged into one message, the timestamp, and we have eliminated the waiting problem.

The need for the C clock is eliminated if both clocks start out in proximity to each other, but we wanted to address the general case.

We need to assume that in the worst case the clocks are running at completely different rates. We do not have to reintroduce the ACK, because the receipt of the timestamp itself continues to suffice.

This leaves us never having to wait longer than one transmit period of the slowest clock, which is quite acceptable compared to infinity. It is in fact optimal.

we can place the C protocol on the A clock, requiring B to listen until it hears from A and then begin the synchronization process. this introduces the asymmetry of making A somehow different than B.

we could make A and B identical, with both being listeners until one is randomly chosen to be the starter. This still introduces the asymmetry of a starter.

If both are chosen simultaneously then we have the dual broadcast problem identified above.

If neigher are chosen, nothing ever happens and we must wait forever to begin synchronization.
-----------

next up: defined the synchronization process and measure the path characteristics.

when the clocks sync up, and we shall soon define exactly how that takes place, we get into the position of having a certainty of the degree of sync we have acheived. once this has taken place, we can begin to look at the time between successive timestamps and determine elapsed time of required to propagate the message.

the goal after all is synced clocks at disparate physical locations that will record events seen from their own reference frames and compare notes using the timestamped information. the side effect of propagation delays helps us to ascertain the uncertainty in the synchronization.