How to perform important transactions over vast distances?

Question

I asked a similar question on the History Stack Exchange, but it was suggested I might get better feedback here.

How can you guarantee atomicity of a transaction in a high-latency system?

High-latency systems are sometimes ones where information must travel vast distances (such as between planets, stars, or galaxies). Atomicity means that only one being can modify the record at a time (basically), and it is guaranteed to either succeed or fail, not partially be applied (as in a bank transaction subtracting from one account and adding to another account).

Or if you can't guarantee it, how do you handle important transactions, such as financial transactions, real-estate transactions, war transactions, trade transactions, etc. if they are operating on time frames of weeks or months?

How was this done in ancient times? Has anyone in history solved this problem? How would you go about building a world where two people can be in separate places billions of miles away, and yet make a trade (financially or otherwise)?

I also thought of this in terms of video games. Say you wanted to play a multiplayer game with someone. The only way you can play a real-time game with someone is if they are within a certain distance from you. If they are on the same planet like Planet Earth, then the latency is small enough as to be imperceptible. But larger latencies such as if you were on Jupiter or separated by planets or stars, there would be no way to play a real-time game with someone (as far as I can tell). But transactions are a bit different, they don't necessarily need to be real-time, they just need to be truthful or something, in the long run, and not run into erroneous states.

How do you do this?

Answer 1

What they did in the olden days was one of two things:

• Either have a trusted party hold the data and record the transactions. This was the method of choice for just about everything except real estate, which, in some places and at certain times,

• Linked ownership to the possesion of the deed / title to the property. This method was used when there was no reliable central registry -- think the Middle Ages.

The principle of ensuring the atomicity, consistency, isolation, and durability of a transaction by means of having one trusted third party hold the data is simple: there is only one register, and only one party who can update it. If the transaction is in the register, it is considered executed; if not, not.

The trusted third party can be the central office of a bank; or the land registry (called cadaster in some countries); or the shareholder registry.

Banks with international branches used this method on a worldwide scale. In practice, the local branch in, for example, Hong Kong, would immediately honor the transaction without waiting for confirmation from, for example, London, but it will hedge its exposure by getting a conditional letter of credit to be released when the confirmation came through.

As I said, at some times and in some places, transactions involving real estate used a more primitive method linking ownership to the possession of the title / deed to the property. Whenever a conflict arose related to the ownership of a piece of real estate, the party which could produce the actual document won.

It's that simple.

Yes, having one central trusted party hold the data and register the transactions communicating over very high latency links limits the speed and the amount which can be transacted. In modern days, what they do is take some risk. For example, when paying with a payment card, if the amount is low enough the payment network may confirm the payment without waiting for the bank to check the transaction; there is a risk that the bank will reject it, but it is assumed that overall the speedup is worth it.

Answer 2

For really long distance travel you must take your wealth with you

I agree entirely with AlexP, but there are additional factors that needs to be taken into account when considering the entirely astronomical distances involved - the expected lifespan of the participants and ability to realise the wealth being transferred.

The following assumes that there is no faster than light (FTL) travel or information transfer available. If there is FTL but it is non-instantaneous then the principle below still holds but the distances for each example increase.

Short range example:

• Person S lives on Earth and accumulates considerable wealth (buying power) on Earth.
• Person S travels through space for 2 years to observatory O that is 0.3 light years from Earth (in the Oort cloud)
• Before leaving Earth, Person S initiated a credit transfer from Earth to observatory O (signal travelling at lightspeed), so his money is available when he arrives.
• Note that this presupposes that observatory O has a financial agreement with Earth which would require at least 0.6 years to establish – 0.3 years for a signal from Earth to reach observatory O and 0.3 years for observatory O’s acceptance to be received on Earth – but this is quite feasible. Even if observatory O didn’t like the terms of the first contract offered and it took multiple offers and counter-offers to come to an agreement, this could still be achieved within a few years.
• Person S arrives and makes a purchase. Observatory O happily accepts his money, because they can use it to purchase supplies, information / entertainment etc from Earth that: a) they want; and b) are confident they will receive. Even if there is a dispute with the vendor that delays delivery by a year or more, the money can still be spent.

