-
Noah Zarro authoredNoah Zarro authored
1. Lecture
Key Concepts
- Edges can communicate with each other
-
\delta
is the degree of a node -
\Delta
is the maximum degree of any node in the tree -
\Chi
is the Chromatic Number, i.e. the least number of colors needed to color the graph - Usually generic fast algorithms need
\Delta+1
colors - Trees always have
\Chi\leq1
- Log* is how many nested logs must be taken
- Six-2-Three Algorithm 3-colors a tree in
\mathcal{O}(Log^* n + k)
Language
Symbol | Meaning |
---|---|
\delta |
degree of a node |
\Delta |
maximum degree of any node in the tree |
\Chi |
Chromatic Number, i.e. the least number of colors needed to color the graph |
Greedy Sequential
2. Lecture
- Radius: Max distance to another node
- Diameter: Max radius of any node in a network
Building a Tree
It can be done with flood and echo, but due to the asynchronous nature of the algorithms maybe not the shortest paths from the root to the leafs is found
It can be improved with Dijkstra, where a tree is built level by level, but this takes a lot of messages
It can be further improved by Bellmann-Ford, which works like BGP, but there the algorithm does not terminate.
MST
The GHS algorithm works as follows: Nodes are split into fragments with roots. The root then asks for the cheapest outgoing edge from the fragment (called blue edge). This edge then is added to the fragment and the fragments are merged. The node who found the cheapest edge becomes the new root and repeats the process until there are no other fragments left.
3. Lecture
Cover Free Families
A set of sets. If one set is chosen then it contains always an element that is not contained in the union of any other set.
Livindals Algorithm
Assign a set from the cover free sets to each of the nodes. Then if every node learns which set his neighbors have, it can then choose a color that is not in the union of the sets of his neighbors. This has complexity \mathcal{O}(1)
, but is not very optimal yet.
Color Reduction
To further reduce the colors needed to \Delta+1
, the colors are grouped into groups with size 2\Delta+2
. Then in every round the node with the highest color in the group chooses a color from the lower half of the group. Different groups do this in parallel, since they cannot choose the same color.
If one iteration is complete, the remaining colors are regrouped again in the same way, but now there are only half as many groups. This is done until only one group is left.
4. Lecture
A 2-coloring of a n-node directed path requires at least \Omega(n)
Any deterministic algorithm for 3-coloring n-node directed paths needs at least \frac{\log∗ n}{2}− 2
5. Lecture
Maximal Independence Sets
A subset of nodes of a graph, where no to nodes are neighbors.
MIS coloring
Copy the graph \Delta+1
times and connect all vertexes that where copied from an original vertex in full mesh, e.g. w, w', w'', w'''
. Then construct a MIS. Then color every original node with the number of the copy, the vertex chosen by the MIS exists in.
Luby's Algorithm
- Assign a random number to all vertexes.
- If a vertex's number is strictly larger than the ones of its neighbors, remove all neighbors.
- Repeat from 1. until no reduction has to be made anymore.
6. Lecture
to be written
7. Lecture
The goal is to develop algorithms that allow read and write access to a shared resource.
Basic Algorithms
In the centralized solution, the object is stored on a single node at the root of a spanning tree. This root handles all accesses.
The home-based solution works as above, but with a separate home for each object. (I guess)
Arrow Algorithm
An object lies always at the root of a spanning tree. If another object wants to access it, it traverses the tree up to the root, and inverts the parent/child relations on its way up. If the former root is found, the object is rooted back to the node that issued the request with any routing protocol.
Caching
Like in arrow, but read requests do not move the object, they only copy it and the root remains the same. When an object is read, the edges which the find message traverses are marked with a cache bit, and as soon as the object is written again, those bits are cleared.
Ivy And Friends
Ivy works similar to the arrow algorithm, but every time a find by u message traverses an edge, its parent is directly set to u. This lets new edges become part of the tree, and connects everybody as close as possible to the new root.
8. Lecture
0-1 Sorting Lemma
To prove correctness and time complexity, it is enough to just prove it for sorting lists/arrays with values 0 and 1. This holds for oblivious networks.
Oblivious
Whether you exchange two values must only depend on the relative order of the two values, and not on anything else.
Odd/Even Sort
Compare and swap two neighbors, where the left one is even, then where the right one is even. Repeat.
It takes n
steps, if performed on an array
Shearsort
In a grid, take turns to sort all columns and then all rows, repeat. In odd rows smaller values go left, in even rows they go right. This means that clean (sorted) rows start to appear on the top and the bottom. Each round cleans one half of the rows.
It takes 2\log m = \log n
rounds, i.e. it has also time complexity of \mathcal{O}(n\log n)
, like non distributed sorting algorithms.
Bitonic Sequence
A sequence of values that is first monotonically growing and then monotonically shrinking, or the other way round.
Half Cleaner
A sorting network, that compares the i
th input with the i+n/2
th input. If feed a bitonic sequence, it outputs one clean (sorted) half, and a half that is sorted in a bitonic sequence way.
Merging Network
A sorting network, that sorts two sorted lists into one sorted list.
Batcher’s “Bitonic” Sorting Network
A recursive sorting network that starts with single values (n
sorted lists) and merges two sorted lists to one in each step with a merging network
It has dept of \mathcal{O}({\log^2 n})
9. Lecture
It covers the calculation of the network diameter
Naïve Approach
Every node calculates its maximum radius by flooding echo. The largest radius is then chosen as the diameter. This leads to message congestion and has round complexity of \mathcal{O}(D)