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.