# TagTime Universal Ping Schedule: Reference Implementation

#1

I previously had this buried in another thread but let me put it here instead, and translate it to the lingua franca, aka Javascript. Thanks to @chipmanaged for nudging me to do this.

First some constants (and a global variable):

``````const log   = Math.log   // Keep
const exp   = Math.exp   // Mathematics
const max   = Math.max   // Beautiful
const round = Math.round

const GAP = 45*60       // Average gap between pings, in seconds

const URPING = 1184083200 // Ur-ping ie the birth of Timepie/TagTime! (unixtime)
const SEED = 666          // Initial state of the random number generator
const IA = 16807        // (7^5) Multiplier used for LCG random number generator
const IM = 2147483647   // (2^31-1) Modulus used for RNG

let state = SEED // Global variable that's the state of the RNG
``````

Next the functions for generating random numbers:

``````// Return a random integer in [1,IM-1]; changes the RNG state.
// (This is ran0 from Numerical Recipes and has a period of ~2 billion)
function ran0() { return state = IA * state % IM }

// Return a U(0,1) random number
function ran01() { return ran0()/IM }

// Return a random number drawn from an exponential distribution with mean = GAP
function exprand() { return -GAP * log(ran01()) }
``````

And finally the functions to compute the next ping time:

``````// Take previous ping time, return random next ping time (unixtime). If the next
// ping is less than 1s after the previous one, artificially push it forward so
// that it's a full second later.
// NB: this has the side effect of changing the RNG state and so should only be
//     called once per next ping to calculate, after calling prevping().
function nextping(pung) { return max(pung+1, round(pung+exprand())) }

// Compute the last scheduled ping time before time t
function prevping(t) {
state = SEED
let p = URPING         // Starting at the beginning of time, walk forward
let prevp = p          // computing next pings until the next ping time is
let prevstate = state  // greater than or equal to t
while(p < t) {
prevp = p
prevstate = state
p = nextping(p)
}
state = prevstate
return prevp
}
``````

To get the next ping times starting now (say thatās time `t`), you first call `p = prevping(t)`. So `p` is now the most recent ping time, according to the universal ping schedule, before time `t`. Then keep doing `p = nextping(p)` and `p` will always be the upcoming ping time.

PS: In Javascript you get current unixtime in seconds with `Date.now()/1000` (just `Date.now()` returns it in milliseconds).

#2

So people using different GAP values will get a completely different set of pings, right? Actually if Iām reading this correctly, everyone will get the same ārelativeā ping schedule, but scaled by GAP, right?

I have always wondered whether it would be possible to have a single universal ping schedule, such that someone with a bigger gap simply gets a subset of the pings of someone with a smaller gap. That is, if person A is using gapA and person B uses gapB, with gapA > gapB, then whenever A gets a ping, B also gets a ping at the exact same time (but not necessarily vice versa). From another point of view, imagine that as gap approaches 0 the ping schedule becomes infinitely dense; pings disappear (but never move) as you smoothly increase the gap, until at gap = infinity there are no pings.

It seems like this should be possible in theory but I havenāt thought too hard about how to implement it. It would be sort of nifty if people with different gap settings still got pings simultaneously some of the time.

#3

Yes.

Sounds right.

That would be amazing. Iām even willing to change the universal algorithm to make it happen.

(I think the way to do that would be to pick a future date when it switches and get all existing implementations on board in time.)

## Sketch of a possible algorithm with @byorgeyās property

You can approximate TagTimeās poisson distribution by discretizing time, letās say into seconds, and just deciding independently each second with fixed probability whether that second should have a ping or not. That probability is in fact 1/g where g is the gap parameter in seconds. So we need to do a bernoulli trial with probability p at time t ā bern(p, t) ā with the constraint that every bernoulli trial at time t with pā>p ā bern(pā, t) ā will say yes if bern(p, t) says yes. For that we just need to pick, for an arbitrary unixtime t, the p threshold above which the answer is yes. So a function pthresh(t) that gives a probability. Now if you want to know if thereās a ping at time t for gap g, you just check if pthresh(t) < 1/g.

I donāt know if itās a dealbreaker that this approach means computing that function again and again for each unixtime until you find the time of the next ping. Maybe worse, when TagTime first starts up, to ensure the RNG is in sync, it has to start at the dawn of (tag)time and walk forward, checking pthresh for every single second up to the present. Maybe thatās fine or thereās a clever way to avoid that.

As for the pthresh function, I think I see a way to write it if we also discretize and bound the possible gap lengths. Like you ask āis there a ping at this time at probability 1/60? no? how about 2/60?ā etc. The first p that yields āyesā is the p that pthresh returns.

#4

I was just going to suggest something similar! I donāt understand pthresh though, could one not just generate a random number in [0,1] each second and check whether it is less than 1/gap? If gapA > gapB then automatically a ping for person A is a ping for person B.

A possible trick to avoid running through every second since the ur-ping: some RNG algorithms allow fast-forwarding in logarithmic time.

#5

Yes, thank you!

I didnāt know about fast-forwarding RNGs. Fascinating. You could also just store the RNG state and current unixtime so you never have to start from very far in the past.

