How do distributed applications verify that the data was processed correctly?

Question

There are a lot of projects out there that rely on the public sphere to process data for them, but I do wonder how they ensure that every computer participating has processed the data properly.

The first one that comes to mind is Bitcoin mining. I know that the Bitcoin network has a mathematical way of verifying that the data has been processed correctly (I'm not going to go into that here).

But, when I think about other projects, such as the SETI@home project, I often wonder how they know that every participant is behaving correctly; how is it that they know the data was actually processed, or that the results being returned are accurate. The only validation I can think of would require them to also process the same data, meaning that the distributed model is moot.

---

The game of connect four has already been solved, but let's say that someone wanted to develop a project that solved the game of connect four using a distributed public network (the internet). The server would send down a large chunk of data to one machine to process, for example it would send down a starting point and the machine would have to process all possible boards with a depth of 5 and use a predetermined formula for scoring, then return the best move to the server.

• How does the server know that this was the best move using the algorithm?
• How do we guarantee that there isn't a rogue actor that is consuming the service and replacing the predetermined scoring algorithm with a junk one that yields the incorrect best move?

Answer 1

You are asking about two different problems, result verification and byzantine failure.

For result verification, the general idea is to find a way to verify the answer more quickly than it can be computed. There are two approaches, which I will call strong verification and weak verification. Strong verification involves a proof that the result is (in)correct. For example, this is a defining characteristic of NP-complete problems: an answer takes exponential time to compute but can be verified in polynomial time.

Weak verification can be used in situations where it is impossible to prove the correctness of a result, and only attempts to verify the result to within some acceptable confidence interval. This is typically a heuristic-based approach, such as SETI@Home's result verification method (as mentioned by MichaelT).

Byzantine systems are those where processes can fail in arbitrary (including malicious) ways. There are a number of methods for achieving Byzantine fault tolerance. The most common is perhaps state machine replication, where the critical step is ordering inputs to ensure that the replicas have a consistent view of the world.

Input ordering is commonly achieved via consensus algorithms. Consensus algorithms are pretty much what they sound like: a way to ensure that there is sufficient agreement about a data value within the system before it is used.

Byzantine failure is a complex problem and this is a very brief and necessarily incomplete summary. For more information, please use the included links and especially the references that they provide.

Answer 2

The use of a global snapshot, in conjunction with an analysis algorithm can (and is) used for this type of verification.

The Snapshot Algorithm works like this:

The observer process (the process taking a snapshot):
    Saves its own local state
    Sends a snapshot request message bearing a snapshot token to all other processes
A process receiving the snapshot token for the first time on any message:
    Sends the observer process its own saved state
    Attaches the snapshot token to all subsequent messages (to help propagate the 
    snapshot token)
Should a process that has already received the snapshot token receive
a message that does not bear the snapshot token, this process
will forward that message to the observer process. This message was obviously sent before 
the snapshot “cut off” (as it does not bear a snapshot token and thus must have come from 
before the snapshot token was sent out) and needs to be included in the snapshot.

From this, the observer builds up a complete snapshot: a saved state for each process and all messages “in the ether” are saved.

Once the observers have all generated a snapshot of their local state, a central analyzer can pull these snapshots, reconstruct them, and run verification on them.