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)
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)
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)
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)
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)
Distributed Computing, COMP 4001 7
The Traditional Perspective
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 8
The Distributed Perspective
, , SCS (September 3, 2021)
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)
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)
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)
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)
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)
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)
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)
Distributed Computing, COMP 4001 24
Graphs: Connected
• Connected graph.
• One connected component.
, , SCS (September 3, 2021)
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)
Distributed Computing, COMP 4001 27
Graphs: Forest
• Forest; four connected components.
• No cycles.
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 28
Graphs: Cycle
• Cycle graph, connected, 2-regular.
, , SCS (September 3, 2021)
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)
Distributed Computing, COMP 4001 31
Graphs: Isomorphism
• Two isomorphic graphs; bijection that preserves the structure
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 32
Isomorphic Graphs: Example
• Three isomorphic graphs
• Three more isomorphic graphs (Petersen graph)
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 33
Graphs: More Examples
• Three graphs: K5, C5, Q3
• Three graphs: Star, Wheel, Windmill
, , SCS (September 3, 2021)
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)
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 ∈ 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 ∈ V and destination v ∈ 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)
Distributed Computing, COMP 4001 36
Graphs: Handshake Theorem
• Theorem 1 Let G = (V,E) be a graph. Then the following
holds: ∑
v∈V
deg(v) = 2|E|.
, , SCS (September 3, 2021)
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)
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)
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 ∈ 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)
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)
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)
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)
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)
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)
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 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)
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)
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)
Distributed Computing, COMP 4001 54
The Power of Ports: Ring
• CW, CCW
• How do you orient a ring graph?
, , SCS (September 3, 2021)
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)
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)
Distributed Computing, COMP 4001 59
Communication Round
• For the graph
• Construct outgoing messages
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 60
Communication Round
• Exchange messages along communication links
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 61
Communication Round
• Exchange messages along communication links
, , SCS (September 3, 2021)
Distributed Computing, COMP 4001 62
Communication Round
• Process incoming messages
, , SCS (September 3, 2021)
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 ∈ 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)
Distributed Computing, COMP 4001 66
Solving Vertex Cover on Regular Graphs
• Problem Π: vertex cover V ′ of an undirected graph
G = (V,E) is a subset of V such that: if {u, v} ∈ E then
u ∈ V ′ or v ∈ V ′
• 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)
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)
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 efficiently?
• 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 sufficient 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
difficult 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
difficult 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)