专栏首页TechFlow每日一题 | 解一个复杂的方程

每日一题 | 解一个复杂的方程

昨日题解

每日一题 | 拜占庭将军问题

拜占庭将军问题是由著名的计算机大神图灵奖获得者兰伯特提出来的非常有名的问题,我们把这个问题外面包着的故事背景去除,实际上的内涵其实围绕的是分布式系统当中的一致性问题。在分布式系统当中,当多个节点当中存在部分节点被黑客攻击而成为恶意节点的时候,如何保证集群的一致性和正确性?

关于这个问题的解法很多,从提出至今好几十年当中陆续提出了很多种解法。包括最近很流行的区块链,其实本质上也是解决的分布式系统一致性的问题。

我们选择其中最简单的一种,也是兰伯特大神自己提出来的解决方法,称为口头协议。口头协议描述的是将军和副官模型,我们把第一个传达出自己意见的节点设为将军节点,其他节点是它的副官。这里只是为了说明需要,其实哪一个节点作为将军节点都没有关系。

为了方便阐述,我们把1号节点设为将军节点,2至6号节点设为副官节点。我们希望能够达成这样的效果,如果将军节点是忠诚的,那么所有忠诚的节点都执行将军的命令。如果将军节点是叛徒,那么是否执行将军的命令不再重要,只需要忠诚的节点保持一致即可。

我们假设将军节点是忠诚的情况,对于将军是叛徒的情况也类似,作为忠诚的节点,它向其他所有节点传递的消息是一致的,不会传递虚假的消息。但问题是其他节点并不知道它是不是忠诚的,这时候我们采取什么样的策略呢?其实也很简单,对于忠诚的节点,我们采取的策略是让它询问其他节点接收到的将军命令。

比如说假如2号节点是忠诚的,它会向3至7号节点发起询问,请问你们各自收到的将军的命令是什么?3至7号节点当中最多只有两个叛徒,也就是说正确的结果是占多数的。那么2号节点只需要根据这份信息作出决策即可。

对于其他忠诚的节点也是一样的操作,我们递归询问其他节点接收到将军的命令是什么,从而让叛徒变成少数,这样每个忠诚的节点之间可以保持一致,不会受到叛徒节点的影响。

但很可惜的是这只是一种理想的情况,因为在实际的分布式场景当中,信息的传递是存在延时的。有可能2号节点向3号节点发起询问的时候,它还没有收到将军的消息。所以实际当中这种方法是不可用的,但这并不影响我们理解和学习它的思路。通过这个经典的问题呢,我们也可以对分布式系统有一个浅显的认识。

实际上分兵多路作战在古时候由于通讯不便一直是一个很大的问题,比如著名的明末萨尔浒之战。明朝发动十几万大军合围萨尔浒,想要把满清来个犁庭扫穴。结果没想到多路大军进攻的时机没能保持同步,援军补给也没能跟上。被努尔哈赤各个击破,最终全军覆没,如若不然,大明也不会那么快灭亡,中国的历史必然将要改写。

今日问题

求解出整数x,使得下列方程成立,保证x只有唯一解。

(\sqrt{x-3} - \sqrt{\frac{3x+2}{2}}^3)^7=(x - \sqrt{\frac{x^2 - 1984}{5}})^3

本文分享自微信公众号 - TechFlow(techflow2019),作者:梁唐

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划入门——动态规划与数据结构的结合,在树上做DP

    之前的几篇文章当中一直在聊背包问题,不知道大家有没有觉得有些腻味了。虽然经典的文章当中背包一共有九讲,但除了竞赛选手,我们能理解到单调优化就已经非常出色了。像是...

    TechFlow-承志
  • 分布式初探——分布式事务与两阶段提交协议

    今天的文章咱们聊的是分布式原理当中的原子性,也称为分布式事务。不知道会不会有人觉得奇怪,分布式系统CAP原则当中并没有原子性,这个原子性是从哪里冒出来的?

    TechFlow-承志
  • 一点微小的改动,让你从B树理解到B+树

    首先和大家道个歉,昨天晚上由于我的失误,发文忘了改标题,引发了一些疑惑。昨天文章的标题应该是“快速求解方程的根——二分法与牛顿迭代法”,我在收录的专题目录当中已...

    TechFlow-承志
  • 我画了 20 张图,给女朋友讲清楚红黑树

    红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分...

    范蠡
  • redis系列:集群

    Redis 集群是Redis 的一个分布式实现,它是一个网状结构,每个节点都通过 TCP 连接跟其他每个节点连接。现在来看看Redis集群实现了哪些目标?

    云枭
  • 我画了近百张图来理解红黑树

    之前在公司组内分享了红黑树的工作原理,今天把它整理下发出来,希望能对大家有所帮助,对自己也算是一个知识点的总结。

    公众号 IT老哥
  • 简述 zookeeper 基于 Zab 协议实现选主及事务提交

    Zab 协议:zookeeper 基于 Paxos 协议的改进协议 zookeeper atomic broadcast 原子广播协议。

    WindWant
  • 「容器架构」 K8s 集群如何规划工作节点的大小?

    欢迎来到小巧的Kubernetes学习——一个定期的专栏,讨论我们在网上看到的最有趣的问题,以及Kubernetes专家在我们的研讨会上回答的问题。

    首席架构师智库
  • 最强大的GNN出现了!

    论文:https://arxiv.org/pdf/2009.00142.pdf 代码:https://github.com/snap-stanford/dist...

    Houye
  • Redis Cluster执行流程

    集群(cluster)是Redis提供的分布式数据库解决方案,集群通过分片(sharding)来进行数据共享,并提供数据复制(replication)和故障转移...

    张申傲

扫码关注云+社区

领取腾讯云代金券