👑 Turing Award
The ACM Alan Mathison Turing Award  "Nobel Prize of Computing".
56 Turing Awards
Field 
Awards 
Percentage 
Programming lauguage 
16 
28.6% 
Computing theory 
12 
21.4% 
Network system 
8 
14.3% 
Database 
7 
12.5% 
AI 
6 
10.7% 
CHI 
4 
7% 
Security 
3 
5.4% 
It starts with cold war...
时间 
事件 
1956 
中苏交恶、太空竞赛与洲际弹道导弹 
1958 
柏林危机
1958年11月，赫鲁晓夫发给了西方一则最后通牒，要求美英法三国掌管的柏林区块转变为独立的、非军事化的自由城 
1962 
古巴导弹危机（扩展: 毛泽东与古巴导弹危机）
苏联寻求在古巴部署核导弹

Computers are rising..
IBM System/360 is taking over 70% computer market.
Remote control, data sharing, etc...
Military demands from USAF, (D)ARPA...
Military initiated? Corporation started? why bother.
US Gov. seeks solutions
US Airforce → RAND
ARPA → Universities
 ACTUV: A project to build an unmanned antisubmarine warfare vessel. (2010)
 Warrior Web: Soft exosuit to alleviate musculoskeletal stress on soldiers when carrying heavy loads. (2014)
 Combat Zones That See: "track everything that moves" in a city by linking up a massive network of surveillance cameras(2009)
 The Energetically Autonomous Tactical Robot (terminated in 2015).
 Switchblade UAV (cancelled in 2008).


Insights from RAND (1)
Define survivability and level of redundancy
Find performance bounds of the circuit switching system
Many thounghts on future systems


Insights from RAND (2)
We will be living in an era in which we cannot guarantee survivability of any single point.
... design systems in which system destruction requires the enemy to pay the price of destroying n of n stations. If n is made sufficiently large, it can be shown that highly survivable system structures can be built, even in the thermonuclear era 😱.
Insights from RAND (3)
Our future systems design problem is that of building very reliable systems out of the described set of unreliable elements (general system reliability issues and enemy attacks) at lowest cost.
Insights from RAND (4)
Lowcost alldigital communications links
Pulse regenerative repeater line
“... digital data rates on the order of 1.5 million bits per second can be transmitted over ordinary telephone line at repeater spacings on athe order of 6000 feet ...”
Insights from RAND (4)
“... There appears to be no fundamental reason why either lines of lower loss with corresponding further repeater spacing ... to extend link distances to in excess of 100 miles. Such distances would be desired for a possible national distributed network. ...”
1 mile ≈ 1.6 km ≈ 5280 feet
Insights from RAND (5)
"Poorboy" Microwave
We would envision the use of almost massproduced microwave crystal receiver/klystron oscillator units mounted on telegraph poles carrying commercial power...
While this technique has not been fully examined,... this may be the cheapest way of building large networks ...
Insights from RAND (6)
TV stations
With proper siting of receiving antennas, broadcast television stations might be used to form additional high data rate links in emergencies.
Insights from RAND (7)
NonSync. Satellites
When a satellite is overhead, the link is operative. When a satellite is not overhead, the link is out of service.
Think about the Starlink.
LEOSatellite, Starlink, OEC, ...
Insights from RAND (8)
Variable data rate
Variable data rate links
... it was seen that in order to make fullest use of a digital link the posterrorremoval data rate would have to vary as it is a function of noise level.
Hamming code  1950
Variable data rate users
... if one transmitted one line of a 60 wpm teletype message over a highdata "express route" at 1,500,000 bits per second.
Insights from RAND (9)
Common users
... we would like to consider the interconnection, one day, of many all digital links to provide a resource optimized for handling of data for many potential intermittent users  a new commonuser system.
Insights from RAND (10)
Standard message block
Present common carrier communications networks, used for digital transmission, use links and concepts originally designed for another purpose  voice. These systems are built around a frequency division multiplexing linktolink interface standard... Time division multiplexing appears so natural to data transmission that we might wish to consider an alternative approacha standardized message block as a network interface standard.
Insights from RAND (11)
Standard message block
Insights from RAND (12)
Switching
... The high data rate of the future carry us into a hybrid zone between storeandforward and circuit switching.
Insights from RAND (13)
The postman
... The postman records bulletins describing the traffic loading status for each of the outgoing links... determine the best direction to send out any letters.
 Hotpotato routing
 Determine of the best path
 The handover number table


