Let’s synchronize our watches: Determining Clock Skew with Christian’s Algorithm and the Reactive Framework

In every playground race, there’s always one child who sets off somewhere between “On your marks” and “Get set”, gaining an unfair advantage over the honest ones who wait for “Go!”. I faced a similar problem in the design of my Windows Phone 7 multi-player game, Simon Squared, though it was unsynchronized clocks and network latency that were to blame rather than cheats.

The multi-player mode in the game relies on puzzles being shown to all players at the same time, and players race to complete them. Since some puzzles can be solved in a matter of seconds, players who get to see them even slightly sooner than their competitors stand a good chance of getting to the solution first. So I needed a plan for avoiding the digital equivalent of playground squabbles.

Any such plan has to take into account network latency: an unpredictable amount of time can elapse between the server shouting “Go!”, and the phones hearing the message. So I got my server to send out a message announcing that it would shout “Go!” at time T, where T is 4 seconds on from the time on the server’s clock (and broadcast in UTC obviously). This gives even the most far-flung phone plenty of time to receive the message, check its own clock, and then start a count-down.

Bet you’ve spotted the flaw in that straight-away! What if the server’s clock and the phones’ clocks are out of sync?

An Overview of Christian’s Algorithm

That’s where Christian’s algorithm comes in. It gives us a simple method of broadcasting the time at the server to a client whilst allowing for network latency. It works like this:

1. Client sends a message to the server: “What’s the time?” [adding ‘Mr. Wolf’ is optional]. Crucially, it notes the time that it sent the message (call it T_sent)
2. Server responds as quick as it can, giving the time according to its own clock, T_server.
3. When Client gets the message, it notes the time of receipt (call it T_received). Then it does some maths: the round-trip time, RTT, is T_received – T_sent . So assuming that the server responded instantly, and that the network latency was the same in both directions, that means that the server actually sent the message RTT/2 seconds ago. Thus, at the instant Client receives the message, the time at the server is T_server + RTT/2. Then the Client can compare with its own clock and determine the difference – the clock skew.

Since network latency can vary with each request we can get an improved result by trying the whole exercise several times then cherry picking the result which had the shortest round trip time, since that minimises the error in our estimate of the network latency.

So what does that look like in code?

The Server Side – with WCF REST

Well first we need the server to be able to serve up the time:

[AspNetCompatibilityRequirements(RequirementsMode = AspNetCompatibilityRequirementsMode.Allowed)]
[ServiceContract]
public class TimeService
{
    [WebGet(UriTemplate = "/?timeAtClient={clientReportedTime}")]
    public TimeCheck GetTime(string clientReportedTime)
    {
        return new TimeCheck()
                   {
                       ClientReportedTime = DateTimeOffset.Parse(clientReportedTime, CultureInfo.InvariantCulture, DateTimeStyles.AssumeUniversal),
                       TimeAtServer = DateTimeOffset.UtcNow,
                   };
    }
}

This is making use of WCF 4’s REST capabilities. Notice the WebGet attribute on the method, with it’s UriTemplate. If I add the appropriate route  to my Global.ascx file,

routes.Add(new ServiceRoute("Time", new WebServiceHostFactory(), typeof(FeedbackService)));

that will ensure that HTTP GET requests like http://localhost/MyApp/Time/?timeAtClient=2011-03-17T20:19:30.2196972Z get routed to the CheckTime method with the appropriate part of the query string passed into the clientReportedTime parameter.

So that's the server side done.

RestSharp and Rx for Asynchronous Web Requests

Then the client needs to be able to call the server. I’ve been making use of the excellent RestSharp library here:

_restClient = new RestClient(ServerUrl);

...

private IObservable<TimeCheck> GetServerTime()
{
    var request = new RestRequest("Time?timeAtClient={timeNow}");
    request.AddUrlSegment("timeNow", DateTime.UtcNow.ToString("O"));

    return ExecuteRequest<TimeCheck>(request);
}

