Topics for the First Exam
(Topics in bold are in the book)
Broadcast
On a ring topology
On a general network, by building a spanning tree
Leader Election
On a token ring ... possibly many initiators, we select the
node with the lowest id
Synchronization Primitives, in the standard OS sense
Semaphires
Monitors
Message passing
Synchronization (The bold stuff is
from chapter 5)
TAI time
UTC time (TAI with leap seconds)
How to synchronize a network
Each node has a "pretty good" clock
Cristian's Algorithm can correct for drift
As can the Berkeley Algorithm
Moving time forward is okay,
but moving time backward can't be done. Rather, we must
slow down our local clocks and let them "catch down."
Logical clocks
Lamport Timestamps
Global State
Consistent state of execution of a distributed system
Not necessarily a temporal snapshot
Chandy's and Lamport's distributed snapshot
Termination detection
We can use a distributed snapshot to detect termination
We are done when a snapshot shows all nodes are done
We can also use a tree-model of
computation
Some initiator begins a computation, and sends messages to
other nodes, considered its children
Each node performs the required computation, and sends a
"DONE" to the parent
Sometimes a node will have to send additional messages asking
other nodes to do some work
In this case, it must wait for "DONE"s from those nodes (its
children) before it can itself be DONE
When the initiator receives DONE from all its children,
computation has terminated
Mutual Exclusion
We could use a "mutex server" which
controls access to critical
regions
But this creates a bottleneck, and potential failure if the
mutex server goes down.
A distributed algorithm can be
employed
Lots of message passing and queueing
All nodes must give permission to a node who wishes to enter
critical region
Logical timestamps (such as Lamport's) used to break ties
Or back to the mutex server, we could detect that the server
had gone down, and elect a new server
This requires leader election on a general network
Suppose many nodes call for an election
Each initiator starts a calculation which broadcasts its
intention
and uses termination detection to conclude
that all nodes have seen his call for election
and also receives the ids of all other nodes
that have called for election, together with
the time of their call for election
When an initiator has concluded its calculation, it
determines which initiatior made the earliest call,
and broadcasts that initiator's id to the rest
of the network, as the new leader
Thus every initiator will announce the id of the "winner"
of the election
This newly elected leader becomes our new mutex server
What happens if the mutex server crashes while some process
is in the CR?
Makes a good test question!
Tree centers, central paths and medians
The median of a tree is the vertex whose average distance to
all other vertices is as small as possible
A tree has either one or two centers
If it has two centers, then they are adjacent
The central path of a tree is the minimal path whose maximum
distance to all other vertices is as small as possible
This path must contain all centers of the tree
We can thus find this central path by finding a center and
"growing" a path from the center toward the leaves of the tree
The center of a tree is the vertex whose maximum distance to
all other vertices is as small as possible
A tree has either one or two medians
The median and the center need not be the same
If a tree has two medians, then they are adjacent
A core of a tree is a path whose average distance to all other
vertices is as small as possible
A tree may have many cores
And these cores need not contain any median of the tree
But cores must have leaves for their endpoints
To find centers and medians in a distributed fashion:
We followed the presentation given in Esther Jennings' paper,
which I distributed in class
She modifies the Basic Algorithm given in the paper of Korach
et al., also distributed in class
When the Basic Algorithm terminates, the one or two SATURATED
nodes contain critical information
When they execute their RESOLVE functions, the tree's
median(s) and center(s) can be identified
Ms. Jennings modifies these RESOLVE functions to identify the
path center, in addition to Korach's medians and centers.
We initially assumed that the Basic Algorithm ran on a
synchronous network
in this case, there is only one SATURATED vertex prior to
the resolve function running
If the network is not synchronous, then there may be either
one or two SATURATED nodes
If there are two, then they must be adjacent
We then saw that modifying the algorithms for asynchronous
networks was not difficult
See Korach's paper, page 396
To find the core, we use the theorem that says that if we
select any vertex r of a
tree, find a rooted core containing r,
and let v be an endpoint of
that rooted core, then we may start with v and "grow" a core, using
information gained from our Basic Algorithm
Agreement
Dr. Abrahamson introduced the notion of agreement among
processes
Several processes perform the same computation to determine
the value of a bit
Some processes may be faulty, but the set of processes wants
to reach agreement on the result
With three processes, one faulty, we cannot have an algorithm
to reach agreement
But with four processes, one faulty, we can.
Dr. Abrahamson also gave a random algorithm for reaching
agreement
We went through the paper of Fischer et al., Impossibility of Distributed Consensus
with One Faulty Process
Here it is shown that in the asynchronous case, there can be no
distributed protocol for reaching consensus
For the proof, we consider the state of a system, which is a
snapshot of all processes, and undelivered messages
The proof proceeds by showing that under reasonable
assumptions, there is a bivalent initial state
We then show that for any protocol, we can concoct
circumstances under which that protocol will process the oldest message
in the message buffer, and afterward still be in a bivalent state
This proves that any protocol can be kept in a state
where it never reaches a consensus
(0, 1, *)-Addressing -- the Squashed Cube Conjecture
This topic followed the presentation of the handout of Chapter
9 from A Course in Combinatorics,
distributed in class
An n-dimensional
hypercube network has 2n
nodes
each labeled with a unique binary string of length n
In this hypercube network, the distance between any two nodes
is exactly the Hamming distance between their binary labels
Packet forwarding is thus very straightforward: Forward
a packet to your neighbor so that the Hamming distance between the
packet's destination and its location decreases.
It is not possible to label the vertices of a triangle with
binary strings so that Hamming distance = network distance
But suppose we use the set {0, 1, *} to build strings to label
our nodes
Where the distance between two strings is the number of
places where one string has a 0 where the other has a 1
For example, the distance betweeen 0011** and 01*01* is 2,
because of positions 2 and 4
Then we can label the
nodes of a triangle network with 000, 01*, *01
The string distance between each pair of labels is 1, which
is also the network distance.
This can also be done with strings of length 2: 00, 01 1*.
We can view this last labeling as a "squashing" of a
2-dimensional cube, or square, along the edge connecting 10 with 11.
We saw in class how the triangle emerges from a squashing of
the 3-cube in the previous labeling with strings of length 3
We wish to take a general topology and label its nodes with
strings over {0, 1, *} so that string distance equals network distance
We showed two ways to do this in a tree topology
First, inductively, where we built a tree by adding leaves,
each time adding a new bit to all labels, and creating a new label for
the new node
Second, by numbering the vertices according to a DFS on the
tree, and labeling bit i of
node j :
1 if node i is on
the path from the root to node j
0 otherwise
In fact, it can be shown that for trees on n vertices, strings of length n - 1 are the shortest possible.
Peter Winkler proved that the nodes in any topology may be
labeled
with (0, 1, *)-strings of length at most #nodes -1
So that string distance equals network distance for every
pair of nodes
His proof starts by doing a BFS of the network to build a
spanning tree
Then labeling these nodes in a DFS fashion, and assigning
strings as we did for trees above
Finally, some of the 0s were changed to *s, according to a
Very Clever Rule