Insights from RAND (14)
Perfect learning
Digital simulation of perfect learning
Forgetting learning
Adaptation to environment
Lowest cost path
Insights from RAND (15)
Where we stand today? (1962)
There is an increasingly repeated statement made that one day we will require more capacity for data transmission than needed for voice.
New digital computer techuniques using redundancy make cheap unreliable links potentially usable.
Insights from RAND (15)
Where we stand today? (1962)
Of course we could use our existing circuit switching techniques. But, a system with greater capacity than the long lines of telephone plants might best be designed for such data transmission and survivability at the outset.
Insights from RAND (15)
Where we stand today? (1962)
Is it time now to start thinking about a new user digital data communication plant designed specifically for the transmission of digital data among a large set of subscribers?
Is it time to consider the detailed format of a standard message block as a possible new data standard for the future?
DARPA's progress
Key man #1: Licklider from MIT
Insights from Licklider (1)
The need is strong
Insights from Licklider (2)
Open questions
... timesharing among many users on a splitmilisecond basis.
Devise an electronic inputoutput surface on which both operators and computers can display and communicate...
Insights from Licklider (3)
Open questions
... a programming system that will facilitate realtime contingent selection and shaping of informationprocessing procedures.
... systems for storage and retrieval of the vast quantities of information required to support, simultaneously at several user stations, creative thinking in various areas of investigation.
Human cooperation in the development of large program systems.
The story starts...
Licklider as the IPTO* leader
Licklider → Lawrence Roberts and Thomas Merrill (Colleagues from MIT)
Lawrence Roberts 
Thomas Merril 
* Information processing techniques office
DARPA's progress
Key man #2: Roberts from MIT
Roberts as IPTO leader
The rise of Packet Switching
"Packet" defined by D. W. Davies from NPL, UK
😼 Circuit switching → Packet switching
Progress and prototype
Message blocks, Errorcorrection and retransmission
Computer/user identification
Wesley Clark from Washington University
Message routing computer >> Interface Message Processor (IMP)
IMPbased architecture
Message format
Protocols
Dynamic routing
Queuing
Error control
Storeandforward (19611968)
System construction
Roberts Request for Proposals (RFP)
BBN wins the contract
BBN: Bolt, Baranek and Newman
BBN engineers: Frank Heart, Severo Ornstein, Will Crowther, Robert Kahn, etc.
Four nodes are selected:
Sigma7  SEX (UCLA)
IBM360/75  OS/MVT (UCSB)
PDP10  Tenex (Utah U)
SDS940  Genic (SRI)
Graduate students: S. Crocker, R. Stoughton, S. Carr, J. Rulifson
The first ARPANET
Machine type 
Different OS 
Different format 
Different terminal 
IMP  Honeywell DDP516
BBN → The four nodes
Functionalities (clientserver)
Telnet
FTP
Continous evolution
NCP: Network control program
NCP provided connections and flow control between processes running on different ARPANET host computers. Application services, such as email and file transfer, were built on top of NCP, using it to handle connections to other host computers.
Transits to TCP/IP in 1983.

* Steve Crocker was instrumental in creating the ARPA "Network Working Group", which later was the context in which the IETF was created. * The inventor of the Request for Comments series, authoring the first RFC (Host Software, S. Crocker, RFC 0001, April 1969.).
* Same high school with Vinton Cerf.

Organization
Network Control Center@BBN (Kahn)
Network/Project Management
Network Measurement Center@UCLA (Kleinrock)
Metrics and measurements
Network Information Center@SRI (Douglas Engelbart)
Information collection and storage
Boosting
From 4 to 23
New nodes include Harvard, Stanford, MIT, CMU, NASA
Scales from West to the entire country of US
1972, Hilton Hotel, Washington DC.
29 stations
40+ computers
Vinton Cerf obtained his PhD degree and started working with Kahn.
ARPANET goes international
UK, Norway joined
Satellite links from CA to Hawaii included
Even more heterogeneity
Key men #3: Kahn x Cerf on TCP/IP
TCP/IP
In 1973, development of a fullfledged system of internetworking protocols for the ARPAnet began.
In early versions of this technology, there was only one core protocol: TCP  Transmission Control Protocol Program.
The first version of this predecessor of modern TCP was written in 1973, then revised and formally documented in RFC 675, Specification of Internet Transmission Control Program, December 1974.
Specification of Internet Transmission Control Program
Important definitions:
Processes, PORTS, SOCKET, Letter sending/receiving, ...
Modern TCP/IP
In March 1977, version 2 of TCP was documented
Key man #4: Jon Postel
19431998 UCLA SMTP RFC 
IEN #2: We are screwing up in our design of internet protocols by violating the principle of layering. Specifically we are trying to use TCP to do two things: serve as a host level end to end protocol, and to serve as an internet packaging and routing protocol. These two things should be provided in a layered and modular way. I suggest that a new distinct internetwork protocol is needed, and that TCP be used strictly as a host level end to end protocol.

