拜占庭将军问题简述

发表于 2021-05-11 更新于 2024-08-12 分类于技术笔记
本文字数： 4k 阅读时长 ≈ 4 分钟

拜占庭将军问题简述

拜占庭的简述

本文将用于介绍著名的拜占庭将军问题。在介绍拜占庭将军问题之前，先简单说一下拜占庭。拜占庭帝国，在古代西欧也被称之为东罗马帝国。是一个位于欧亚交界处的封建君主制国家，其领土包括现在的欧洲南部，西亚和北非。公元四世纪左右，罗马帝国开始分列为罗马东部和罗马西部，这两个国家都被视为罗马正统，大概到公元十世纪，罗马西部陷落，随着神圣罗马帝国的建立，罗马东部失去了罗马这个单词的独占权，开始被称之为东罗马帝国。大概在16世纪之后，开始出现了拜占庭帝国的说法。值得一提的是，拜占庭帝国的首府君士坦丁堡被第四次十字军东征攻陷，从此一蹶不振。1453年5月29日，君士坦丁堡被强大的奥斯曼帝国攻陷，末代皇帝君士坦丁十一世战死。东罗马帝国就此终结。当然，此文不是介绍东罗马帝国历史的文章，在此仅简述拜占庭帝国的历史。

拜占庭将军问题是什么

拜占庭将军问题和拜占庭的历史其实并无关联，拜占庭将军问题也不是历史上真实存在的问题，他是著名计算机大神兰伯特于1982年提出的。拜占庭问题描述的是如下的场景

假设有一座城堡，拜占庭帝国想攻陷这座城堡。所以派出了很多支军队，因为通讯条件很落后，军队和军队之间必须经过信使来传递作战命令。城堡十分坚固，可以抵御一两只军队的进攻。只有所有军队同时进攻，才可以攻陷城堡。为了保证作战命令的统一，提出一个办法，投票。超过半数投票决定作战命令。比如：决定明天早上进攻，如果有半数的军队同意这个作战计划。则在明日早晨开始一起进攻。反之，如果一大半人都不同意明天早上进攻，则明早就不进攻。

现在存在的问题是：军队中有叛徒。叛徒会随意调整作战命令

我们现在用图一来表示这种困境，在图示中，我们用黄色的小人代表正常的部队，粉色的小人代表判叛徒。A表示进攻Attack，R代表拒绝Reject。因为正直的的部队会忠实的执行命令，所以我们把A和R标记在他们身上。

如图所示，身上标记A的三位将军表示他们决定“明早发动进攻”，身上标记R的三位将军决定明早不应该发动进攻，现在叛徒至关重要。叛徒的这一票将决定明早是否决定进攻。这时候叛徒给三位决定进攻的将军传递的消息是明早发动进攻，给三位不进攻的将军发送的消息是明早不发动进攻。所以三位决定进攻的将军知道了，有4票发动进攻的，那么大多数人决定进攻那我明早就发动攻势。三位不进攻的将军则知道，有四票不发动进攻的，那我明早不进攻。所以拜占庭难度就产生了，这些部队有的进攻有的撤退，战斗就失败了。

阅读全文 »

在M1上编译substrate

发表于 2021-03-11 更新于 2024-08-12 分类于技术笔记
本文字数： 3k 阅读时长 ≈ 3 分钟

之前已经在x86的mac电脑上编译过substrate，按照官方指南上的操作就可以正常编译。但是在新款m1电脑上并没有编译通过，现在重新尝试在m1上编译substrate。

主要的准备过程参考如下文章

https://zhuanlan.zhihu.com/p/337224781

不过参考文章写于2020年12月16日，到现在（2021年3月10日）有部分状况已经发生了变化。针对和文章中不一样的状况稍作说明。

RUST

rust环境现在可以直接支持m1。所以使用rustup脚本可以直接安装rust，不需要额外设置。安装完成之后使用

rustup show

查看toolchain。则会发现是以aarch64开头的，原来的x86下面的tool-chain是

stable-x86_64-apple-darwin (default)

注意差别。

阅读全文 »

sqlite自增小知识

发表于 2021-01-20 更新于 2024-08-12 分类于技术笔记
本文字数： 1.5k 阅读时长 ≈ 1 分钟

Sqlite自增字段

