Summer of 2012. Suddenly several “integer-as-a-service-providers” spring from nowhere. They deliver “artisanal integers”. Integers which (they claim) are “hand-crafted and guaranteed to be unique and hella-beautiful”.
Are you still with me?
Perhaps it helps to have a look at one of the three such services still operational today: Brooklyn Integers, Mission Integers (after San Francisco’s historic Mission District), and London Integers.
Still in the dark?
Here’s my very own, freshly minted, unique integer: $420557015$.
Anyone can check that this is a genuine Brooklyn-integer by looking up its corresponding number-site. In our case the URL would be: http://www.brooklynintegers.com/int/420557015/.
Please pause a moment to admire the hipster-style web-design and the wonderful tagline:
we have infinity on our side (Brooklyn Integers)
Why do we need integer-as-a-service-providers?
This story starts in 2010 when Aaron Straup Cope wants to play with all of the buildings encoded in OpenStreetMap.
Each of these 67 million buildings was added to the database by first creating four or more “nodes” and then grouping them together in a “way”. Aaron wanted to build a catalog of all of these buildings. Because the “ways” had already a numeric ID in the OpenStreetMap-database (using 32-bit integers), he generated a new numeric ID for each and every building, starting at 32-bits plus one, to avoid collisions between the two databases.
He met a similar problem one year later while working on a project called parallel Flickr. Here the idea is to allow individuals to run and maintain their own local copy of Flickr, consisting of their own photos, those of their close friends as well as photos they like.
Assume a fair number of people have set up their local Flickr site and the very worst happens: Flickr itself shuts down. Can we recover the (to us) relevant part of Flickr from all our local copies?
Yes. That is if all of us had the discipline to maintain the original Flickr-IDs and metadata in our parallel Flickrs. A collision between two or more of our databases would only mean we share a copy of the same photo.
If however (and this is infinitely more likely) we all used our own idiosyncratic system to name files, rebuilding the network from our little Flickrs would quickly become hopeless.
Parallel Flickr is an exercise in how individual people can take control and responsibility to archive material they leave on global social media sites such as Facebook, Google+, YouTube, Instagram and the likes. How can we collectively maintain generated content in case the service pulls the plug?
Another example. Consider a large group of people, each of them geotagging and archiving their own tiny part of a larger collective neighbourhood. What’s needed to construct the bigger picture from their individual efforts?
When Aaron asked his pal Mike over coffee in San Francisco’s Mission District, the reply was: “So, are you suggesting that we need something like a centralized ‘integers as a service’ platform?” As a gag Mike also suggested that rather than any old unique integers, there would probably be a demand for hand-crafted artisanal integers.
It’s how Mission Integers was born. And immediately forgotten. There already exist methods to deliver unique IDs, such as the UUID scheme.
The idea was rekindled when Aaron moved to New York and started the Gowanus Heights Neighborhood Project. Here again they needed unique IDs. Because the long strings of alphanumerical characters and dashes provided by UUID are less efficient at the database layer, they needed Mission integers, or perhaps Brooklyn integers, or both.
In order to avoid collisions between these two artisanal integer providers, Mike claimed the even numbers for Mission (as San Francisco is on the ‘left hand’ coast) and Aaron the odd ones for Brooklyn (New York lying on the ‘right hand’ coast).
Remember all of this started in order to empower individuals against the frills of global players, type Facebook.
And now, this new system would depend on a two-party US-based monopoly? Most certainly not!
Along came Dan Catt who created London Integers, using a rather different look-and-feel. “Both Mission and Brooklyn have gone for a hipster boutique type of look, which I wanted to eschew. The London I know is dirty, gritty, beautiful and punk.”
London ‘artisan’ Integers would be multiples of $9$ and in order to avoid collisions with the others he took the maximal integer minted by both Brooklyn or Mission, added a couple of millions to it, and just started distributing integers.
Someone could look at an artisan integer and work out if it was a London Integer by adding up the digits, repeatedly if necessary to get to single digit. If that’s $9$ it’s a London Integer.
If it's not a London Integer then you can tell if it's Brooklyn or Mission on the odd, even front.
Where’s the math in all this?
Ideally, integers-as-a-service-providers will be set up in all major cities, and why not, even in small communities.
Nelson Minar solved two of the most imminent problems arising from having multiple providers of artisanal integers:
- all parties producing integers should be aware of one another and honour their respective offsets.
- given an artisanal integer one should be able to figure out where it came from
Nelson did this using secret magical powers better known as “maths”. (Aaron Straup Cope)
He used the Cantor pairing to generate a unique integer $z$ corresponding to the $y$-th number produced by the $x$-th foundry:
$z = \frac{(x+y)(x+y+1)}{2} + y$
Conversely, if you’re given the artisanal integer $z$, you can work out its integer-provider by following these rules:
$w=\lfloor \frac{\sqrt{8z+1}-1}{2} \rfloor,~t = \frac{w^2+w}{2},~y=z-t,~x=w-y$
Elegant as this is, there’s a serious flaw. The number of providers will always be significantly smaller than the number of integers they mint. Therefore, most integers will not be used, ever.
Here’s my two-pence worth of advice to build a slightly more economic system:
- The $x$-th foundry should only mint multiples of $p(x)$, the $x$-th prime number.
- As any time $t$ one should know the product $T$ of all prime numbers of foundries in operation.
- In order to decide whether the $x$-th foundry can distribute its $y$-th number $n = y \times p(x)$ one computes $gcd(n,T)$ and look at its largest prime divisor. If this is $p(x)$, the number $n$ can safely be minted. If not it will eventually be distributed by the foundry corresponding to that largest prime factor.
- With a little bit of extra work one gets a fairer system. Decompose $gcd(n,T)=p(x_1)^{e_1} p(x_2)^{e_2} \dots p(x_k)^{e_k}$. Then $n$ will be minted by the foundry having the largest exponent. If there are $m$ equal maximal exponents $e$ corresponding to $p(x_{i_1}), p(x_{i_2}) \dots p(x_{i_m})$, then $n$ will be minted by foundry $x_{i_j}$ where $j = e~mod(m)$.
- A new foundry will be associated to the next prime number, will advertise its existence to the existing services (changing $T$) and respect as initial offset the smallest prime multiple larger than the maximum integer already minted by the others.
No doubt you will come up with a much cleverer idea! Please leave it in the comments.
Sources:
– H/T Christian Lawson-Perfect via Twitter
– Aaron Straup Cope: “The “Drinking Coffee and Stealing Wifi” 2012 World Tour”
– Rev Dan Catt: “London Artisan Integers; distribution, Hotel Infinity, punk, an excuse & explanation of sorts”