v3/v4 TCP 1978
The above observation led to the creation of "TCP/IP" architecture: TCP at the transport layer and IP at the network layer
The first formal standard for the versions of IP and TCP used in modern networks (version 4) were created in 1980. This is why the first “real” version of IP is version 4 and not version 1.
TCP/IP Race
 TCP/IP was at one time just “one of many” different sets of protocols that could be used to provide networklayer and transportlayer functionality.
 Integrated Addressing System: TCP/IP includes within it a system for identifying and addressing devices on both small and large networks. The addressing system is designed to allow devices to be addressed regardless of the lowerlevel details of how each constituent network is constructed.
 Design For Routing: Unlike some networklayer protocols, TCP/IP is specifically designed to facilitate the routing of information over a network of arbitrary complexity. In fact, TCP/IP is conceptually concerned more with the connection of networks, than with the connection of devices. TCP/IP routers enable data to be delivered between devices on different networks by moving it one step at a time from one network to the next. A number of support protocols are also included in TCP/IP to allow routers to exchange critical information and manage the efficient flow of information from one network to another.
*Even former “competitors” to TCP/IP such as NetWare now use TCP/IP to carry traffic.
TCP/IP Race
 Underlying Network Independence: TCP/IP operates primarily at layers three and above, and includes provisions to allow it to function on almost any lowerlayer technology, including LANs, wireless LANs and WANs of various sorts. This flexibility means that one can mix and match a variety of different underlying networks and connect them all using TCP/IP.
 Scalability: One of the most amazing characteristics of TCP/IP is how scalable its protocols have proven to be. Over the decades it has proven its mettle as the Internet has grown from a small network with just a few machines to a huge internetwork with millions of hosts. While some changes have been required periodically to support this growth, these changes have taken place as part of the TCP/IP development process, and the core of TCP/IP is basically the same as it was in 1980s.
 Open Standards and Development Process: The TCP/IP standards are not proprietary, but open standards freely available to the public. Furthermore, the process used to develop TCP/IP standards is also completely open. TCP/IP standards and protocols are developed and modified using the unique, democratic “RFC” process, with all interested parties invited to participate. This ensures that anyone with an interest in the TCP/IP protocols is given a chance to provide input into their development, and also ensures the worldwide acceptance of the protocol suite.
*Even former “competitors” to TCP/IP such as NetWare now use TCP/IP to carry traffic.
TCP/IP Race
ARPA/IPTO promotes
Embedded into BSD Unix
All ARPANET devices use TCP/IP in 1983
ARPANET adopted TCP/IP on January 1, 1983, and from there researchers began to assemble the “network of networks” that became the modern Internet. The online world then took on a more recognizable form in 1990, when Tim BernersLee invented the World Wide Web.
Recent news?
IPv6 (32→128)
China: 59039/32; USA: 57785/32
IPvX
IPv5 (1979, IEN119): the experimental Internet Stream Protocol
IPv7 (1993): TP/IX: The Next Internet
IPv8 (1994):Pip protocol
IPv9 (1989RFC1347/2004China): Address Extension/decimal vs hex
IPv9 4.1 Special (1994): A Historical Perspective On The Usage Of IP Version 9
Recent news?
IPv9 China
 2007年,上海通用化工技术研究所所长谢建平宣布IPv9正式走出实验室,开始进行商业化运作
 2010年,信息产业部十进制网络标准工作组称已经有上百家企业使用IPv9
 谢建平团队有放出一个实验软件,让IPv9对于现阶段IPv4和IPv6网路的兼容实现,但方式类似于DNS劫持,需要更改用户计算机的DNS设置到他专门的域名服务器才可以达成
 曾公开支持IPv9的院士有童志鹏、倪光南、周仲义、蔡吉人、沈昌祥、吾守尔、郑建华、魏正耀、丁文华、鄂维南、柴洪峰等
 逐步形成共识: IPV9并非互联网,只是一种域名设计。