Long range example:

• Person L lives on Earth and accumulates considerable wealth (buying power) on Earth.
• Person L spends half their wealth purchasing a starship and leaves the rest on Earth.
• Person L travels through space for 1500 years (Earth frame of reference) in suspended animation and arrives on small planet B in the vicinity of Betelgeuse, over 600 light years from Earth.
• Before leaving Earth, Person L initiates a credit transfer from Earth to planet B,
• Note that this presupposes that planet B has a financial agreement with Earth which would require over 1200 years to establish – more than 600 years for a signal from Earth to reach planet B and the same for planet B’s acceptance to be received on Earth. If multiple communications were required then negotiations could drag out for ten thousand years or more – which is likely because...
• Person L arrives and wants to make a purchase. The question for the vendor on planet B is – what are they receiving in return? The minimum time to realise the wealth is over 1200 years, in the event that they want to purchase some information that can be transmitted by Earth. (They transmit the credit back along with an order and 1200 years later receive the Friends episodes they ordered.) They are losing the use of their money for a vast period; there is a high probability that any vendor, bank or civilisation they attempt to deal with will no longer exist by the time their order arrives; and they have no recourse if the "money" is not honoured.

Broad principle: Once the latency of transactions approaches a certain percentage of the expected lifespan of the participants, transactions will not occur. Once the latency approaches a percentage of the lifespan of the financial institution, transactions are impossible. (By the time an agreement is reached and a transaction is commenced the financial institution will not exist to complete the transaction.)

• Looking at a historic example - there is a reason that European explorers carried trade goods rather than letters of credit when dealing with tribal peoples. Even if the tribes understood the financial model involved they would have been unable to redeem the letters of credit.

• The most hard science fiction example I can think of is Flare Time by Larry Niven - the ramships traded information and technology they had acquired at their previous stops but never counted on the same market still existing even if they eventually returned to a planet.

Answer 3

It’s been proven to be impossible — it’s known as the Two Generals' Problem. Given a communication channel that isn’t 100% reliable, it’s impossible to use it to synchronise certainty of message delivery. It’s reliability that’s at issue, not latency — if your channels have high but known latency and are 100% reliable then there is no problem, just a long time lag. However, it’s hard to see how such a channel could be 100% reliable — there’s always the danger of a power failure or misaligned antenna or natural disaster at the other end.

Answer 4

Managing "state"

In software design, there's a concept called the "source of truth" (SoT). The idea is that, to guarantee atomic updates to some data, the change must be fully written to a SoT as a transaction. Once this is performed, the transaction is "committed", and cannot be undone. If the write fails, the entire transaction is discarded.

For many systems, there is a single source of truth that records all transactions.

