title: Automatic message routing on a sneakernet
body: <p>I'm working on a project which needs a system that boils down to a strange exercise in network protocol design. The particular details of the situation are complicated and irrelevant, so here I'm going to compare it to a sort of obligatory sneakernet.</p>
  
  <p>Say there are a number of desktops in buildings spaced throughout a forest or mountain range or arctic plateau or something. They aren't networked, because laying cables between the buildings is prohibitively expensive. (In this case, literally physically impossible, but I digress.) People commute between the buildings regularly, though, and everyone has a flash drive on them. One of the first things they do when arriving at a new building is plug this flash drive into the desktop there. When it's plugged in, a piece of software starts up and reads the data from it, and can transfer data to and from it freely. You can assume that the desktop has infinite storage space, but the drive does not.</p>
  
  <p>The desktop is loaded with messages that need to get to other buildings. Each message has metadata indicating a source and destination, as well as potentially any other necessary protocol information. The drive is also carrying messages intended for <em>this</em> building, which the software would unload first. Then, based on some algorithm, the software loads new messages onto the drive.
  Each building is connected to five or so other buildings by roads that the carriers travel along. Any given building isn't likely to be directly connected to any other <em>specific</em> building, but there is always at least one path (via other buildings) between any two given points.</p>
  
  <p>I'm hoping to minimize the human interaction necessary to get the messages between buildings. The sender would have to specify a destination, obviously, and we can reasonably expect the carriers to know their very next stop, but perhaps not further than that. I'm also hoping for something that's perfectly distributed - something that doesn't need to rely on any central server.</p>
  
  <p>What's the simplest system the software can use to automatically route messages from one building to another? Ideally, each independent instance of the software would decide on the same route for the same input. Given that each drive/carrier and each building already has a unique ID, how could the software automatically map out all of the connections in the network? How could such a system handle discovery of a new building or road? If some carriers know they have a definite far off source, destination, and waypoints, how should that be handled for messages that could feasibly follow that same path (for part and/or all of their route)? How could the system handle "packet loss" (e.g. one of the carriers crashes en route)? Is there a way that the system could be abused or broken? What could I do to prevent that?</p>
  
  <p>Also, say I wanted to update the software on the desktops. I could require each drive to carry a copy of newest version they've encountered, but that's not very space-efficient. Instead I could have them just carry the newest version number, as well as a list of the IDs of any buildings that they visited which needed the update. When the drive hits a building with the newest version, the software there purges the list and creates an automated message to those buildings asking whether they still need the update. If they reply "yes", it packages up the locally stored deltas and sends them off. The patches would, in this case, be signed by the system's developer to ensure authenticity. Is there a way this could be distributed though (i.e. what if each building's resident hacker was given access)? Or more specifically, how could it deal with delta collisions?</p>
  
  <p>Any questions or suggestions for clarity would also help; what I've described is only logically similar to what I'm going to apply it to, so I don't know whether I've assumed something that isn't obvious or forgotten to mention important details.</p>