Huawei New IP
旨在通过顶层设计，提供“万网互联、万物互联”的新连接能力、确定性传输及大吞吐量传输的新服务能力、安全可信及用户可定义的新内生能力，使能更多的新服务接入网络。
 变长网络地址
 多样化寻址
 面向服务的路由
 天空地海网络使用统一网络协议进行多样化寻址
 确定性IP技术、内生安全、用户可自定义、新传输层技术 ...
* 华为或许有能力实现，但首先要定义清楚，且推进到底
Vinton Cerf
Name: 
Vinton Cerf 
Photo: 

Date of Birth: 
Jun 23, 1943 
Education: 
UCLA (MS1970, PhD1972) 

Stanford (BS1965) 
Hobbies: 
🥪 delicious food, 🍷 wine 
Robert Bob Kahn
Name: 
Robert Kahn 
Photo: 

Date of Birth: 
Dec 23, 1938 
Education: 
Princeton (MS1962, PhD1964*) 

NYU (BS1960) 
Advised by Bede Liu.
It starts with a game...
123456789
 Two players
 Each picks a number in each round
 The one that picks the right numbers that sum up to 15 wins.
R1: 123456789
R2: 123456789
R3: 123456789
R4: 123456789
If we change the layout...
The magic square
Turns out to be another game
A reduced to B
There are many, many, many problems out there...
Can they be reduced to some common problems, that can be solved by known algorithms?
Cook's reduction
if X ≤^{C} Y 
then 
1. if you can solve Y, you can also solve X. 
2. if X not solvable, then Y also not solvable. 
Prestage
John Nash
In 1955, mathematician John Nash wrote a letter to the NSA, where he speculated that cracking a sufficiently complex code would require time exponential in the length of the key.
Prestage
Kurt Gödel's thinking (1956)
Gödel asked whether theoremproving (now known to be coNPcomplete) could be solved in quadratic or linear time,pointed out one of the most important consequences that if so, then the discovery of mathematical proofs could be automated.
Stephen Cook
The complexity of theorem proving procedures, by Stephen Cook, 1971.
Leonid Levin independently (1973).
Levin got his PhD at MIT in one year (19781979).
NPcompleteness theorem also called CookLevin theorem.
Richard Karp
TSP
Branch and bound method
49 by RAND → 65 by KarpHeld.
A lot more
Coloring, partition, set cover, knapsack, etc.
Combinational explosion.
Cook's reduction
if X ≤^{C} Y 
then 
1. if you can solve Y, you can also solve X. 
2. if X not solvable, then Y also not solvable. 
Karp's reduction
A language L ⊆ {0,1}^{*} is Karp reducible to a language L' ⊆ {0,1}^{*} if there exists a computable function f:{0,1}^{*} → {0,1}^{*} such that for every X ∈ {0,1}^{*} f(X)∈L' ⇔ X∈L 
if we can decide L', we can also decide L. 

Language Decidability*
A decision problem P is decidable if the language L of all yes instances to P is decidable.
*A language is called Decidable or Recursive if there is a Turing machine which accepts and halts on every input string w. Every decidable language is TuringAcceptable.
Example 1
Find out whether the following problem is decidable or not
Is a number m prime?
Solution
Prime numbers = {2, 3, 5, 7, 11, 13, …………..} 
Divide the number 'm' by all the numbers between 'm' and '√m' starting from '2'. 
If any of these numbers produce a remainder zero, then it goes to the “Rejected state”, otherwise it goes to the “Accepted state”. So, here the answer could be made by 'Yes' or 'No'. 
It is a decidable problem. 
Example 2
Given a regular language L and string w, how can we check if w ∈ L?
Solution
Take the DFA that accepts L and check if w is accepted 
Polynomial time Karp reduction
A language L ⊆ {0,1}^{*} is polynomialtime Karp reducible to a language L' ⊆ {0,1}^{*} if there exists a polynomialtime computable function f:{0,1}^{*} → {0,1}^{*} such that for every X ∈ {0,1}^{*} f(x)∈L' ⇔ X∈L 
L ≤_{p} L' 

