22

I am designing a prototype for a distributed database that could work across vast distances of space, like the goals behind IPFS working at planetary, or galactic, scale. I want to solve the problem, at least theoretically (with a practical prototype POC in JavaScript demonstrating the key algorithms), of doing database transactions when the data is in different planets or different stars or different galaxies. What this boils down to is that, latency will be a problem no matter what. Things can only move so fast, and it takes 8 minutes for light to travel from the sun to the earth, let alone from one planetary system to another. So none of the traditional distributed consensus or transaction algorithms would probably work in my understanding (like two-phase commit).

What I imagine so far is that you would have the database copied in several places within a planet. This would be for data that is common to the planet. You can get away with latency issues here at least. Then every so often someone wants to do some data transaction with the data on another planet. You can't get away with latency here. So what do you do?

You do something like how communication may have worked hundreds of years ago when people travelled by horse or by foot. How did they guarantee atomicity in that situation? What are the types of things they would do to keep their data "in sync" in different parts of the world, and resolve any conflicts that may have emerged? It may take weeks or months to send messages from one place to the next. What happens during this time? How would you translate this to a database system?

Say for example you want to perform an ATM transaction and your origin planet is PlanetA at StarX, while you're visiting PlanetB in StarY. When you make a purchase with a universal form of money on StarY:PlanetB, it should at some point deduct that amount from StarX:PlanetA. If you are on your last pennies and charge something for $5 on StarY:PlanetB, it should know you are out of money. Meanwhile, your partner is on StarZ:PlanetC a hundred million miles in the opposite direction. You both are using the same credit card and deducting from the same bank account at your origin, StarX:PlanetA. How would you go about allowing for both people to get on with their lives and purchase things with their ÅTM card?

Perhaps you would divide the money to start, so you each get half to spend. Then when you run out, you can ping (and wait for weeks) to ask your partner for more money or something. Perhaps you would copy your half of the bank account to your current location, and deduct your stuff locally, syncing it slowly (over weeks) to the origin planet.

How would you solve this problem? Of doing an ATM transaction with multiple people sharing a bank account across these vast distances? Besides this specific question, I would be interested to know more generally where I can find more info on this sort of topic. But the key question is that, how to handle database transactions where the latency is a very long time (days or weeks or longer)? The key-er question is, how did people throughout history perform such "atomic" transactions when they had to travel vast distances very slowly?

I believe this is a valid problem to solve, as we will soon likely have to deal with at least communicating between Mars and Earth, where it takes about 3 minutes for light to travel. And once we are capable of that, then communicating with other planets or solar systems might be in order.

Maybe NASA communicating with their satellites might have some insight 🤔.

If bank transactions are a bad example for history, then what is a better example? Perhaps war plans is a better example. Perhaps purchasing land was another example, or trading of some sort.

  • 31
    This si the same problem that the Templars solved in the 11th century. Don't attempt synchronicity - just resolve trust, allowing construction of "signed financial instruments". If you war game this, you will also quickly rediscover bullion famine, when the valuable renewable commodity of one culture/planet (spices or silk) can only be purchased with the non-renewable commodity (gold and silver) of another. – Pieter Geerkens Aug 8 at 2:50
  • 5
    It has been suggested that this might get an answer on worldbuilding rather than here. – Mark C. Wallace Aug 8 at 11:29
  • 3
    Read 'Neptunes Brood' by Charles Stross. He details a similar system as a central part of the story. The storey also involves a certain amount of fraud which is enabled by the system. – simon at rcl Aug 8 at 14:54
  • 7
    Until recently even modern bank transactions took three days to clear, though any technical reason for that had vanished many years before. The point was that the medieval bankers were trusting each other, not the customer; issuing banker's drafts, not cheques. – Robbie Goodwin Aug 9 at 0:41
  • 3
    You demand partition tolerance. This requires that you abandon either consistency or availability (or both). See the CAP theorem and the PACELC theorem which forces you to choose between latency and consistency. – Eric Towers Aug 10 at 9:08
41

Historically, the solution to this was the letter of credit, circular note, traveller's cheque, or similar. Basically, it was an attestation that the bearer of the document had deposited a certain amount of money with the issuing institution. No attempt was made at "atomicity", rather, the goal was "eventual correctness", where the money eventually ended up in the correct place.

| improve this answer | |
  • 1
    It's worth noting that those are simply "cheques", basically. The answer to the OP's question is dead simple: cheques bounced all the time. It did NOT "work" in the sense the OP has asked. – Fattie Aug 10 at 14:55
  • 10
    @Fattie Not exactly - a cheque is ME saying "I have the money with Big Bank, Inc." - a traveller's cheque is Big Bank, Inc saying "corsiKa has money with us". The amounts are the same, but people tend to trust banks more than random tourists. – corsiKa Aug 10 at 19:07
  • sure, but they're basically cheques "from banks" (as you say, rather than "from me"). that system bust all the time. – Fattie Aug 10 at 19:12
36

Quite simply, they did not guarantee atomicity or synchronicity, they guaranteed eventual consistency.

The general principle is simple: it doesn't matter when the money actually gets moved, provided that it's done in a 'reasonable' amount of time and is reserved for the specified transaction.

The way you achieve this is very simple too. For this to work, you need exactly two things:

  • A bank you trust at the place you're coming from, known as the issuing institution.
  • A bank that your bank trusts at the place you're going to, known as a corresponding institution.

