👑 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 anti-submarine 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)
Low-cost all-digital 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)
"Poor-boy" Microwave
We would envision the use of almost mass-produced 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)
Non-Sync. 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.
LEO-Satellite, 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 post-error-removal 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 high-data "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 common-user 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 link-to-link interface standard... Time division multiplexing appears so natural to data transmission that we might wish to consider an alternative approach--a 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 store-and-forward 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.
- Hot-potato 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
... time-sharing among many users on a split-milisecond basis.
Devise an electronic input-output surface on which both operators and computers can display and communicate...
Insights from Licklider (3)
Open questions
... a programming system that will facilitate real-time contingent selection and shaping of information-processing 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, Error-correction and retransmission
Computer/user identification
Wesley Clark from Washington University
Message routing computer >> Interface Message Processor (IMP)
IMP-based architecture
Message format
Protocols
Dynamic routing
Queuing
Error control
Store-and-forward (1961-1968)
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)
PDP-10 - Tenex (Utah U)
SDS-940 - 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 DDP-516
BBN → The four nodes
Functionalities (client-server)
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 full-fledged 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
1943-1998 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 network-layer and transport-layer 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 lower-level details of how each constituent network is constructed.
- Design For Routing: Unlike some network-layer 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 lower-layer 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 world-wide 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 Berners-Lee 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 (1989-RFC1347/2004-China): 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 (MS-1970, PhD-1972) |
|
Stanford (BS-1965) |
Hobbies: |
🥪 delicious food, 🍷 wine |
Robert Bob Kahn
Name: |
Robert Kahn |
Photo: |
|
Date of Birth: |
Dec 23, 1938 |
Education: |
Princeton (MS-1962, PhD-1964*) |
|
NYU (BS-1960) |
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...
2 |
7 |
6 |
9 |
5 |
1 |
4 |
3 |
8 |
The magic square
__ |
X |
O |
__ |
X |
__ |
__ |
O |
__ |
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. |
Pre-stage
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.
Pre-stage
Kurt Gödel's thinking (1956)
Gödel asked whether theorem-proving (now known to be co-NP-complete) 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 (1978-1979).
NP-completeness theorem also called Cook-Levin theorem.
Richard Karp
TSP
Branch and bound method
49 by RAND → 65 by Karp-Held.
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 Turing-Acceptable.
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 polynomial-time Karp reducible to a language L' ⊆ {0,1}* if there exists a polynomial-time 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.
n2, n7, ... 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 |
n5 |
0.1s |
24.3s |
5.2m |
2n |
0.001s |
17.9m |
35.7y |
NP hard and NP complete
NP-Complete
NP-Complete 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.
2n, 7n, ..., computers take very long time to solve.
NP-hard
At least as hard as NP-complete, NP-hard 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 NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.
- Since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.
- A problem is NP-complete if it is both in NP and NP-hard.
- Although a solution to an NP-complete 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)
- 0-1 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
- 3-dimensional 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.
0-1 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 NP-hard
Idea: Reduction from the problem of vertex cover. let G=(V,E) be an undirected graph.
min Σv∈Vyv |
yv+yu≥1, ∀uv∈E |
yv≥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, yv 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 sub-collection of S whose union equals the universe.
Hitting set formulation
* Two problems are equal.
TSP
Finding the optimal route
Held-Karp alg. (Branch and bound)
Traverse different branches of the problem tree
Use lower bound to find optimal solution
Recursively divide the problem into sub-problems, 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 Σni=1vixi |
s.t. Σni=1wixi≤W and xi∈ {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 polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete 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: |
BS-1961@University of Michigan, PhD-1966@Harvard) |
Work Exp.: |
UCB → U Toronto |
Contributions: |
Definition of P, NP and P?=NP |
Leslie Lamport
Date of Birth: |
Feb 7, 1941 |
Education: |
MIT (BS-1960) Brandeis University (MS-1963, PhD-1972) |
Work experience: |
Massachusetts Computer Associates (COMPASS, 1970-1977) SRI International (1977-1985) DEC/Compaq (1985-2001) 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 fault-tolerant computer for aircraft control
Using multiple general-purpose 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 two-round 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.
Fault-tolerant 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 non-faulty)
Quorum
Strong majority
A set of acceptors consisting of more than half of all acceptors.
Any two quorums have a nonempty intersection.
Helps avoid “split-brain” problem.
- Acceptors decisions are not in agreement
- Common node acts as “tie-breaker.”
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 highest-numbered 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 highest-numbered 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 highest-numbered 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
Multi-Paxos
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 non-participation.
Adds an extra “verify” phase to the algorithm.
Paxos=Democracy?