Design algorithm
Suppose we want an efficient algorithm for decision problem X but we already have an efficient algorithm for decition problem Y.
 If we have X ≤_{p} Y. For an input w, we can decide whether w∈X
 compute f(w)
 check whether f(w)∈Y
Obtain lower bound and Equivalence
 If X ≤_{p} Y, and X cannot be decided in polynomial time, then Y cannot be decided in polynomial time either.
 If X ≤_{p} Y and Y ≤_{p} X, then X≡Y
P and NP
P: Problems that can be solved in polynomial time
Shortest path, spanning tree, etc.
n^{2}, n^{7}, ... algorithm steps are proportional to the input size, reasonable amount of time
NP: Problems that can be verified in polynomial time, but may take exponential number of steps to solve.
Algorithm complexity
f(n)\n 
10 
30 
50 
n 
0.00001s 
0.00003s 
0.00005s 
n^{5} 
0.1s 
24.3s 
5.2m 
2^{n} 
0.001s 
17.9m 
35.7y 
NP hard and NP complete
NPComplete
NPComplete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.
2^{n}, 7^{n}, ..., computers take very long time to solve.
NPhard
At least as hard as NPcomplete, NPhard problems do not have to be in NP, and they do not have to be decision problems.
NP hard and NP complete
 A problem X is NPhard, if there is an NPcomplete problem Y, such that Y is reducible to X in polynomial time.
 Since any NPcomplete problem can be reduced to any other NPcomplete problem in polynomial time, all NPcomplete problems can be reduced to any NPhard problem in polynomial time. Then, if there is a solution to one NPhard problem in polynomial time, there is a solution to all NP problems in polynomial time.
 A problem is NPcomplete if it is both in NP and NPhard.
 Although a solution to an NPcomplete problem can be verified "quickly", there is no known way to find a solution quickly.
NP hard and NP complete
P?=NP
Unsolved problem in computer science
Why bother
If the solution to a problem is easy to check for correctness, must the problem be easy to solve?
Karp's 21 Problems
 Satisfiability (SAT)
 01 integer programming
 Clique (independent set problem)
 Set packing
 Vertex cover
 Feedback node set
 Feedback arc set
 Directed Hamilton circuit/cycle
 Undirected Hamilton circuit/cycle
Karp's 21 Problems
 Satisfiability with at most 3 literals per clause
 Chromatic number
 Clique cover
 Exact cover
 Hitting set
 Steiner tree
 3dimensional matching
 Knapsack
 Job sequencing
 Partition
 Max cut
