The purpose of this document is to elucidate Mojo Nation's distributed metatracking architecture, and some of the motivations and implementation issues. "Metatracking" is the process of exchanging "phonebook" info about other brokers. It includes both listing brokers who provide specific services, and about their menu of services and prices (the "yellow pages" part of a phonebook) and giving information about how to contact a specific broker (the "white pages" part of a phonebook). In the coming weeks, as distributed metatracking is implemented, this document might be updated to reflect new desiderata or design decisions. Or it might not. In any case, the most up-to-date version of this file can always be found in CVS on SourceForge, and is browse-able over the web via this link. (You have to click on the version number to get the document.)
The following system is designed with three goals:
I have deliberately avoided mentioning possible improvements which I don't think are required right now, but at the end of this article I do talk about future addition of sophisticated reputations. I'll first describe the basic idea and the desired systemic behavior and then the implementation.
This idea is simply "every broker a metatracker". I think we can use the current metatracker protocols and the current source code to deploy really good distributed metatracking.
Every broker would come with metatracking service enabled by default. There would be a "starting set" of metatrackers, gleaned from the bootpage and hardcoded constants. When you do "hellos", which I call "advertising", you send hello messages to a subset of the metatrackers that you know. When you query (either "list servers" or "get contact info"), you likewise query a subset of the metatrackers.
All "phone book" information that you learn about other servers (i.e. services offered, prices, comm strategy, public key) is added to your persistent db and you resell that information when others query you (assuming you haven't disabled metatracker serving).
Now, how will this behave at the systemic level? I think that if each agent makes a judicious choice of which subset of known metatrackers to use, the system-wide behavior will be good.
The desired system-wide behavior is twofold:
First, it should be efficient. Propagation of new phone-book information shouldn't take too long. For example, if you change your comm strategy because you have dynamic IP service and you were off-line for a while to play Quake, you want people who already know you and who want to do business with you to be able to discover your new IP address as soon as possible.
Also it should be efficient in that the traffic required to implement metatracking shouldn't swamp people's capacity. The described system uses roughly three times the current aggregate traffic for metatracking (ask for details if you doubt this estimate), but spread out more evenly instead of focussed on central points.
Second, the system should be robust, self-healing, and self-balancing. If one, or even more than one, metatrackers drop off the net at once, the system should automatically and efficiently replace the lost services. If a metatracker starts to become widely used and it chokes under the load, brokers should automatically and efficiently switch to less loaded metatrackers.
I think that if each agent uses the following simple strategy, the network will exhibit all of these desired characteristics.
The strategy: whenever you need to deal with metatrackers, you sort the list of known metatrackers using your handicappers, then do your transaction with all of the top N. (It seems like N should be larger for "hellos" than for "get contact infos", and smallest of all for "list servers". I'm envisioning something like 50 hellos, 10 get contact infos, 3 list services.)
You use our current handicapper funcs, plus one new one which rates a metatracker more highly if it returns more hits. (Also, it might be a good idea to add some "serendipity" handicapper that makes you use a random broker once in a hundred times, as a way to discover new brokers.)
The reason that the network would be efficient is that some metatrackers would become "big" (that is: widely preferred) due to the bias towards popular metatrackers. This means when you advertise new phonebook info, you will probably advertise to at least one of the "big" metatrackers, and the info will propagate relatively quickly throughout the whole network.
The reason that the network would be robust is that each broker would know many metatrackers, and would be able to automatically fall back on alternatives if the most preferred ones are not answering. The addition of a "serendipity" handicapper would make it even more robust, at the cost of a little bit of efficiency.
The reason that the network would be self-balancing is that a metatracker that was overloaded would suffer from increased latency and would raise its prices or drop some requests. This would be taken as evidence by our handicappers to select alternative metatrackers.
There is one more detail that I haven't addressed -- how do you make sure that you know enough metatrackers? You need to keep a good surplus of known metatrackers so that if a lot of them disappear when you aren't looking, you won't be down to zero.
The current plan is that most servers will also offer metatracking service, so when you do a "list blob servers" and learn about 50 new brokers who offer block services, you are also learning about 45 new metatrackers. (This is because the entry for each broker in a 'list blob servers response' contains the full phonebook entry for that broker, not just the blob-service part.)
Also, there will be a few default metatrackers listed in the bootpage, which will hopefully always be available.
There are only six things that need to be done:
Integrate MetaTrackerLib with the metatracker's db. This makes the MetaTrackerLib info persistent, and it means that when you learn about someone then you automatically resell their phonebook info to others.
Greg says this is "hard", and it is all stuff that he is most familiar with, so he'll do it.
Change advertising code to advertise to N metatrackers. Change querying code to query N of them. (There is an issue here about whether you wait for the other responses to come back after you get the first response. My feeling is you never need to wait, once you get a useful response -- the other responses will get added to your MetaTrackerLib db whenever they come in anyway.) The N should be chosen out of the full set as described above.
This one is easy.
Fix it so that you lookup contact info on fast fail or timeout. (Currently you lookup contact info on SUPERfast fail, i.e. a CannotSendError, but not on fast fail nor on timeout.)
This one is medium. It involves transaction/comms code that I have touched most recently, so I'll do it. I'm guessing I can do it in 1 day.
Fix it so that when someone asks you for a service you don't provide, or they offer you too low a price, you return your current phone book info. Fix it so that when someone returns that to you, you enter it into your MetaTrackerLib db.
This one is easy.
Add a handicapper that prefers metatrackers who give you lots of results. Optionally add a handicapper to for serendipity.
This one is easy.
In order to prevent old phonebook info from floating around and overwriting new phonebook info, add a sequence number or timestamp to hellos. In order to prevent denial of service by poisoning phonebooks, add signatures to hellos.
This one is hard. I'd like to do it, and I want to do it in the most SPKI-friendly way, but if I don't have time then Bram, Greg, Drue or Nejucomo could do it.
The SPKI / SDSI standard uses s-expressions as the basic datatype, just as we do, and it builds up structured data objects with name, type, and value just as we do, and it uses a key-oriented PKI model just as we do. It is a very good fit. Greg's first-pass proposal for how to sign phonebook entries is almost exactly like Rivest's solution. (Basically you add a field to the object which contains the signature information and which is special and gets excluded from the object when signing or verifying the object.)
The abstraction of "handicapping" provides a way to plug in more sophisticated reputation algorithms. One such example would be an algorithm that rates a metatracker more highly if the brokers that it introduced you to turned out to be more valuable to you. This would allow your view of the Mojo network to be customized. Servers that are closer to you in network topology and have low latency would be recommended to you by your preferred metatrackers. Similarly so for content trackers that specialize in your favourite content. Another algorithm could implement distributed reputations in which you allow your friends' opinions of a given metatracker to bias you. Both of these could be integrated with this strategy by the simple addition of a new handicapping function.