The design of distributed system must meet real-time, fault-tolerance and security requriements. This article contains notes of 7 fundamental topics in building dependable distributed computing systems.1. Clock SynchronizationNotes for Cristian, F. (1989),"Probabilistic clock synchronization", Distributed Computing (Springer) 3 (3): 146–158$H$: hardware clock, $\rho$: maximum clock drift rate$P$: slave's clock, send message ("time=?") to $Q$$Q$: master's clock, send message ("time=",$T$) back to $P$$T$: time on $Q$'s logical clock$D$:halfround trip delay measured on P's clock ($2d$ is the real ...继续阅读 (23)

Summary for F. Cristian,"Understanding Fault-Tolerant Distributed Systems", CACM, vol. 34, no. 2, February 1991, pp. 56-78.1. Basic Architectural Concepts1.1 Services, Servers and the "Depends" RelationA computingservicespecifies a collection of operations whose execution can be triggered by inputs from service users (client) or the passage of time.The operation defined by a service specification can be performed only by aserverfor that service. A server implements a service without exposing to users the internal service state representation and operation implementation details.Servers impleme ...继续阅读 (21)

Something You Must Know Before Learning MonadThere is a saying goes that "Monad has a curse that when someone learns what monads are and how to use them, they lose the ability to explain it to other people."I would like to say it is true, at least for most of the normal people. The reason is that you probably need sufficient background knowledge in order to fully (or better) understand Monad.So how much on earth you should know before learning Monads? Why not take a look at my story first.My Story of learning MonadThe first time I heard Monad is around November 2013 in one of my Computer Scien ...继续阅读 (16)

Terms like "P, NP" should not be unfamiliar to computer science or software engineering major student, and in fact you might have already heard it thousands of times. However, when asked about what is the real definition of these terms, when and where to use them exactly, many people may shake their head.1. Decision problemFirst of all, "P, NP, co-NP, PSPACE" can be only used to describedecision problems. A decision problem is a question with a yes-or-no answer given some input parameters. For instance, the problem "given two numbersxandy, doesxevenly dividey?" is a decision problem.On the oth ...继续阅读 (18)

1. Flow NetworkGraphs are often used to model transportation networks such as traffic control or airline scheduling, and this particular kind of graph are always calledFlow Networks. Thus, the formal definition of flow network we are discussing here is adirected graph$G=(V,E)$ with following features.Each edge has a capacity of flow which is labeled as a nonnegativeinteger$c_e, e\in{E}$ and $c_e\geq{0}$A single source node $s\in{V}$A single sink node $t\in{V}$more2. Max-flow Min-cut ProblemBefore getting into this problem, we first need to understand what is flow and what is cut.2.1 Flow and ...继续阅读 (21)

1. Greedy AlgorithmBefore talking about greedy algorithm, I would like to share a learning habit of mine with you. I think most (almost all) of the technologies is computer science or software engineering can be described as "Problem and Solution". Therefore my habit is that we should know exactly what kind of problem we want to solve in the first place, then we could start to think how to solve it, and finally how to solve it efficiently.1.1 ProblemThe kind of problem we are facing is called"Optimization Problem", and here is an example.Suppose there are $n$ cities in Texas, each city has sev ...继续阅读 (21)

1. Graph Basic DefinitionA graph is a simple way of encoding pairwise relationships among a set of objects: it consists of a collection $V$ of nodes and a collection $E$ of edges, each of which "joins" two of the nodes. An edge $e \in{E}$ is represented of $V: e={u,v}$ for some $u,v\in{V}$ and $u,v$ are called the ends of edge $e$.Graphs can be divided into directed and undirected.more2. RepresentationThere are two kinds of ways to represent (use a data structure to encode) a graph (undirected and directed).2.1 Adjacency ListIn undirected graph. An adjacency list is a linked list with $n$ node ...继续阅读 (22)

1. Stable Marriage Problem1.1 Problem DefinitionThere are $n$ men and $n$ women. Each man has a preference list of the women he wants to marry, and each women also has a preference list of her ideal men. The problem is that how should we match these people such that there is no instability in the result.Here, instability means that suppose there are two matches in the result: $(m,w)$ & $(m',w')$, however, if $m$ prefers $w'$ over $w$ andsimultaneously$w'$ also prefers $m$ to $m'$, then this is called a instable match. (i.e. A man and a woman who are not matched together prefer each other to th ...继续阅读 (25)

In theprevious articlewe discussed how to use DNA sequences to reconstruct phylogeny tree. However, due to the length of DNA sequences methods are limited to only a few genes. Thus, gene order phylogeny is useful if you want to analysis the whole genome, and the reason it is considered to be useful because the rearrangement, indel, duplication events are rare in evolution history and may contains valuable information.1. BPAnalysisBreak Point Analysis (BPAnalysis) is one of the earliest algorithm for reconstructing phylogeny tree under Nadeau-Taylor model (GNT) [1] using breakpoint distance, wh ...继续阅读 (24)

As a biologist, suppose you would like to construct a phylogeny tree on several species, what kind of "raw data" you may have? Usually, you might have DNA sequences or morphology data. As a computer scientist, these are the input to our phylogeny reconstruction algorithms, which can be represented by a matrix. For DNA sequences each row represents a species and each column stands for a particular position on the sequence, and each entry is a nucleotide. For morphology data, rows have the same meaning, columns stands for different characters and each entry stands for the state of the character ...继续阅读 (30)

Feature Model (FM):A feature model (FM) defines the products of a product line.FM defines variations that programs can have in an SPL.FM is a blueprint to allow user specify products declaratively.Feature Diagrams (FD):A FD is a tree.Leaves are primitive features, while internal nodes are compound features.Parent and child are containment relation (has …).Order doesn’t mattermoreFDs are GrammarsCar := [Cr] Eng+ Tr CBodyTr := Auto | ManualEng := Gas | EleApplication defined by FD = Sentence defined by Grammar Car.Grammars are compact representations of propositional formulas.E := R S ; ...继续阅读 (22)

1. Software Product LineBefore discussing FOSD (Feature Oriented Software Development), we have to know the concept of SPL (Software Product Line) due to it is the origins of FOSD.A SPL defines a set of distinct but related programs. These programs always have a lot of commonality.Domain specific.Do not build softwares from scratch.A design for a program family, not a single program.Examples: Purchasing Macbook in Apple store, choose type and all kinds of features you want then click check-out.more1.1 FeaturesRefinement:process of adding implementation detail without changing semantics. (Imple ...继续阅读 (22)

1. IntroductionA broad view of MDE (Model Driven Engineering) is transforming models of software into code.What are models? In software engineering, generally, graphs, all kinds of graphs. E.g. finite state machine (FSM), message sequence charts, logic circuit diagram, data flow model, petri net, network architecture, etc.MDE is a fancy database application.moreRecall MDE is about drawing all kinds of graphs then transfer them to code. In fact, any model could be mapped to a database, i.e. tables, constraints, thus, any model is intrinsically a database which it can be transfered to.Take class ...继续阅读 (24)

Tree of lifeA phylogeny tree is also called evolutionary tree. It is used to depict the evolutionary relationships among various biological species by similarities and differences in their physical or genetic characteristics. It can also be used to describe linguistic evolution history.This (from Wikipedia) is a phylogeny tree showing how bacteria, archaea, eukaryota evolve. It's important to point out that we don't know whether the tree is correct (the true tee) or not, because we could only infer the history of this period of time by some archaeology evidence. In computational biology, howev ...继续阅读 (25)

1. IntroductionIn thelast articlewe illustrated the first step of compiling: Lexical Analysis in detail. Let's do some review and peek a bit to parsing to prepare moving onto the second part.Lexer: Input (String of code) -> Output (String of tokens)Parser: Input (String of tokens) -> Output (Parse tree)As we mentioned before the output of lexical analysis is the input of parsing. Besides, not all strings of tokens are programs so verifying tokens is necessary in parsing. Another important point is that parser not only check if certain token is valid to the language but also generate a parse tr ...继续阅读 (25)