SAT
The "hardest" problem
Boolean satisfiability problem
It asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE.
Examples
a AND NOT b
a AND NOT a
The first NP complete problem
Vertex cover
a set of vertices that includes at least one endpoint of every edge of the graph.
01 Integer Programming
Applications
Scheduling
Agriculture production
Is linear programming NP hard?
In general, a continous domain means there is no brute force (and no clever heuristics to speed it up Raphael's comment.
Proof of NPhard
Idea: Reduction from the problem of vertex cover. let G=(V,E) be an undirected graph.
min Σ_{v∈V}y_{v} 
y_{v}+y_{u}≥1, ∀uv∈E 
y_{v}≥0, ∀v∈V 
0. Any feasible solution to the integer program is a subset of vertices
1. At least one end point of every edge is included in this subset
2. Additionally given some vertex cover C, y_{v} can be set to 1 for any v∈C and to 0 for any v∉ C thus giving us a feasible solution to the integer program.
* Integer Programming Reduction
Set cover
Set cover
Given a set of elements {1,2,...,n} (called the universe) and a collection S of m sets whose union equals the universe, the set cover problem is to identify the smallest subcollection of S whose union equals the universe.
Hitting set formulation
* Two problems are equal.
TSP
Finding the optimal route
HeldKarp alg. (Branch and bound)
Traverse different branches of the problem tree
Use lower bound to find optimal solution
Recursively divide the problem into subproblems, bounding the solution each step of the way
Branch&bound: Example
Visit 5 cities with smallest weights.
Branch&bound (1)
Branches
Branch & bound (2)
We start with node 0
City 
0 
1 
2 
3 
4 
Reduce 
0 
∞ 
12 
34 
17 
27 

1 
12 
∞ 
22 
44 
17 

2 
34 
22 
∞ 
45 
19 

3 
47 
44 
45 
∞ 
57 

4 
27 
17 
19 
57 
∞ 

Reduce 






Branch & bound: Example (2)
We start with node 0
City 
0 
1 
2 
3 
4 
Reduce 
0 
∞ 
0 
21 
9 
15 
12 
1 
0 
∞ 
9 
6 
5 
12 
2 
34 
22 
∞ 
45 
19 
19 
3 
15 
3 
0 
∞ 
0 
44 
4 
10 
0 
1 
14 
∞ 
17 
Reduce 
0 
0 
1 
26 
0 
131 
Branch & bound (3)
Updated weight matrix
City 
0 
1 
2 
3 
4 
Reduce 
∞ 
∞ 
∞ 
∞ 
∞ 
∞ 

1 
∞ 
∞ 
9 
6 
5 

2 
34 
∞ 
∞ 
45 
19 

3 
15 
∞ 
0 
∞ 
0 

4 
10 
∞ 
1 
14 
∞ 

Reduce 






Branch & bound (3)
The algorithm recursively goes..
Until every weight becomes infinity.
Try it yourself, and check the answers in next page
Branch & bound (4)
Result
Directed Hamilton Cycle
Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once.
Knapsack
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
maximize Σ^{n}_{i=1}v_{i}x_{i} 
s.t. Σ^{n}_{i=1}w_{i}x_{i}≤W and x_{i}∈ {0,1} 
Turing remarks
For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomialtime computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NPcompleteness. Karp introduced the now standard methodology for proving problems to be NPcomplete which has led to the identification of many theoretical and practical problems as being computationally difficult.
Stephen Cook
Name: 
Stephen Cook 
Photo: 

Date of Birth: 
December 14, 1939 
Education: 
BS1961@University of Michigan, PhD1966@Harvard) 
Work Exp.: 
UCB → U Toronto 
Contributions: 
Definition of P, NP and P?=NP 
Leslie Lamport
Date of Birth: 
Feb 7, 1941 
Education: 
MIT (BS1960) Brandeis University (MS1963, PhD1972) 
Work experience: 
Massachusetts Computer Associates (COMPASS, 19701977) SRI International (19771985) DEC/Compaq (19852001) Microsoft Research (2001) 
Contributions: 

LaTeX
LamportTeX
TeX () vs LaTeX
Tex: An environment and a program.
TeX is a typesetting system. It provides many commands which allow you to specify the format of your document with great detail (e.g. font styles, spacing, kerning, ligatures, etc.), and has specialized algorithms to compute the optimal flow of text in your document (e.g. where to cut lines, pages, etc.).
LaTeX
LaTeX is a set of macros built on top of TeX. The idea behind LaTeX is to shift the focus from the format to the content of your document.
XeLaTeX, LuaLaTeX, htLaTeX
LaTeX
Writing is the nature's way of letting you know how sloppy your thinking is.
Dick Guindon
To think, you have to write.
Leslie Lamport
If you are thinking without writing, you only think you are thinking.
Leslie Lamport
LaTeX
Interesting packages
Lamport's bakery algorithm
In computer science, it is common for multiple threads/processors/computers to simultaneously access the same resources. Data corruption can occur if two or more threads try to write into the same memory location.
Lamport's bakery algorithm is one of the many mutual exclusion algorithms designed to prevent concurrent threads entering critical sections of code concurrently to eliminate the risk of data corruption.
Lamport's bakery algorithm
Problem:
Multiple computers/processors/threads execute common and critical sections. The critical section is that part of code that requires exclusive access to resources and may only be executed by one thread at a time
Requirement:
At any time, at most one computer may be in its critical section.
Each computer must eventually be able to enter its critical section (unless it halts).
Any computer may halt in its noncritical section.
Lamport's bakery algorithm
Consumer 
P0 
P1 
P2 
P3 
P4 
Ticket 
0 
3 
1 
2 
0 

0 
2 
0 
1 
0 
Ticket 
0 
1 
0 
0 
0 
Ticket 
0 
0 
0 
0 
0 
More complex bakeries?
Byzantine generals
 If all generals agree to attack → win
 If some generals retreat → lose
