这是我的要点问题(我想尽可能清楚):
- 我有一组计算机，以点对点方式连接，因此没有中央服务器。
- 每台计算机有时(但不是经常，正常运行时间应该在 0.98 左右)离线。此外，连接有时会丢失，或者两个节点可能由于某种原因无法连接。但大多数情况下，连接会正常工作并且相当稳定。
- 这些计算机中的每一台都保存着一堆更新的副本。更新按渐进顺序编号。
- 在任何时间点，外部用户都可以连接到网络中的任何计算机并发布(已签名，因此更新可通过网络验证)更新。
- 然后应通过网络分发更新，并将其添加到每台计算机的更新堆栈中。
到目前为止一切顺利。我知道这样做相当简单:
- 通过网络中的计算机已建立的连接发送更新。
- 如果计算机在某个时候掉线，当它恢复在线时，更新已排序和编号的事实将允许它再次与网络同步。
现在，当有多个用户时，我的问题就来了。如果两个用户同时尝试发布两个不同的更新，连接到网络中的两台不同计算机，会发生什么情况？
- 如果他们只是分发更新，一些节点将有一个更新，而另一些节点将在他们的堆栈中有另一个不同的更新，所以我失去了连贯性。
- 如果我实现某种形式的锁定机制，在发布更新之前尝试锁定所有节点，我可能会遇到各种与饥饿相关的问题。
- 我考虑过选择一台计算机作为主计算机并让所有用户都连接到该计算机，但是我该如何选择哪一台作为主计算机呢？出现以下问题:
- 如何选择师傅？
- 这也应该是动态的。如果主机离线会怎样？
- 由于可能存在错误连接，并非所有节点都会看到一个节点在线，即使它是在线的:在极少数情况下，可能会发生在线并可以连接到所有其他计算机的主计算机将被其中之一视为离线。然后会发生什么？
是否有解决此类问题的已知策略？我打赌有。我尝试在网上查找，但我真的不知道如何表达我要查找的内容。
最佳答案
这个答案不完整，不幸的是含糊不清，因为我仍在努力理解此处链接的论文。但我想发布到目前为止我发现的内容。
同步分布式数据复制系统似乎有两种主要方法。
- 悲观
原子性和锁属于“悲观”算法的范畴，在任何一个用户发布更新时阻止所有其他用户访问。
正如您提到的，这种方法容易出现死锁和/或饥饿问题。
- 乐观
In contrast, optimistic algorithms let data be read or written without a priori synchronization, based on the "optimistic" assumption that problems will occur only rarely, if at all. Updates are propagated in the background, and occasional conflicts are fixed after they happen.
http://pages.cs.wisc.edu/~remzi/Classes/739/Spring2004/Papers/optimistic-survey.pdf
根据维基百科，version vectors是用于乐观复制系统的“主要”数据结构。但是，正如您所指出的，在去中心化环境中存在明显的并发问题。
“如果两个用户同时尝试发布两个不同的更新，连接到网络中的两台不同计算机，会发生什么情况？”
作为 Brent Hoon Kang notes :
... it is extremely rare that different users (or sites) make an update at the same time. However, such rare events do happen in practice, and their consequence is prohibitive: An update may be completely lost by different versions having the same id. Indeed, such an occurrence is present in the CVS logs of sourceforge.net
根据 Hoon 的论文，显然“修复”此问题的一种方法是在版本 ID 前加上原始节点 ID 和本地时间戳。然后随着更新被“传播”(我还没有掌握)，节点可以识别版本何时不同，尽管版本 ID 相同，合并它们，并创建一个新版本来传播(如果我理解正确的话)。
然而，随着节点数量的增加，分配唯一 ID 变得缓慢而复杂。
If the sites are introduced through linear chaining (e.g., A introduces B, B introduces C, C introduces D, and so on), the total size of all site names could grow quadratically in terms of number of sites.
版本向量还有其他问题。
Hash histories提供另一种方法来进行乐观复制。
有了 HH，不需要节点 ID，节点可以随时加入或消失。出于我无法理解的原因(在论文中描述)，跨网络的数据同步也比 VV 的收敛速度更快。
散列涉及一定的版本冲突概率，但 AFAIU 现代散列可以做到这一点 negligible在实践中。
Hoon 的完整论文(相关): https://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1351.pdf
海报摘要: http://roc.cs.berkeley.edu/retreats/summer_02/posters/hoon_poster.pdf
由于源代码链接已关闭，我对一些细节有些迷茫，但当我弄清楚时，我会用伪代码更新这个答案。如果我误读了您的问题或这没有帮助，我深表歉意。
关于networking - 跨计算机网络的原子更新同步，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40027940/