起因：在使用数据库存储从区块链网络上取来的block_header时，block_header本身并不带自身的高度信息。不过取来的数据是经过筛选的，按照数据库存储的顺序就可以代表blockheader的高度。所以在数据库中增加一个id primiry key autoincrement 的自增主键。每次从数据库查询时获取id值来代表区块的高度。但后来重构，id被TEXT类型的逐渐替代，所以这个功能无法正常实现。所以产生以下疑问

在已经有TEXT类型的主键后，sqlite可以拥有别的自增字段吗?

不可以！在sqlite的文档FAQ中第一个问题（文末给出参考链接）就是关于如何设置自增字段的。在sqlite中自增约束AUTOINCREMENT只可以跟在PRIMARY KEY后面。把AUTOINCREMENT放在主键以外的地方是不可以的。或者再明确一点，要想在sqlite中拥有一个自增字段必须这样写

1	id INTEGER PRIMARY KEY AUTOINCREMENT,

要求id的类型必须是INTEGER。每次插入数据库的时候，不要插入id的数据，数据库会自动为我们的主键id实现自增。之前提到的情况：id已经是TEXT PRIMARY KEY的状态下，无法再拥有另一个自增字段了。

题外：在sqlite以外的数据库中是可以的。以mysql为例，mysql的AUTOINCREMENT是可以加在主键之外的地方的。一个表中，只允许有一个自增字段，而且在mysql中需要给主键以外的字段实现自增，必须给该字段加上unique约束。

注意点:

在设定id INTEGER PRIMARY KEY，不加AUTOINCREMENT，只要不指定插入id的数据，id字段也可以实现自增。

在已经有TEXT类型的主键后，一定要有一个自增的字段来记录当前所在的行数怎么办？

阅读全文 »

多线程原语ConVar

发表于 2020-12-24 更新于 2024-08-12 分类于技术笔记
本文字数： 2.1k 阅读时长 ≈ 2 分钟

多线程原语CondVar

多线程下的原语，除了我们常用的锁，还有另外一类用于同步的原语叫做“屏障”，“条件变量”(在rust或者cpp中)。在其他语言中也有类似的概念，叫做栅栏，闭锁，屏障，信号量等。他们具有相同的意义。

在介绍条件变量之前，先介绍屏障（Barrier）。屏障相当于一堵带门的墙，使用wait方法，在某个点阻塞全部进入临界区的线程。条件变量（Condition Variable）和屏障的语义类似，但它不是阻塞全部线程，而是在满足某些特定条件之前阻塞某一个得到互斥锁的线程。

单纯讲条件变量的意义并不直观。换种描述

条件变量可以在我们达到某种条件之前阻塞线程，我们利用此特性可以对线程进行同步。或者说做到按照某种条件，在多个线程中达到按照特定顺序执行的目的。

为此我们设计如下下面流程。为此流程写一段代码，来体会条件变量的作用

我们启动三个线程，t1，t2，t3。分别执行任务T1，T2，T3。现在要求：T2必须等待T1和T3完成之后再执行

use parking_lot::{Mutex, Condvar};
use std::sync::Arc;
use std::thread;
use std::thread::sleep;
use std::time::Duration;


pub fn main() {
    let pair = Arc::new((Mutex::new(0),
                         Condvar::new()));
    let pair2 = pair.clone();
    let pair3 = pair.clone();


    let t1 = thread::Builder::new()
        .name("T1".to_string())
        .spawn(move ||
            {
                sleep(Duration::from_secs(4));
                println!("I'm working in T1, step 1");
                let &(ref lock, ref cvar) = &*pair2;
                let mut started = lock.lock();
                *started += 2;
                cvar.notify_one();
            }
        )
        .unwrap();

    let t2 = thread::Builder::new()
        .name("T2".to_string())
        .spawn(move ||
            {
                println!("I'm working in T2, start");
                let &(ref lock, ref cvar) = &*pair;
                let mut notify = lock.lock();

                while *notify < 5 {
                    cvar.wait(&mut notify);
                }
                println!("I'm working in T2, final");
            }
        )
        .unwrap();

    let t3 = thread::Builder::new()
        .name("T3".to_string())
        .spawn(move ||
            {
                sleep(Duration::from_secs(3));
                println!("I'm working in T3, step 2");
                let &(ref lock, ref cvar) = &*pair3;
                let mut started = lock.lock();
                *started += 3;
                cvar.notify_one();
            }
        )
        .unwrap();

    t1.join().unwrap();
    t2.join().unwrap();
    t3.join().unwrap();
}