The steps to 'move' the money then work as follows:

  1. Prior to departing, you go to the issuing institution and request a circular letter of credit. Ideally, you should request a number of them instead of just one so that you do not have to 'move' all of the money at once. Chances are that there will be a minimum amount that each must be worth. Upon doing so, the issuing institution will require payment equal to the value of the letters of credit plus some small fee (historically it was around 1% of the value).
  2. When you go on your trip, you take the letters of credit with you.
  3. On arriving, you go to one of the corresponding institutions listed on the letter of credit, and request to cash it in the local currency (or whatever currency), and they give you the monetary value listed and invalidate the letter of credit (just like how banks today handle cashing a cheque).
  4. If you requested multiple letters of credit and did not cash all of them, you can then (probably) return to the issuing institution and have them converted back into the original cash.

That's quite literally all it takes. This general principle has been in use since as far back as the Renaissance, and was very widely used by merchants and travelers alike prior to the advent of traveler's cheques, money orders, and ATMs.

This guarantees that you can't spend the same money twice, and eventual consistency is guaranteed by either having people get letters of credit going in the other direction, or by an intermittent 'settlement of accounts'. It has some limitations in terms of efficiency and requires you to know ahead of time how much you might need, but entire economies worked on this relative simple system of transference of credit (and technically still do depending on how you think about the way that credit cards work).

| improve this answer | |
  • 4
    This sounds kind of like a predecessor of "traveler's cheques", which I think was one of the primary services offered by American Express when I was growing up. – Barmar Aug 8 at 23:56
  • 3
    There's also hawala: en.wikipedia.org/wiki/Hawala – Acccumulation Aug 9 at 5:22
  • 4
    @NooneAtAll forgery protections varied over time, but a lot of it was the usual basic stuff like the use of special inks and papers, watermarks, and other things that were difficult for forgers to copy at the time. I imagine in an interplanetary setting as outlined by the OP much more advanced techniques would be used, along the lines of modern anti-forgery methods used with bank notes (albeit even more advanced than that probably). – Austin Hemmelgarn Aug 9 at 12:13
  • 3
    Fraud was very much an experience. That's why batch transaction processing was taken up so very quickly by banks, despite the high cost. The transaction could be turned around whilst the person trying to pass the forgery could still be found. Even after that international business used vast amounts of cash when there was absolutely no trust: for example, until the late '80s all the world's international telephone bills were annually settled in an Hawaiian hotel by an exchange of US dollars. Smaller businesses would use a mutually-trusted party -- the import/export agent. – vk5tu Aug 10 at 1:34
  • 5
    @vk5tu The reference to international telephone bills sounds really interesting – do you have any details to help me look into it further? – dbmag9 Aug 10 at 9:53
1

Two Generals Problem

To more directly answer your question, in technological history, this is a form of Two Generals Problem, which not only factors in latency but the risk of losing transmissions (highly likely over the dangerous vastness of space) when sending data between two places with a risk of data loss/delay inbetween.

From a technical standpoint, atomicity would require the sender to effectively say to the receiver 'can I have an exclusive lock on this data?' and 'please don't make any modifications to this whilst I'm updating it', sending the data, and then saying 'you can unlock this data now' or the lock expiring if an unreasonable amount of time has passed.

Spoke and Hub Model

Assuming it takes 8 minutes to send, 8 minutes to receive, plus any errors, ensuring atomicity would be very time consuming. Effectively what you would need is a unique, exclusivity container based on trust; trusted bank withdraws 100 credits, puts it into the pre-signed (using other planet's key), encrypted container, container has instructions (E.G send to Xarg's account), sends container to planet, receives receipt of container being picked up.

Essentially, this is what occurred with certified horsemen carrying letters with wax seals and royal approval. The model is also a form classically known as Spoke and Hub model.

The issue of latency (and message failure) is likely to be better covered on technological pages.

| improve this answer | |
  • 2
    This is History.SE, not Worldbuilding.SE, and I'm not aware of what you describe ever actually being used. – Mark Aug 10 at 1:47
  • 2
    @Mark Your comment is particularly vague. What part of my description? Two Generals problem is a historical technological problem which required a solution in the development of TCP. Spoke-and-Hub is used in logistics delivery networks, also historical delivery models - typically postmen deliver to a hub (say a port, coach station or sorting office) and from there it's delivered onto a spoke (say a house). Sealing wax is also well known, historically. If you refer to the encrypted container - BitCoin uses this in the form of harddrive storage. This is technological history. – SSight3 Aug 10 at 13:43
  • 3
    @Mark Also just because I cite technology - to solve a technological problem - does not mean it's 'worldbuilding'. Technological history is still history too. Just because it's not horses doesn't mean it isn't a solution to the issue. Two Generals problem is effectively how two commanders communicate by any means - not merely horses, and is an issue of antiquity, even if the paradox definition in computers (and thus banking) is historically recent. – SSight3 Aug 10 at 13:46
  • 2
    @SSight3, prior to the advent of modern low-latency communication, banks did not use the techniques you're describing. Instead, they used systems based on trust and on the difficulty of forging documents. – Mark Aug 10 at 21:26
  • 3
    @SSight3 You describe solutions that could be used for such problems. Can you provide some evidence that these are the solutions that have been used in history for bank transactions in time "when they had to travel vast distances very slowly"? For example, hub-and-spoke is a popular model for interbank clearing currently, but I'm not sure if it was popular before e.g. the age of telegraph. It's well known that the 'letter of credit' model was used historically at that age, but arguing that hub-and-spoke is also relevant requires some evidence of how it was used before 19th century or so. – Peteris Aug 10 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.