However, this doesn't have to be the case. Each piece of information must have a single SoT, but unrelated data can be safely divided between several SoT.
(Aside: The plural of "Source of Truth" can be "Sources of Truth", to avoid the strange s in Source of Truth's)

One trick I find pretty interesting, is that a source of truth can be moved (or more precisely, migrated).

Migrating

To migrate, the "old" source of truth just needs to record the location of a "new" source of truth, then stop accepting transactions.

Any system which relied on the old SoT can then just connect to the new SoT instead.

In practice, this can get very complicated, though it's relatively simple in concept.

Migrating: Bonus exercise

If the location of a SoT can change, does the "location" information for this SoT also need to be stored in a SoT?

Answer: Yes. I've already dealt with this in the migration section, how did I do it?

Regarding latency

All that really needs to be done, is to move the SoT for each piece of data closer to where it's needed, using the migration described above.

For example: bank accounts could be migrated as people travel around the galaxy. For a shared/company account, funds within the account could be broken down and given to separate branches.

Things to remember

• There's no free lunch. If the SoT is far away, at least one round-trip is required to access it, or alternatively, to request that it be moved.
• Data that doesn't ever change can be duplicated without risk of being incorrect. (caching)
• Sometimes slightly outdated data is "good enough" for now and can fixed later. (the common example for this is the view count on a youtube video)

Answer 5

All those problems existed in medieval Europe, including months-long delays or even years in case of war, and transactions nonetheless took place.

Essentially they worked by either

• producing physical objects which act as the registry, either definitively, or until the transaction can be authoritatively recorded in a central registry

• Making more people aware of the transaction, treating the general public or specific individuals as an ad-hoc registry

Financial Transactions

These were handled by letters of credit, akin to banker's drafts. In a nutshell, a bank in one location takes a deposit of gold or other valuables, and issues a letter which can be drawn on a bank in a distant location. For this to work the banks must have a stock of gold to draw against. For gold you can substitute uranium, plutonium or unobtainium. Letters of credit were easier to transport, conceal and protect from theft.

The primary responsibility for proving authenticity of such letters and detecting forgeries lay with the receiving bank, and many secret methods were used to verify them such as seals, embosses, secret marks, handwriting and so forth, just as today banknotes have anti-forgery holograms and watermarks.

Real estate transactions

To obtain good title to land, you would have possession of a bundle of documents (called "title deeds") proving a chain of title, from some original grant of title which is uncontested. Each document would be a deed setting out what title was transferred, any conditions attached (such as a duty to pay rent, a duty to pay towards maintenance of churches, limitations on permitted use and so forth).

To convey title (e.g. to sell the property) you would hand over the entire bundle, together with a new deed documenting the transfer. In this way the bundle grows with every transfer.

The advantages is that a central registry is not required, but this system can be combined with a system of registration, registering the title as it exists at certain points is a protection against loss of the documents or forgery.

Note that this is still commonplace in England even though England has now moved to a central registry system for recording title. For properties which haven't been transferred in the last few decades, the bundle is still definitive.

Witnesses, notarisation and publicity

Contracts and agreements are written in physical form which is difficult to alter, and witnessed by persons who give their name, and the location where they can be found. In case of dispute, these witnesses can testify that the contract is valid.

Notaries are a special case of witnesses. A trusted person can record a copy of the document (or just details of when the document was notarized, who signed etc), and keep it safe. In case of dispute, he can consult his records.

The general case of this is essentially "spreading it around". The agreement can be published in newspapers, posted in the town square, and so forth. As long as enough people know about the agreement, it becomes impractical to deny it.

So war agreements can be proved by announcing them widely:

• posting in the public square,

• broadcasting on radio and television,

• Memorializing in stone tablets or monuments

• having them cried about town by "town criers" (officials whose job it is to make public announcements): "Hear ye, hear ye, hear ye! On Michaelmas his Majesty the King did treat with the King of France that ..."

• having lavish ceremonies to celebrate the agreements with large public attendances attracted by free food, drink and entertainment.

The public ledger of crypto-currencies are a special case of this.

Indentures

Two copies of the contract can be written side by side on a single piece of paper, and both signed and sealed by all parties. The document is then folded (indented, hence the name) and torn down the middle, so that each party has a copy. Proof that the two halves belong together is given by the shape of the tear, which is unique. Proof that the documents haven't been altered, is given by the difficulty of erasing the ink used. If words appear on one copy and not the other, then these must have been added later.

These were typically used for contracts for a number of years of personal service such as apprenticeships.

Distant transactions

These were handled by "powers of attorney". (The word "attorney" means "appointed person").

You appoint a person in a distant location to exercise a limited power to undertake certain transactions on your behalf, and record the powers they have in a document using one of the above methods.

They then transmit to you what they have done in a similar method.

In this way you can enter into an agreement to buy a distant property (land in another country, or on another planet). An attorney in London will have instructions to sell the property. When you agree to buy, you get a physical document proving the agreement, which you take with you to your new residence in Northumbria. You present the letter to the attorney in the new location, who conveys title to you. This works because to take possession, you need to travel, and you take your proof of entitlement with you.

Sometimes ambassadors were given limited powers to enter into agreements on behalf of the sending country.