问题标签 [consensus]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
8 回答
3323 浏览

algorithm - Lamport 的 Paxos 中的矛盾使纸变得简单

阶段 2. (a) 如果提议者从大多数接受者那里收到对其准备请求(编号为 n)的响应,那么它会向这些接受者中的每一个发送一个接受请求,以获取编号为 n 且值为 v 的提议,其中 v 是响应中编号最高的提案的值,或者如果响应报告没有提案,则为任何值。

如论文所述,

提议者通过向一组接受者发送提议被接受的请求来发布提议。(这不必是响应初始请求的同一组接受者。)“

但据我了解,如果我们将阶段 2. (a) 更改为:

如果提议者从大多数接受者那里收到对其准备请求(编号为 n)的响应,则它会向任意一组多数接受者发送一个接受请求,以获取编号为 n 且值为 v 的提议,其中 v 是响应中编号最高的提案,或者如果响应没有报告提案,则为任何值。

该算法将失败,以下是一个示例。考虑总共有 3 个接受者 ABC。我们将使用 X(n:v,m) 来表示接受者 X 的状态:提案 n:v 是 X 接受的编号最大的提案,其中 n 是提案编号,v 是提案的值,m 是X 曾经响应过的最大编号的准备请求的数量。

  1. P1 向 AB 发送“准备 1”
  2. 两个 AB 都以不接受任何编号小于 1 的请求的承诺响应 P1。现在状态为:A(-:-,1) B(-:-,1) C(-:-,-)
  3. P1 收到响应,然后卡住并运行得很慢
  4. P2 向 AB 发送“准备 100”
  5. 两个 AB 都以不接受任何编号小于 100 的请求的承诺响应 P2。现在状态是:A(-:-,100) B(-:-,100) C(-:-,-)
  6. P2 收到响应,选择一个值 b 并将“接受 100:b”发送给 BC
  7. BC接收并接受accept请求,状态为:A(-:-,100) B(100:b,100) C(100:b,-)。请注意,已选择提案 100:b。
  8. P1 恢复,选择值 a 并将 'accept 1:a' 发送到 BC
  9. B 不接受,但 C 接受,因为 C 从未承诺过任何事情。状态为:A(-:-,100) B(100:b,100) C(1:a,-)。选择的提案被放弃,Paxos 失败。

我在这里错过了什么吗?谢谢。

0 投票
1 回答
186 浏览

matlab - Matlab KNNClassify 共识

我使用 knnclassify 共识。我尝试使用共识在类标签中查找缺失值。

这是我的代码;

这是我的工作空间;

我的工作空间良性和恶性我的班级价值观 http://imgbox.com/EmWvlqnv

代码不是返回错误而是 pred 在所有行中返回 NaN 并返回一个警告;

我尝试欧几里得、余弦、城市街区和相关性。如何解决这个问题?

0 投票
2 回答
139 浏览

distributed-computing - 服务发现如何不是集中配置的子集?

我正在研究ZooKeeperConsulEureka等共识型工具,它们似乎都在推销相同的解决方案:

  • 服务发现
  • 动态、集中的配置管理
  • 同步原语
  • 共识算法

然而,我对这些东西了解得越多,就越难以理解服务发现与动态的集中式配置管理(KV 对)系统有何不同。

我对服务发现的理解(到目前为止)是它允许节点动态搜索、查找和连接到远程服务。因此,如果一个应用程序使用一个AuthService进行身份验证、授权,它会使用服务发现来找到一个AuthService节点,比如说,http://auth103.example.org:9103并使用它。

动态配置系统的理解是,它们为节点提供了一个集中的基础设施,可以动态地从配置服务器接收更新以及向配置服务器发布更新。因此,如果应用程序实例决定需要更新其所有其他实例的配置,它将联系配置服务并更新,例如,numPurgerThreads配置。然后,配置服务将更新所有其他应用程序实例,以便它们正确更新各自的配置。

但这些不都是同一个问题吗?

在这两种情况下,您:

  1. 连接到某种查找服务
  2. 查询数据;或者
  3. 向其发布数据,然后将其波及到其他节点

服务发现动态配置的吧?!?!

我真正想要的是:我不能只用这些工具之一实现一个配置服务,巧合的是,它也解决了服务发现问题?或者是否有理由让我需要一个用于配置/KV 管理的 Consul 集群,以及另一个用于服务发现的 Consul 集群?

0 投票
0 回答
128 浏览

data-structures - 协调多个数据集

我正在尝试协调多个数据集以识别与共识的差异。可能有 100 组相同的数据,每组可能有 30,000 条记录。每个集合具有相同的列,但可能不具有相同的行,即 Person1 的记录可能只存在于一个集合中,也可能存在于所有集合中。我只想识别不同的记录并报告差异。可能更容易举个例子,例如