It is about consensus
Byzantine fault tolerance
Byzantine fault:
Any fault presenting different symptoms to different observers.
A Byzantine failure:
The loss of a system service due to a Byzantine fault in systems that require consensus
Byzantine fault tolerance
Interactive consistency problem, Robert Shostak
Context: SIFT: design and analysis of a faulttolerant computer for aircraft control
Using multiple generalpurpose computers that would communicate through pairwise messaging in order to reach a consensus, even if some of the computers were faulty.
Byzantine fault tolerance
Problem settings:
 n components, out of which t dishonest
 p2p channel between all the components
Properties:
The system is said to Byzantine fault tolerant if a component A can broadcast a value x, and then:
 If A is honest, then all honest components agree on the value x.
 In any case, all honest components agree on the same value y.
Byzantine fault tolerance
Shostak
A minimum of 3n+1 are needed for consensus
A tworound 3n+1 messaging protocol for n=1
Pease
Generalized the algorithm for any n > 0, proving that 3n+1 is both necessary and sufficient
Lamport
Sufficiency of 3n using digital signatures
Byzantine fault tolerance
Practical BFT
Castro, Liskov, "Practical Byzantine Fault Tolerance and Proactive Recovery". ACM Transactions on Computer Systems, 1999.
Blockchain consensus
PBFT, Proof of Work, Proof of Stake, Raft, Ripple, Paxos, Zookeeper
Paxos
Distributed state machine
Replicated, redundant servers
Need to guarantee consistency among replicas
Operations to replicas must follow the same order
Distributed consensus
Intuitive solution: One syncs all
Not fault tolerant
Paxos (why paxos?)
Achieve consensus in distributed manner
Achieve consensus with fault tolerance
Assumptions
Fail stop
When a node fails, it stops entirely.
May resume normal operations when restarted
Messages
could be lost
could be duplicated
could be delayed
cannot be corrupted
Stable storage
Notations
Proposer

suggest values for Acceptors.

advocate for a client

Acceptor

consider the values proposed by proposers.

render an accept/reject decision.

Learner

learn the chosen value

Proposal
 An alternative proposed by a proposer.
 Consists of a unique number and a proposed value (13, V)
Chosen
 a value is chosen when consensus is reached on that value.
*In practice, each node will usually play all three roles.
Faulttolerant consensus
Requirements:Safety and liveness
Validity: Only proposed values can be chosen and learned.
Agreement: There can't be more than one decided value
Liveness (or termination): If value C has been proposed, then eventually learner L will learn some value (if sufficient processors remain nonfaulty)
Quorum
Strong majority
A set of acceptors consisting of more than half of all acceptors.
Any two quorums have a nonempty intersection.
Helps avoid “splitbrain” problem.
 Acceptors decisions are not in agreement
 Common node acts as “tiebreaker.”
In a system with 2n+1 acceptors, n acceptors can fail and we'll be OK.
Quorum
Quorums in a system with 7 acceptors
Consensus
 Values proposed by proposers are constrained so that once consensus has been reached, all future proposals will carry the chosen value
 For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either:
 (a) no acceptor in S has accepted any proposal numbered less than n, or
 (b) v is the value of the highestnumbered proposal among all proposals numbered less than n accepted by the acceptors in S.
Basic Paxos Alg
Proposer 
Acceptor 
Prepare: Select proposal number* N and send a prepare(N) request to a quorum of acceptors 


Promise: If N > number of any previous promises or acceptances,
 send a promise(N, U) response
(where U is the highestnumbered proposal accepted so far)

Accept: If proposer received promise responses from a quorum,
 send an accept(N, W) request to those acceptors
(where W is the value of highestnumbered proposal among promise responses, or any value if no promise contained a proposal)



Accepted:If N >= number of any previous promise,
* accept the proposal
 send an accepted notification to the learner

Example
Example
Example
Example
MultiPaxos
chosen value 
S 
P 
? 
O 

instance 
39 
40 
41 
42 

 A single instance of Paxos yields a single chosen value.
 To form a sequence of chosen values, simply apply Paxos iteratively.
 Include an instance number in messages.
 Facilitates replication of a state machine.
Extensions
Cheap Paxos
Reconfigurations (e.g., eject failed acceptors)
Fast Paxos
Reduce message traffic.
Byzantine Paxos
Arbitrary failures  lying, collusion, fabricated messages, selective nonparticipation.
Adds an extra “verify” phase to the algorithm.
Paxos=Democracy?