How do you enforce fair decentralized workload sharing among computers or programs?

The problem is that malicious workers can exploit the others to get more than their fair share of work done, or to do less than their fair share of work. I'm thinking of this in the context of computers (or phones, or IoT nodes…) participating in a mesh network, where you want them to all share the work of routing each other's packets, but you cannot control the behavior of each one because they aren't all under your control. But this could equally be applied to ad-hoc cluster computing or other purposes.

You could have them all inspect each other's programs to ensure that they will behave fairly. But that's impractical and reliability might be impossible.

You could do it how cryptocurrencies do it, and incentivize the doing of work with monetary rewards, and/or use consensus to ensure consistency in operation between different workers. But the first method doesn't work if you have nothing of value to distribute, and the second doesn't work if each worker is in a different position and doesn't have access to all of the same resources as any given other.

But there's a way to apply the methods described in the previous paragraph to this problem anyway. It adds another layer to provide the conditions necessary for the methods of fairness enforcement used by cryptocurrencies to work. This layer is a cryptocurrency.

When a worker does a piece of work (e.g. a mesh node routing a packet), it receives a reward of some amount of this cryptocurrency. When it has work that needs to be done, it must spend some of its cryptocurrency to pay the other workers to do work for it (e.g. route its packets). To reduce overhead, several pieces of work can be paid for at once. Instead of mining new currency for doing work (which results in a deflationary currency, which I think is unnecessary for this purpose), each worker gets a specific amount of cryptocurrency just by joining the network.

This provides something of value to exchange for work, and does not require that workers have consensus on the results of their actual work (which might be impossible to get), only that they can provide proof of work. The proof of work is used to enable consensus about cryptocurrency transactions, as usual. In that layer, all workers have more or less equal ability to ensure that the proof of work is valid and so form consensus.

Proof of work depends on the type of work being done (routing, distributed computing, etc.), so I won't cover that here. (Also, I have no idea how to do that.) Several proof- of-work algorithms already exist (though most just do work for the sake of doing work, not doing anything useful; see Namecoin for an exception).

Open problems include how to keep workers from creating new virtual workers and funneling their starting balance into their own wallets, how to implement proof of work for specific applications, and how to implement taxes and welfare (necessary because some workers have more work to be done and some have more resources—consider edge nodes and central nodes in a mesh network) without a central government, etc.

I'm aware that all I've invented here is effectively capitalism for computers. (If you did the same thing with people, it would be nothing new.) But I've never heard of such a concept before.
-- notexactly, Dec 04 2015

Decentralized autonomous organization https://en.wikipedi...nomous_organization
Mentioned in my anno. How this should be implemented, I think. [notexactly, Jun 03 2016]

It is to easy to crib a system like this by having dummy nodes join and then produce massive quantities of faked circular traffic. Essentially the same idea was tried and failed in file sharing services; was easy to puppet the system using fake nodes and transactions.
-- WcW, Dec 05 2015


Circular traffic doesn't increase any money. But in the open problems paragraph, I did mention the related issue that fake new workers could be created to the same effect.

I'm sure a Satoshi Nakamoto-level crypto genius could come up with elegant solutions to all of these problems.
-- notexactly, Dec 05 2015


That would spam the blockchain with thousands of times more transactions than is necessary.

The blockchain is the shared history of transactions in the current crypto-currency implementations. Out of 7B people, we might have a few dozen monetary transactions per day. But, with IoT or routers in general, we could easily generate 10,000 transactions per person per day, as even this halfbakery post reading is split into several separate packets as it goes across the net.
-- sophocles, Dec 06 2015


//It is to easy to crib a system like this by having dummy nodes join and then produce massive quantities of faked circular traffic.

Maybe the edge should pay into the pool to run the infrastructure for each send/receive.

//The blockchain is the shared history of transactions in the current crypto-currency implementations.

Surely there is some better suited cryptocurrency out there that scales better for this kind of mesh application.
-- ixnaum, Dec 07 2015


// That would spam the blockchain with thousands of times more transactions than is necessary. […] even this halfbakery post reading is split into several separate packets as it goes across the net. //

Good point. This is partly solved by the part where I said

// To reduce overhead, several pieces of work can be paid for at once. //

which is currently done in practice with Bitcoin micropayments, but it would still be a problem eventually, just like it is with any cryptocurrency that keeps its blockchain forever. Probably the best solution is to have each node keep a local copy of only some amount of the blockchain, not going back all the way to genesis, and let only a few servers handle the whole thing. It does probably make a 51% attack a bit easier, but I think this is actually done in practice currently without serious problems.
-- notexactly, Dec 07 2015


I have recently realized that this should be implemented using a DAO. [link]
-- notexactly, Jun 03 2016



random, halfbakery