Recent Advances in Network Computing


Zhiwei Zhao
zzw@uestc.edu.cn


mobinets @ SCSE, UESTC

Two lines

Recent advances Turing award winners
1. NDN/SDN/NFV 1. Stories
2. Edge computing 2. Interesting works
3. Lectures

Coursework (60%+40%)

A one-column, two-page course work.

Sample pdf, Template tex file.

Attendance

The roll will be called when many are absent.
No final score if you are found absent for ≥3 times.

Submission

Email: fmi_course@mobinets.org
Deadline: May 26, 2022.

👑 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%

Stars in networks (1)


Ken Thompson & Dennis Ritchie (1983)

Richard M. Karp (1985)

Fernando J. Corbató (1990)

Butler W. Lampson (1992)

Stars in networks (2)


Vint Cerf & Robert Kahn (2004)

Charles P. Thacker (2009)

Leslie Lamport (2013)

Tim Berners-Lee (2016)

On our stage..


Vint Cerf & Robert Kahn (2004)

Richard M. Karp (1985)

Leslie Lamport (2013)

🤔
Explore their problems

📜
Seminal works

🎤
Stories and Interviews

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

Tech. state: Telecommunications

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).

Competition

RAND

On distributed communications networks, RAND Corporation, 1962

ARPA

On-line Man-Computer Communication, J Licklider and W Clark, 1962 Spring Joint Computer Conference.
Toward a cooperative network of time-shared computers, T. Marill and L. Roberts, 1966.

Insights from RAND (1)

On distributed communications networks

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

On-line Man-Computer Communication

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)

A cooperative network of time-sharing computers.

Lawrence Roberts

Thomas Merril

* Information processing techniques office

The Experimental Network

TX-2 (MIT)AN/FSQ-32 (SDC)PDP-10 (ARPA)
Low-efficiency: 1) Circuit switching 2) TDM/FDM

A three-node network: The first network ever -- The Experimental Network

DARPA's progress

Key man #2: Roberts from MIT

Toward a cooperative network of time-shared computers, T. Marill and L. Roberts, 1966.

Roberts as IPTO leader

The rise of Packet Switching

Information flow in large communication nets, Kleinrock from MIT.
"Packet" defined by D. W. Davies from NPL, UK

😼 Circuit switching → Packet switching

L. Roberts, Multiple computer networks and inter-computer communication, ACM SOSP 1967.
D. W. Davies, A digital communication network for computers giving rapid response on remote terminal, ACM SOSP 1967

Progress and prototype

Frank Westvelt from MSU

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

Group leader: S. Crocker*
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

NewIP:开拓未来数据网络的新连接和新能力

旨在通过顶层设计,提供“万网互联、万物互联”的新连接能力、确定性传输及大吞吐量传输的新服务能力、安全可信及用户可定义的新内生能力,使能更多的新服务接入网络。
  • 变长网络地址
  • 多样化寻址
  • 面向服务的路由
  • 天空地海网络使用统一网络协议进行多样化寻址
  • 确定性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.

Interview with Vinton Cerf

USC Interview with Vinton Cerf, Dec 2018.

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

2 7 6
9 5 1
4 3 8

Turns out to be another game

__ X O
__ X __
__ O __

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.

Letter from John Nash

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.

Kurt Gödel, von Neumann, and the P?=NP problem

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
    1. compute f(w)
    2. check whether f(w)∈Y

Obtain lower bound and Equivalence

  1. If X ≤p Y, and X cannot be decided in polynomial time, then Y cannot be decided in polynomial time either.
  2. 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.

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}

Richard Karp

Name: Richard Karp
Photo:
Date of Birth: January 3, 1935
Education: Harvard (BS-1955, MS-1956, PhD-1959)
Background: Mixture of control theory, statistics, complex analysis
Contributions: "三栖学者" computer science, combinatorial algorithms, and operations research

* Hartley Rogers, "Theory of Recursive Functions and Effective Computability" (1967).

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

Interview with Karp @UCB

Host: David A. Patterson

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,
Paxos algorithm,
Sequential consistency,
Lamport's bakery algorithm,
Byzantine fault tolerance,
Temporal logic (TLA+)[1][2][3],
Full collection

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.
People: Donald Knuth (高德纳), Leslie Lamport
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

coffee balance rainbow marginnotes algorithm2e
李阿玲@知乎

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.
Pease, Shostak, Lamport, Reaching Agreement in the Presence of Faults

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:
  1. If A is honest, then all honest components agree on the value x.
  2. 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
Alabanian army → Lamport, Shostak, Pease. The Byzantine Generals Problem

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
    1. suggest values for Acceptors.
    2. advocate for a client
    Acceptor
    1. consider the values proposed by proposers.
    2. render an accept/reject decision.
    Learner
    1. 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?

Interview with Lamport