分布式应用程序如何验证数据处理是否正确？

Question

有很多项目依靠公共领域为他们处理数据，但我想知道他们如何确保每一台参与的计算机都能正确地处理这些数据。

首先想到的是比特币的开采。我知道比特币网络有一种数学方法来验证数据处理是否正确(我不打算在这里讨论这个问题)。

但是，当我想到其他项目(如SETI@home项目)时，我常常想知道他们如何知道每个参与者的行为都是正确的；他们如何知道数据是实际处理的，或者返回的结果是准确的。我所能想到的唯一验证就是要求他们也处理相同的数据，这意味着分布式模型是毫无意义的。

连接4的游戏已经解决了，但假设有人想要开发一个项目来解决使用分布式公共网络( internet)连接4的游戏。服务器将向一台机器发送大量数据以进行处理，例如，它将发送一个起点，该机器必须处理所有深度为5的可能的板子，并使用预定的评分公式，然后将最佳移动返回到服务器。

• 服务器如何知道这是使用该算法的最佳步骤？
• 我们如何保证没有一个流氓演员正在消耗服务，并将预定的评分算法替换为垃圾算法，从而产生不正确的最佳动作？

Answer 1

您问的是两个不同的问题，结果验证和拜占庭失败。

对于结果验证，一般的思想是找到一种方法，以更快地验证答案比它可以计算。有两种方法，我称之为强核查和弱核查。强有力的验证需要证明结果是正确的。例如，这是NP-完全问题的一个定义特征:一个答案需要指数时间来计算，但可以用多项式时间进行验证。

弱验证可以用于在不可能证明结果正确性的情况下，并且只能尝试在某种可接受的置信区间内验证结果。这通常是一种基于启发式的方法，例如SETI@Home结果验证方法 (正如MichaelT所提到的)。

拜占庭系统是指进程可能以任意(包括恶意)方式失败的系统。实现拜占庭容错的方法有很多。最常见的可能是状态机复制，关键步骤是排序输入，以确保副本具有一致的世界观。

输入排序通常是通过共识算法实现的。协商一致的算法听起来很像:一种确保在系统中使用数据值之前就有足够的一致性的方法。

拜占庭式的失败是一个复杂的问题，这是一个非常简短和必然不完整的总结。有关更多信息，请使用所包含的链接，特别是它们提供的参考资料。

Answer 2

使用全局快照，结合分析算法可以(而且也是)用于这种类型的验证。

快照算法的工作方式如下:观察者进程(获取快照的进程)：保存自己的本地状态，向所有其他进程发送带有快照令牌的快照请求消息--在任何消息上第一次接收快照令牌的进程:发送它自己保存的进程，将快照令牌附加到所有后续消息(以帮助传播快照令牌)，如果已经接收到快照令牌的进程接收到不带快照令牌的消息，该进程将将该消息转发到观察者进程。此消息显然是在快照“截断”之前发送的(因为它不包含快照令牌，因此必须是在发送快照令牌之前发出的)，因此需要包含在快照中。由此，观察者构建了一个完整的快照:为每个进程保存状态，并保存“以太”中的所有消息。

一旦观察者都生成了本地状态的快照，中央分析器就可以提取这些快照，重构它们，并在它们上运行验证。