private IObservable<TResult> ExecuteRequest<TResult>(RestRequest restRequest) where TResult : new()
{
    var subject = new AsyncSubject<TResult>();

    _restClient.ExecuteAsync<TResult>(restRequest, response => HandleResponse(response, subject));

    return subject;
}

private void HandleResponse<T>(RestResponse<T> response, AsyncSubject<T> subject)
{
    subject.OnNext(response.Data);
    subject.OnCompleted();
}

This is where things start hotting up. The first part of GetServerTime is obvious enough: in lines 7-8 I’m constructing a RestRequest consisting of a url and the appropriate query string parameter. Then I Execute it. Now since we’re talking Windows Phone here, I can’t make synchronous web requests – the phone UI has to remain responsive. So I can’t wait and then return the response from the method.

Instead I return an IObservable, an interface you might not be familiar with. This creature is the brain-child of the clever folks on the Reactive Framework team. They like to call IObservable the mathematical dual of IEnumerable. And what they mean is this: IEnumerable is used when you want to pull elements one by one out of a collection. IObservable is used when you want elements to be pushed one by one to you. You can think of an IObservable as being a stream of events. And just like you can build queries on top of IEnumerable, using Where and Select, so you can build queries on top of IObservable.

Here I’m using an IObservable as the channel to push back the result of the Web request when it becomes available – you can see that happening in the HandleResponse method, which is the callback that RestRequest calls when it gets a response back from the web server.

Finally – the Algorithm

Finally we get to the implementation of the algorithm itself: and with the underpinnings in place, it turns out to be one big LINQ query:

public IObservable<TimeSpan> DetermineClockSkew()
{
    var timeOffset = (from tick in Observable.Interval(TimeSpan.FromMilliseconds(100)).Take(5)
                      from timeCheck in GetServerTime().Timestamp()
                      let estimatedOneWayLatency =
                          (timeCheck.Timestamp.UtcDateTime - timeCheck.Value.ClientReportedTime).
                              TotalMilliseconds/2
                      let estimatedTimeAtServer =
                          timeCheck.Value.TimeAtServer + TimeSpan.FromMilliseconds(estimatedOneWayLatency)
                      let predictedClockSkew = estimatedTimeAtServer - timeCheck.Timestamp
                      select new {predictedClockSkew, estimatedOneWayLatency})
        .MinBy(p => p.estimatedOneWayLatency)
        .Select(p => p.predictedClockSkew);

    return timeOffset;
}

Let's step through this line by line:

• Line 1: We start things off by generating a stream of 5 tick events, at 100 millisecond intervals – we’re going to ping the server 5 times, and use the result with the shortest round trip time
• Line 2: Each time we hear a tick we fire off a what’s-the-time request to the server using GetServerTime which we discussed above. The Timestamp() method will stamp each response that we get back from the server with the time at which we received it.
• Line 3: For each response we get back from the server we estimate the one-way latency from server to client by taking half of the round-trip time (when we send a request to the server we send our own time, and the server echoes this back in the ClientReportedTime property of the message)
• Line 4: Now that we have an estimate of how long the message took to get from the server, we can estimate the time at the server at this precise moment.
• Line 5: We can now figure out the difference between the clock on the phone and the server’s clock by comparing the time at which we received the server’s response with our estimate of the server’s time at that moment.
• Line 6: We stash our estimate of the latency, and the estimate of the clock skew into an anonymous type
• Line 7 - 8: We look over all 5 attempts at estimating the clock skew, and we take the one which had the smallest latency. Notice how MinBy returns an IObservable rather than an actual value as it might in good old Linq-to-Objects: it has to be this way, otherwise the whole method would block waiting for all the web requests to complete, rather defeating the our use of asynchronous calls elsewher.

So there you have it: thanks to Christian, the WCF REST framework and the Rx team, a neat and elegant way of determining clock skew between server and phone.

See it in Action

Remember, for a limited time only you can see this in action by downloading my game to your phone or Emulator (for free!) and playing with your friends. Full source code to the whole game is also available.

Finally, judging for the Windows Phone 7 app contest finishes on March 31st, so make sure you check out the entries, and be sure to tell Red Gate what you think of mine!