#6

Any linear congruential generator (of the form seedā = a * seed + c mod m for constants a, c, and m) has that property, since you can represent the transition step as multiplying the column vector (seed, 1) by the matrix [ [a, c] [0, 1] ]. Repeatedly applying the transition corresponds to taking powers of the matrix, which can be done in logarithmic time via repeated squaring. (Of course all of this has (mod m) thrown in everywhere appropriately, but it doesnāt change the basic argument.) LCGs arenāt necessarily the state-of-the-art, but they seem perfect for this application.

Edited to add: I think the algorithm @dreev has outlined (as enhanced by @mvr) should work very nicely indeed!

#7

And actually, since TagTime is already using ran0, an LCG with c = 0, fast-forwarding becomes even simpler: you donāt need matrices at all, you are just computing powers of IA, mod IM.

#8

Beautiful! Want to help implement the reference implementation? I have the current implementation (the code above) running on Glitch here:

So we could say the new universal ping schedule is the existing schedule until 2019-01-01 at which point it switches to the new algorithm.

#9

I donāt think so. Itās a pretty tiny amount of computation for each check. Even on a slower embedded device I think you could probably check at least one million unixtimes per actual second (about 11 daysā worth of pings).

#10

Should we care that ran0ās period is only 2 billion? If computing a random number every second thatās 68 years before it starts repeating. Some of us may still be alive in 68 years!

For the original algorithm that period was definitely fine because there was just one random number computed per ping so with a 45 minute gap thatās like a couple hundred thousand years of non-repeating ping gaps.

PS: Googling around about periods of random numbers I, amusingly, came across this:

#11

I really donāt think it matters. Even aside from the unlikeliness of a TagTime user still being alive and still using TagTime in 68 years, what exactly would be the problem? That somehow they would remember ping patterns from 68 years ago and it would ruin TagTimeās effectiveness for them, because their subconscious would know when to expect the next ping?

#12

It sounds farfetched when you put it that way but I guess I was thinking if something incredibly unlikely and memorable happens then youāll know thatās coming again in 68 years. Maybe an epic ping day that motivates you to work more when the Great Wraparound approaches. Or vice versa for an epic ping famine. Of course if Iād just never mentioned the 68-year periodā¦ But, yeah, this is still farfetched.

One more farfetched scenario: conceivably we could care about subsecond granularity. Some people may answer pings in well under a second if the UI is smooth enough. And if you want to track the time you spend answering pings, wellā¦

Still fairly far-fetched, but throw in the unknown unknowns and maybe itās worth having a longer period just in case? I just learned from a paper by LāEcuyer that itās easy to pick constants for a multiplicative linear congruential generator that have longer periods than we could even conceivably care about.

So might as well go with one of those if weāre changing the algorithm anyway!

#13

Sure, thereās certainly no harm in picking an LCG with a longer period!

#14

If we change the algorithm, we should make sure we have a long period and we solve the Ran0 correlation issue.

#15

Could we make the ārandomā value a function of the time (hashing maybe?), so rather than generating the next ping time we find it by comparing every timestamp until we find the next one.

Computers are fast enough that this is not a problem at a 1 second resolution. (and probably for any resolution > human reaction time. /handwave)

Caveat: Itās a while since I studied the relevant math for all this.

#16

#17

Oh, thatās a great idea. Then the whole thing about fast-forwarding is moot.

#18

Based on the link @insti posted, it looks like the best choices would be FNV-1a or some variant of Murmur. FNV-1a is much simpler to implement. Both look like they give a reasonable distribution of hash values when calling them on consecutive input values (our use case), though Murmur looks perhaps slightly more uniform? One thing to be careful about/do more research on is that a good distribution of values is not quite enough: we also need consecutive hash outputs to be uncorrelated, which is not necessarily an important criterion for choosing non-cryptographic hash functions, so I donāt know how well these would fit the bill.

On that page it is claimed that Murmur is faster, but that seems to be due to the fact that it works 4 bytes at a time instead of 1 byte at a time, so there is probably not much difference (or it might even be slower) on small values: we are going to be using it on 32-bit Unix time stamps.

Overall it seems to me FNV-1a on 32-bit values is the way to go. For reference, the algorithm is as follows:

``````hash = 2166136261  // magic FNV offset basis for 32 bits
for each byte:
hash = hash xor byte
hash = hash * 16777619  // magic FNV prime for 32 bits
``````

(If TagTime is still around in 2038 we can easily specify a switchover date to the 64-bit version of FNV-1a, to work with 64-bit unix timestamps.) Iāll play around with this a bit and get a feel for how well it would work.

#19

By using strings rather than integer timestamps we can more easily add salt if one doesnāt want the universal schedule `1533467950 - Insti secret`

Or maybe add fractional seconds to the timestamp. (Do we care about sub-second accuracy? (I donāt)) `1533467950.1234`

And handle 64 bit timestamps without changing the algorithm again. `129518309081725000`

#20

Iāve been playing around with this using Murmur2

Do you know of a statistical test we can use to check this?