Event Horizon

Und wenn du lange in einen Abgrund blickst, blickt der Abgrund auch in dich hinein.

Distributed Algorithm Basics (IX) - Paxos made simple

Notes on DA study

这是分布式算法笔记的第九章，讲述经典Paxos算法。 Paxos是解决一部环境下的数据强一致性的共识算法，在工业界有着广泛的应用。最早的实现就是Google的chubby系统。目前比较著名的Paxos实现包括zookeeper、DynamoDB以及阿里的X-Paxos。Paxos算法是由Lamport大神提出的，强烈建议大家去看《Paxos Made Simple》这篇文章，Lam...

Posted by swimiltylers on December 26, 2018

Distributed Algorithm Basics (VIII) - Fault-Tolerant Consensus

Notes on DA study

这是分布式算法笔记的第八章，讲述了节点故障情况下同步系统中的共识算法。 共识算法是分布式算法中非常重要的算法，涉及的方面非常广泛，之前的协调进攻算法可以当作在 link failure 情况下的共识算法问题。但是由于主要参考Attiya教材，因此本章讨论的仅限于节点故障情况下的。对于非同步系统中的共识问题，将在之后的笔记中单独阐述。 共识算法考虑两种情况下的节点故障 ...

Posted by swimiltylers on December 10, 2018

Distributed Algorithm Basics (III) - Distributed BFS

Notes on DA study

这是分布式算法笔记的第三章，讲述分布式BFS生成算法。 本章主要讲述三种BFS生成算法，通过衡量到达树根的距离，处理器确定自己在BFS tree中的层数以及对应的子节点和父节点。后两种算法涉及到不同类型的同步机制(Synchronizer)，这里就不细细展开了。 Explicit Distance Complexity: $O(VE)$ messages and $O(D)$ ...

Posted by swimiltylers on November 30, 2018

Distributed Algorithm Basics (VII) - Scenario: Coordinated Attack

Notes on DA study

这是分布式算法笔记的第七章，讲述了协调进攻算法。 Requirements Randomized Agreement: For any adversary $A$, the probability that some process decides 0 and some other process decides 1 given $A$ is at most $\epsil...

Posted by swimiltylers on November 24, 2018

Principle of Complier (I) - Lexical Analysis

Notes on Principle of Compiler

这是编译原理笔记的第一章，讲述了词法分析。 编译原理是计算机科学的一个基础课程，但是这门课比较难，因此上课的同时做一下笔记，方便之后查阅复习。本篇主要是对一些概念进行提纲，对一些算法进行简单的阐释。参考书是龙书。 词法分析的作用 编译器划分为两个阶段的原因 简化编译器的设计，任务分解 提高编译器的效率 增强编译器的可移植性 ...

Posted by swimiltylers on November 10, 2018

Distributed Algorithm Basics (VI) - Mutual Exclusion

Notes on DA study

这是分布式算法笔记的第六章，讲述了建立在共享内存模型下的互斥算法。 互斥算法的重要性不言而喻，因此本章的内容也比较繁杂，从问题阐述到算法过程，最后讨论互斥问题的复杂度下界。有不理解的地方可以参考Attiya的原文。 互斥问题的程序可以分为4个阶段 尝试阶段(Entry)：代码尝试进入critical section 保护阶段(Critica...

Posted by swimiltylers on November 2, 2018

Distributed Algorithm Basics (V) - Logical Clock

Notes on DA study

这是分布式算法笔记的第五章，讲述两种标量(scalar)时钟和一种向量(vector)时钟。 逻辑时钟主要解决的是在现实情况非同步的下如何确定时间戳(timestamp)，本章介绍的三种算法各有优劣。参考Yale讲义。 Causal ordering happens-before $e\Rightarrow_se’$: $e$ precedes $e’$ in $S$ ...

Posted by swimiltylers on October 18, 2018

Distributed Algorithm Basics (IV) - Scenario: Leader Election

Notes on DA study

这是分布式算法笔记的第四章，讲述选举问题。 选举问题(Leader election)就是在一群处理器中选举出中央的处理器，这种特殊的处理器在集群中只有一个，而且选举人其实可以不知道中央处理器是谁，只需要知道自己是否是中央处理器。选举问题可以变得非常复杂，但是在本章中，主要考虑在环状网络下通过MP系统进行选举。可以查阅Yale的详细表述。 本章主要举出了三种不同场景下的选举算法（P...

Posted by swimiltylers on October 4, 2018

Coq Basics (I) Inductives, Fixpoints, Tactics

Notes on Coq

这是Coq笔记的第一张，记录了SF教材的第一卷前三章 Inductive Inductive是Coq用来定义数据类型，实际上Coq的数据类型十分精简，但是我们可以通过这样的方法来自定义数据类型，Coq中最基本的数据类型就是Type，相当于Java的Object。语句的结构为Inductive [TYPE_NAME] : [INHERITED_TYPE] := {IND_DEF} ...

Posted by swimiltylers on September 23, 2018

Distributed Algorithm Basics (II) - Broadcast and Converge-cast

Notes on DA study

这是分布式算法笔记的第二章，讲述洪泛(Flooding)算法和汇合(Converge-cast)算法。 从本章开始，分布式算法的笔记也将围绕算法展开。本章主要讲述两个非常基础的生成树算法。本章介绍的算法非常基础，尤其是洪泛，但也存在在效率的问题。这一章的内容主要围绕Yale讲义，由于本章算法比较简单，因此只是简述算法流程，不进行详细的讨论。 Simple Flooding 得到...

Posted by swimiltylers on September 10, 2018

FEATURED TAGS
Distributed Algorithm Message-Passing model Shared Memory model Notes MST Lower Bound Consensus
ABOUT ME

Undergraduate in Nanjing University
近期正在学习分布式算法和Coq

FRIENDS