Distributed Computing, COMP 4001 1
Distributed Computing
(The Basics)
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 2
A New Perspective
, , SCS (September 3, 2021)
Propagated
Distributed Computing, COMP 4001 3
Issues
• Fundamental questions:
– what can be computed?
– what can be computed fast?
• Model of computation:
– distributed
, , SCS (September 3, 2021)
( I do not mean clock)!
centralized
Distributed Computing, COMP 4001 4
Distributed: Basic Concept
• A distributed system is one in which components located at
networked computers communicate and coordinate their
actions only by passing messages.
• Computers that are connected by a network may be spatially
separated by any distance. They may be on separate
continents, in the same building or in the same room.
• This leads to the following characteristics of distributed
systems:
– concurrency of components,
– lack of a global clock,
– and independent failures of components.
, , SCS (September 3, 2021)
–
wag”
Distributed Computing, COMP 4001 5
Motivation
• Resource sharing is a main motivation for constructing
distributed systems.
• Resources
– either may be managed by servers and accessed by clients
– or may be encapsulated as objects and accessed by other
client objects.
, , SCS (September 3, 2021)
client/server system
0<-70 O_0 Distributed Computing, COMP 4001 6 Examples • Web search. • Multiplayer online games. • Financial trading systems. • Internet factorization of integers. • Privacy maintaining computation. , , SCS (September 3, 2021) RSA (n ) t homomorphic security pqcomputation Distributed Computing, COMP 4001 7 The Traditional Perspective , , SCS (September 3, 2021) 80 Solve the Leader Election problem " 6 Distributed Computing, COMP 4001 8 The Distributed Perspective , , SCS (September 3, 2021) 0 Distributed Computing, COMP 4001 9 Main Elements , , SCS (September 3, 2021) Distributed Computing, COMP 4001 10 Outline • Graphs • Distributed Systems • Distributed Algorithms • Optimization , , SCS (September 3, 2021) Distributed Computing, COMP 4001 11 Graphs , , SCS (September 3, 2021) Distributed Computing, COMP 4001 12 Graphs • Concept , , SCS (September 3, 2021) Distributed Computing, COMP 4001 13 Graphs: Nodes, Edges • Nodes and Edges , , SCS (September 3, 2021) V -- set of nodes E. . . . edges (V , E) , E c- Vxv Distributed Computing, COMP 4001 14 Graphs: Adjacent Nodes • Adjacent nodes (neighbours) , , SCS (September 3, 2021) Distributed Computing, COMP 4001 15 Graphs: Adjacent Edges • Adjacent edges , , SCS (September 3, 2021) Distributed Computing, COMP 4001 16 Graphs: Degree • node with 3 neighbours; adjacent to 3 nodes • incident to 3 edges • degree is 3 , , SCS (September 3, 2021) ) Distributed Computing, COMP 4001 17 Graphs: Subgraph • Subgraph , , SCS (September 3, 2021) 3- @ is• • ✗ % isolated subgraph Distributed Computing, COMP 4001 18 Graphs: Induced Subgraph • Subgraph induced by the red nodes • All red nodes; all edges that join a pair of red nodes , , SCS (September 3, 2021) tgf - • green Distributed Computing, COMP 4001 19 Graphs: Edge-Induced Subgraph • Subgraph induced by the red edges • All red edges; all nodes that are incident to red edges , , SCS (September 3, 2021) • ☒ Distributed Computing, COMP 4001 20 Graphs: Node Induced Subgraph • Not a node-induced subgraph; not an edge-induced subgraph; not a spanning subgraph. , , SCS (September 3, 2021) 0 . . : : C < - - Distributed Computing, COMP 4001 21 Graphs: Distance, Diameter and Shortest Path • Shortest path from u to v; length 6. • distance(u, v) = 6; diameter � 6. , , SCS (September 3, 2021) path darned 7- diaumaetermneeoyfhpath ) The function dluivl = length of shortest path from u to v is a " distance metric ! dlu.ie/--0dcuil--dluiul ( undirected )graphs dluif-fdluiwl-dlw.ir ) triangle inequality Proofed : chair ) flluiv ) = dcuiwltdcw , v ) Distributed Computing, COMP 4001 22 Graphs: Sphere of Radius r • Consider the “red” node, call it u. • Sphere Sr(u): set of vertices at distance exactly r from u. , , SCS (September 3, 2021) ¥ - ¥ , ¥ ( f ' É¥•¥: t.EE. " Salut § (n) Distributed Computing, COMP 4001 23 Graphs: Ball of Radius r • Consider the “red” node, call it u. • Ball Br(u): set of vertices at distance at most r from u. , , SCS (September 3, 2021) mounts 1st 3.se/2sec 14 =¥41 Distributed Computing, COMP 4001 24 Graphs: Connected • Connected graph. • One connected component. , , SCS (September 3, 2021) •¥2T Distributed Computing, COMP 4001 25 Graphs: Not Connected • Not a connected graph. • Three connected components; one isolated node , , SCS (September 3, 2021) Distributed Computing, COMP 4001 26 Graphs: Tree • Tree; connected; no cycles. , , SCS (September 3, 2021) A EF "An upside down free Distributed Computing, COMP 4001 27 Graphs: Forest • Forest; four connected components. • No cycles. , , SCS (September 3, 2021) satan' # ☒ ① A forest is a collection of frees not connected to eachother Distributed Computing, COMP 4001 28 Graphs: Cycle • Cycle graph, connected, 2-regular. , , SCS (September 3, 2021) ✗Xx g. ggy ° """ """ degreelats YuII. ¥¥¥ 3-regular Distributed Computing, COMP 4001 29 Graphs: Line • Path graph. • Tree, connected, maximum degree 2 , , SCS (September 3, 2021) ÉÉ Distributed Computing, COMP 4001 30 Graphs: Isomorphic • Two isomorphic graphs , , SCS (September 3, 2021) u→ flat Earl ⇒ ' Élflul ,fH ) Distributed Computing, COMP 4001 31 Graphs: Isomorphism • Two isomorphic graphs; bijection that preserves the structure , , SCS (September 3, 2021) o_0 Distributed Computing, COMP 4001 32 Isomorphic Graphs: Example • Three isomorphic graphs • Three more isomorphic graphs (Petersen graph) , , SCS (September 3, 2021) ÷ ✓ ✓ More complex Distributed Computing, COMP 4001 33 Graphs: More Examples • Three graphs: K5, C5, Q3 • Three graphs: Star, Wheel, Windmill , , SCS (September 3, 2021) ¥7s, ✓ • Distributed Computing, COMP 4001 34 Fundamentals • A graph G = (V,E) is an abstract object formed by a set V of vertices (nodes) and a set E of edges (links) that join (connect) pairs of vertices. • The vertex set and edge set of a graph G are denoted by V (G) and E(G), respectively. • The cardinality of V is usually denoted by n, the cardinality of E by m. • The two vertices joined by an edge are called its endvertices. • If two vertices are joined by an edge, they are adjacent and we call them neighbors. , , SCS (September 3, 2021) "i D Ket = Ii> Till 😉
Bra =
lil (
Distributed Computing, COMP 4001 35
Fundamentals
• Graphs can be undirected or directed. In undirected graphs,
the order of the endvertices of an edge is immaterial.
• An undirected edge joining vertices u, v 2 V is denoted by
{u, v}.
• In directed graphs, each directed edge (arc) has an origin (tail)
and a destination (head).
• An edge with origin u 2 V and destination v 2 V is represented
by an ordered pair (u, v).
• As a shorthand notation, an edge {u, v} or (u, v) can also be
denoted by uv.a
aIn a directed graph, uv is short for (u, v), while in an undirected graph, uv
and vu are the same and both stand for {u, v}.
, , SCS (September 3, 2021)
0
(un) u•→zv
0
a
•→
Distributed Computing, COMP 4001 36
Graphs: Handshake Theorem
• Theorem 1 Let G = (V,E) be a graph. Then the following
holds: X
v2V
deg(v) = 2|E|.
, , SCS (September 3, 2021)
• Every edge has two vertices
÷:
Distributed Computing, COMP 4001 37
Distributed Computing
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 38
Distributed System
• Intuition:
– distributed system
⇡ communication network
⇡ network equipment + communication links
– distributed algorithm
⇡ computer program
• Precisely how are we going to model this?
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 39
Port Labels: Numbering
• Ports (per node)
• Ports are usually labeled as numbers.
, , SCS (September 3, 2021)
②
Distributed Computing, COMP 4001 40
Port Numbering: Abstraction
• Network device = state machine with communication ports
• Ports at the node are numbered: 1, 2, 3, 4
• Node’s point of view:
1
2 3
4
, , SCS (September 3, 2021)
⑨ ③ 12
If Ignore1ft permute ✗✗✗✗
u differentthe labels
will anything more cpap samsung
names
change?
Node u can
distinguish
the four
ports
Distributed Computing, COMP 4001 41
Port Numbered Network
• Network = several devices, connections between ports
• Abstraction
1
2 3
4
1
2 3
, , SCS (September 3, 2021)
U 4
1
~
U
O
On
Distributed Computing, COMP 4001 42
Port Labeling (Numbering)
• There is an underlying graph G = (V,E).
– V is the set of nodes.
– E is the set of edges.
– Each vertex u has a number of neighboring vertices: called
the degree of u (sometimes denoted by d(u)).
• A port labeling is a triple N = (V, P, p)
– P is a set of pairs (u, i), where u 2 V and i < d(u).
– p : P ! P is the port function such that if p(u, i) = (v, j)
then {u, v} is an edge, i is the port number on this edge at
u pointing from u to v, and j is the port number on this
edge at v pointing from v to u.
, , SCS (September 3, 2021)
vertices
links dlut-deg.lu)
0142,314dcu
_¥-¥
Distributed Computing, COMP 4001 43
Port Numbered Network
• Nodes V = {u, v, . . .}
• Ports P = {(u, 1), (u, 2), (u, 3), (u, 4), (v, 1), (v, 2), (v, 3), . . .}
• Connections p(u, 4) = (v, 1), p(v, 1) = (u, 4), . . .
, , SCS (September 3, 2021)
✗
✗ .
plus 4) = (v , 2)
Distributed Computing, COMP 4001 44
Port Numbered Network
• Nodes V = {u, v, . . .}
• Ports P = {(u, 1), (u, 2), (u, 3), (u, 4), (v, 1), (v, 2), (v, 3), . . .}
• Connections p(u, 4) = (v, 1), p(v, 1) = (u, 4), . . .
• Not a complete example, some ports not connected!
, , SCS (September 3, 2021)
0.0
.
Distributed Computing, COMP 4001 45
Port Numbered Network
• nodes V = {a, b, c, d}
• ports P = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (c, 1), (c, 2), (d, 1)}
connections p(a, 1) = (b, 1), p(b, 1) = (a, 1), . . .
• All ports connected
, , SCS (September 3, 2021)
b
a
d
c
deg (a) =3
deg (b) = 2
degcd)-1 deg E) = 2
Distributed Computing, COMP 4001 46
Port Numbered Network
• nodes V = a finite set
• ports P = a finite set of (node, number) pairs
• connections p = an involution P ! P
• involution: p�1 = p; p(p(x)) = x
, , SCS (September 3, 2021)
^
,
¥4
-
-⑨
Distributed Computing, COMP 4001 47
Loops
• We may have multiple connections or loops
• p(c, 3) = (c, 4), p(c, 4) = (c, 3), p(d, 2) = (d, 2)
, , SCS (September 3, 2021)
F.
÷ - ¥
Distributed Computing, COMP 4001 48
Simple Port Numbering
• Simple port-numbered network:
• no multiple connections, no loops
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 49
Underlying Graph
• Underlying graph of a simple port-numbered network
, , SCS (September 3, 2021)
⇐
Distributed Graph
Computing Repr .
Representation
Distributed Computing, COMP 4001 50
The Power of Ports
• Ports are very useful in distributed computing:
– Can be used to orient consistently a graph.
– Can be used to embed a graph into another.
– Can be used to forward messages to correct destination.
– Can be used to broadcast.
– . . .
• Ports are everywhere . . . even when we do not mention them!
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 51
The Power of Ports: Line
• L,R
• Can you orient the line consistently?
• In how many ways?
• How do you assign port labels?
, , SCS (September 3, 2021)
MR 1 R e , , *②
Orientationcanonical
2 3 4 5
M①R→¥④R-€-
1. Send Mt 1 . Send all
{ 2. Forward righto }⇐§ . Harward R \R Unless yourID is 2 in
which case forward I
Distributed Computing, COMP 4001 52
The Power of Ports: Grid
• N,S,E,W
• Can you orient the grid consistently?
• In how many ways?
• How do you assign port labels?
• Can you embed a line graph into a grid?
, , SCS (September 3, 2021)
Thy
Distributed Computing, COMP 4001 53
The Power of Ports: Trees
• How do you use port labels to traverse all the vertices of the
tree?
• Can you embed a line graph in the tree? Of what size?
, , SCS (September 3, 2021)
pre-order
⑤
traversal
Distributed Computing, COMP 4001 54
The Power of Ports: Ring
• CW, CCW
• How do you orient a ring graph?
, , SCS (September 3, 2021)
'
Canonical
:
Can simplify
""taken
an algorithm .
Distributed Computing, COMP 4001 55
The Power of Ports:
• How do you label this graph?
• Maybe this is not the right question!
• How do you label this graph to achieve a particular goal?
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 56
Distributed Algorithms
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 57
State Machine
• State machine,
– x = current state:
– x init(z): initial state for local input z
– send(x): construct outgoing messages
send(x) = vector, one element per port
– x receive(x,m): process incoming messages
m = vector, one element per port
• How powerful are these commands? What do they mean?
, , SCS (September 3, 2021)
*¥
.
÷¥÷¥I
send 1×1 :
(Si
,
Sa
, S3 )
i 2 3
d = degree
✗ ← rec Mn , . . - , mad. )
Distributed Computing, COMP 4001 58
Execution
• Execution of algorithm A in network N
• All nodes of N are identical copies of the same state machine A
– functions init, send, and receive may depend on node
degree (number of ports)
– in all other aspects the nodes are identical
• All nodes are initialised
• Time step (communication round):
– all nodes construct outgoing messages
– messages are propagated
– all nodes process incoming messages
• Continue until all nodes have stopped
, , SCS (September 3, 2021)
7am
'
A single
} round
⑨
RoundI ⇒ Round[⇒ Rounds!
Advantage is that we do
not have to use clocks !
Distributed Computing, COMP 4001 59
Communication Round
• For the graph
• Construct outgoing messages
, , SCS (September 3, 2021)
d
i.
a
Distributed Computing, COMP 4001 60
Communication Round
• Exchange messages along communication links
, , SCS (September 3, 2021)
0
" simultaneously
"
Distributed Computing, COMP 4001 61
Communication Round
• Exchange messages along communication links
, , SCS (September 3, 2021)
0
Distributed Computing, COMP 4001 62
Communication Round
• Process incoming messages
, , SCS (September 3, 2021)
a
Distributed Computing, COMP 4001 63
Communication Round
• Construct outgoing messages
• Exchange messages along communication links
• Process incoming messages
• Communication rounds are synchronous
• Each step happens synchronously in parallel for all nodes
• Everything is deterministic,...
• ...but sometimes we may have to randomize!
, , SCS (September 3, 2021)
_
Distributed Computing, COMP 4001 64
Distributed Algorithm
• Algorithm designer chooses:
– how to initialize nodes
– how to construct outgoing messages
– how to process incoming messages
• Network structure determines:
– how messages are propagated between ports
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 65
Solving a Problem
• Algorithm A solves graph problem ⇧ on a family of graphs F if:
– for any graph G 2 F ,
– for any simple port-numbered network N that has G as
underlying graph,
– the execution of algorithm A on the network N stops, and
produces a valid solution of the problem ⇧
• NB: Both the problem ⇧ as well as the family of graphs F
must be well-defined!
, , SCS (September 3, 2021)
0
If there are faults (
nodes tael
links fail )
% then degsign • f- an algorithm
can be more complicated
Distributed Computing, COMP 4001 66
Solving Vertex Cover on Regular Graphs
• Problem ⇧: vertex cover V 0 of an undirected graph
G = (V,E) is a subset of V such that: if {u, v} 2 E then
u 2 V 0 or v 2 V 0
• Family of graphs F : G is a regular graph.
• Solution: Algorithm A finds a minimum vertex cover in any
“regular graph”:
– for any simple port-numbered network G that has a
“regular graph” as underlying graph,
– execution of A on the graph G, stops,
– the stopping states of the nodes are 0 and 1,
– nodes in state 1 form a minimum vertex cover
, , SCS (September 3, 2021)
o_0
u
V
Distributed Computing, COMP 4001 67
Example
• Design a distributed algorithm that finds a minimum vertex
cover for the family of graphs
F = { , }
• A correct algorithm could output the following solution
F = { , }
The marked vertices form vertex covers in each graph.
• First add port numberings:
F = { 1 1 2 1 2 1 ,
1 1 2 1 2 1 2 1
}
• Another representation is the following
, , SCS (September 3, 2021)
4
5
1111
⇒
0000
EBBE
¥aB⇒E→
oA¥ÉO
OB_⑧B_B0-B→
Distributed Computing, COMP 4001 68
Example: In One Round of send/receive
• Distributed Algorithm
1. send
(a) if your degree is 1 send message A (from port 1);
(b) if your degree is 2 send message B (from both ports 1, 2);
2. receive
(a) if you receive only one B you are not in the cover set;
(b) if you receive (B,B) you are not in the cover set;
(c) if you receive either (A,B) or (B,A) you are in the cover
set
• Running Time one communication round
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 69
Important Themes in
Distributed Computing
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 70
Important Themes (1/2)
• Communication: How does it compare to the cost of local
processing or storage?
• Coordination: How can you coordinate a distributed system
so that it performs some task e�ciently?
• Fault-tolerance: Distributed systems can survive even in the
presence of failures.
• Locality: Global information is not always needed to solve a
task, often it is su�cient if nodes talk to their neighbors.
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 71
Important Themes (2/2)
• Parallelism: Can you solve a task faster if you increase the
number of nodes that can share the workload?
• Symmetry breaking: Computation (and communication)
needs to be selected and orchestrated.
• Uncertainty: As the whole system is distributed, the nodes
cannot know what other nodes are doing at this exact moment,
and the nodes are required to solve the tasks at hand despite
the lack of global knowledge.
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 72
Optimization
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 73
Optimization: Max
• Maximization problems:
– maximal = cannot add anything maximum = largest
possible size ↵-approximation = at least 1/↵ times
maximum
• Example: independent set
– maximal is trivial to find greedily, maximum may be very
di�cult to find
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 74
Optimization: Min
• Minimization problems:
– minimal = cannot remove anything
– minimum = smallest possible size
– ↵-approximation = at most ↵ times minimum
– competitive ratio
• Example: Vertex Cover
– minimal is trivial to find greedily, minimum may be very
di�cult to find
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 75
Optimization: Terminology
• “↵-approximation of minimum vertex cover” implies two
properties:
1. vertex cover
2. at most ↵ times as large as minimum vertex cover
• Approximations are always feasible solutions!
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 76
Exercisesa
1. Contrast Sequential, Distributed and Parallel Computing.
2. What is more general: (a) An algorithm for directed or
undirected networks? (b) A control algorithm for centralized or
decentralized basic algorithms?
3. (?) Let �(G) denote its diameter of a graph G.
(a) What is its diameter of a complete binary tree T on n nodes
as a function of its height?
(b) Let G be a graph with n nodes and maximal degree d � 3.
Show that
�(G) �
log2 n
log(d� 1)
� 2
4. Define the average degree of graph.
(a) Use the handshake theorem to derive a closed formula for
aNot to hand in!
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 77
the average degree of graph.
(b) What is the average degree of a ring of n nodes?
(c) What is the average degree of a rline graph of n nodes?
(d) What is the average degree of a complete binary tree?
5. A robot B is to cross a road, while another robot A is moving
from left to right. Assuming that each
robot can determine the (x, y) coordinate of both the robots,
outline the program for each robot, so that they do not collide
with each other. You can assume that (a) the clocks are
synchronized, and (b) the robots advance in discrete steps –
with each tick of the clock, they move one foot at a time.
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 78
6. In a network of processes, every process knows about itself and
its immediate neighbors only. Illustrate with an example how
these processes can exchange information to gain knowledge
about the global topology of the network.
7. Sixteen sensors are being used to monitor the average
temperature of a vineyard. Each sensor has limited
communication ability and can communicate with two other
sensors only. The wireless network of sensors is not partitioned.
Find out how each sensor can determine the average
temperature of the vineyard.
8. Give an algorithm to construct a maximal independent set in
an arbitrary graph. What is the size of the independent set
constructed if the underlying graph is a line of n nodes? (Give
upper and lower bounds.)
, , SCS (September 3, 2021)