集合set复制：通过锁定广播实现无全序的容错算法

虽然状态机复制是实现任何理想功能的黄金标准，但它需要对所有交易 (事件)进行完全的总排序（全序），在某些情况下，这种开销是不必要的。

事实证明，在许多自然用例中，特别是规范的简单代币支付用例，不需要全序：作为一个具体的例子，假设 Alice 正在将代币转给 Bob，而 Carol 正在将代币转给 Dan。没有必要完全排序这两笔交易。

FastPay、Guerraoui 等人，2019 年、Sliwinski 和 Wattenhofer，2019 年采用了这种方法，应用于隐私保护交易（参见UTT和Zef），并计划在Sui 平台中使用。

在一个全序的系统中，我们想要的属性是任何人都可以写入和读取相同的有序事务日志，但是现在我们只想写入和读取相同的无序事务集，让我们从刷新日志复制开始，然后定义set replication。

日志复制的定义
客户端和n个服务器：客户端可以提出两种类型的请求：

• read，作为响应返回一个值的日志（或空日志是“⊥”）；
• write(v)，得到一个输入值，同时返回一个响应，这是一个值的日志。

客户端可以在不同时间有多个输入值：

• Termination最终：如果一个非故障的客户端发出了一个请求，那么它最终会收到一个响应。
• Agreement同意：任何两个请求都会返回日志，那么一个是另一个的前缀。
• Validity：日志中的每个值都可以唯一地映射到一个有效的写入请求。
• 正确性：对于一个具有值v的写请求，它的响应，以及在这个写响应之后开始的请求的任何响应，返回一个包括v的值日志。

我们只需删除agreement属性，就可以得到set replication。

集合set复制（Set Replication）的定义
客户端和n个服务器：客户端可以提出两种类型的请求：

• read，它返回一个值set（或空set的⊥）作为响应；
• write(v)，它得到一个输入值，也返回一个响应，这是一个值set。

Termination最终：如果一个非故障的客户端发出一个有效的请求，那么它最终会收到一个响应。

Validity：集合set中的每个值都可以唯一地映射到一个有效的写入请求。

正确性：对于一个具有值v的写请求，它的响应，以及在这个写响应之后开始的请求的任何响应，返回一个包括的值set。

讨论：对单一写者来说没有区别
请注意，当只有一个单一写入者single writer的客户端时，日志复制和集合set复制没有区别：
（单一写者）客户端可以通过给它的操作添加一个序列号来按顺序提交命令，并在集合set抽象的基础上实现其命令的日志。

事实上，集合set复制正在解决单个写入者对象的多次共识（参见Guerraoui 等人，2019 年）。

此外，如果您将空间划分为对象，并允许每个对象由单个客户端（与对象的公钥关联的私钥的所有者）写入，那么您可以允许多个客户端并行处理，只要每个一个正在写入不同的对象。

日志复制 和 集合set复制 的区别在有两个或更多 writer 时可以看出：
例如，如果两个写入需要决定谁先写（假设他们都想在AMM上交换货币），那么日志复制将提供这两个事务的顺序，但集合复制无法做到。

通过锁定广播实现集合set复制
日志复制需要解决多发协议，即使是一个协议也可能在最坏的情况下需要f+1f+1轮。在以前的文章中，我们展示了如何通过重复应用锁定广播来解决日志复制。

集体复制是一个比较容易的问题。它可以被实现为一个单一的锁定广播实例：

Write(v):     客户端驱动锁定广播(v) Read():     客户端查询所有的副本     复制体的回应是：设置所有具有锁定证书的值     客户端等待n-f个响应，并取其联合。

写一个值只是运行一个锁定的广播；读取所有的值只是读取所有的锁证书。
请注意，写和读都需要不断的轮回，并在异步工作。

详细点击标题