设置1:

  • 人 性别 DOB 工资等
  • 人 1 M 12/12/2000 100000 等
  • Person2 F 11/11/1999 200000 等

    设置2:

  • 人 性别 DOB 工资等
  • Person2 F 11/11/1999 250000 等
  • 人 3 M 10/10/1998 150000 等

    第 3 组:

  • 人 性别 DOB 工资等
  • 人 1 M 12/12/2000 100000 等
  • Person2 F 11/11/1999 250000 等
  • 人 3 M 10/10/1998 150000 等

    我想报告 Set1 对 Person2 的薪水与共识不同(Set2 和 Set3 有 250000 但 Set1 有 200000)。不会为 Person1 或 Person 3 报告任何内容,因为所有集合都具有相同的信息。

    做到这一点的最佳技术是什么?带有 SQL 语句的关系数据库?某种矢量数据库?Hadoop?统计软件?

    提前致谢,

    罗宾

  • 0 投票
    2 回答
    433 浏览

    computer-science - 使用 Paxos 跨节点同步大文件

    我正在尝试使用 Paxos 在大小约为 50MB 的文件上保持节点之间的共识,并在各个节点上不断进行修改。我遇到了实用性问题。要求:

    1. 跨数百个节点同步一个 50MB 以上的文件
    2. 对此文件进行更改,可以从任何节点进行,并且不太可能直接相互竞争,最多在几秒钟内通过网络传播
    3. 加入网络的新节点可以在几分钟(<1 小时)内按照 Paxos 消息构建整个文件

    我面临的问题是似乎没有办法同时实现目标 2 和 3。

    以下是我目前考虑过的选项:

    • 每轮同步整个文件——完全不切实际,Paxos 轮次需要几分钟
    • 仅同步对文件的更改——对于目标 1 和 2 来说是合理的,但会破坏目标 3,因为新节点只能在每个状态单元更改后才能同步整个文件
    • 每轮同步更改和文件的随机部分——我不确定 Paxos 是否允许这样做。节点将能够根据自己的更改验证更改(允许新更改),并且能够根据其版本的所述部分验证文件的随机部分,但这实用吗?

    我认为第三种选择是最好的,但我不确定 Paxos 是否允许这样做。想法是将每轮交换的数据限制为 1500 字节,并主要用对文件的更改来填充这 1500 字节。大多数轮次,文件将保持不变,而发生变化的轮次很可能少于 100 字节的更改状态,因此其他 1400 字节可以用文件的某些部分填充,这将允许构建新节点随着时间的推移整理整个文件。这实用吗?这个问题已经解决了吗?

    0 投票
    2 回答
    610 浏览

    consensus - RAFT 中是否存在竞态条件?

    当领导者获得日志条目时,它会将其复制到集群中的其他服务器。然后它提交条目并告诉其他服务器也提交。这里似乎有两种情况:
    1)领导者提交条目,然后告诉其他服务器也提交。
    2)领导者告诉每个人都承诺,然后它也这样做。

    在#1中,如果领导者在告诉其他人提交之前崩溃了,那么成为新领导者的人是否会使用该条目,即使它没有提交?如果不是,那么我们有一些与最新条目不同步的日志。(老领导会应用它,而另一个不会。)如果是这样,那么它怎么知道可以提交它?

    在#2中,如果leader在提交之前就崩溃了,那么所有其他节点在提交之后都崩溃了,然后在选举中,旧的leader再次成为新的leader,然后其他服务器已经提交了新leader没有提交的条目没有。在这种情况下会发生什么?

    0 投票
    1 回答
    1591 浏览

    java - 使用 FIFO 队列和 peek() 方法实现共识协议

    我需要实现一个使用带有 peek() 方法的队列的共识协议,以表明可以为任意数量的线程达成共识,即带有 peek() 方法的队列具有无限的共识数

    这是我的代码

    据我了解,这应该可行,因为如果两个线程返回不同的值, peek() 将必须返回不同的线程 id 并确保有效性,因为每个线程在推送其线程 id 之前将其自己的值写入建议中。

    有没有人能够弄清楚我哪里出错并指导我纠正我的代码

    0 投票
    4 回答
    1963 浏览

    distributed-computing - 分布式数据库事务上下文中的Paxos算法

    我对 paxos 有一些困惑,特别是在数据库事务的上下文中:

    在“paxos made simple”一文中,它说在第二阶段,提议者需要选择其中一个接受者之前接受过的具有最高序列号的值之一(如果不存在这样的值,则提议者可以自由选择建议选择原始值)。

    问题:

    1. 一方面,我理解这样做是为了保持共识。但另一方面,我对实际价值感到困惑——“必须向接受者发送以前接受过的价值”有什么意义?

    2. 在数据库事务的上下文中,如果它需要提交一个新值怎么办?是否需要启动一个新的 Paxos 实例?

    3. 如果上述问题的答案是“是”,那么接受者如何重置状态?(据我了解,如果它不重置状态,提议者将被迫发送之前已接受的旧值之一,而不是自由提交新值。)

    0 投票
    2 回答
    315 浏览

    algorithm - Paxos 阶段 2a 消息丢失

    下图是基本 Paxos 的消息流,在阶段 2a,Leader 为其提案 1 选择值 Vn,并向每个接受者发送 Accept!(1,Vn)。我的问题是:如果这三个消息中的两个丢失了怎么办?我的意思是只有接受者 1(不是多数)接收接受!(1,Vn)。Acceptor 1 会接受这个请求吗?然后广播给每个学习者?选择这个值? 在此处输入图像描述

    0 投票
    2 回答
    168 浏览

    distributed-computing - Paxos 和发现

    假设我将一些机器放在一个弹性集群中,并希望在它们中运行一些共识算法(比如 Paxos)。假设他们知道网络的初始规模,比如 8 台机器。

    因此,他们将运行共识算法,法定人数为 5。

    现在,考虑这些情况:

    1. 我看到 CPU 太低了,我将集群大小减半,减少到 4 台机器。
    2. 有一个分区拆分,每个拆分得到4台机器。

    如果我采用当前的集群大小来获得仲裁,我会受到分区拆分的影响。因为对于底层集群,情况(1)和(2)看起来完全一样。但是,如果我使用固定数量,我将无法缩小集群(如果我扩大规模,我会因分区而出现不一致)。

    我有第三种选择,即在扩展时通知所有机器集群的大小,但是有可能在扩展之前发生分区,例如,该分区没有收到新的大小并且有足够的仲裁使用旧尺寸的共识。

    Paxos(以及任何其他安全的共识算法)在弹性环境中无法使用吗?