-
Noah Zarro authoredNoah Zarro authored
- 1. Lecture
- Key Concepts
- Language
- Greedy Sequential
- 2. Lecture
- Building a Tree
- MST
- 3. Lecture
- Cover Free Families
- Livindals Algorithm
- Color Reduction
- 4. Lecture
- 5. Lecture
- Maximal Independence Sets
- MIS coloring
- Luby's Algorithm
- 6. Lecture
- 7. Lecture
- Basic Algorithms
- Arrow Algorithm
- Caching
- Ivy And Friends
- 8. Lecture
- 0-1 Sorting Lemma
- Oblivious
- Odd/Even Sort
- Shearsort
- Bitonic Sequence
- Half Cleaner
- Merging Network
- Batcher’s “Bitonic” Sorting Network
- 9. Lecture
- Naïve Approach
- BFS Based
- Fooling Sets
- Communication Complexity
- 11. Lecture
- Slotted Aloha
- Collision Detection - CD
- Initialization
- Without CD, n known
- With CD, n unknown
- Without CD, n unknown
- Leader Election
- Without CD
- With CD
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)
BFS Based
As the naïve approach, but each node only starts the flooding if it receives the pebble. The pebble is forwarded in a BFS way and pauses at each token one round to ensure that the flooding messages do not overlap. It has round complexity of \mathcal{O}(n) + \mathcal{O}(D) = \mathcal{O}(n)
Fooling Sets
A set where all nodes have the same value and each two nodes can span up a rectangle, where one of the edges has a different value than the nodes in the fooling set.
Communication Complexity
To test equality of to bit strings of length k
(a function with a fooling set as solution set) \mathcal{O}(\log 2^k)
bits have to be exchanged. After this, the solution set can be narrowed down to a single value. If fewer bits get exchanged, the solution set can still be a fooling set, which is not monochromatic (same values anywhere) and is therefore ambiguous.
11. Lecture
It covers the topic of wireless transport protocols to avoid collisions
Slotted Aloha
In this protocol, each node sends in a slot with probability 1/n
. The probability that in a slot any node successfully transmits is 1/e
. But n
must be known.
Collision Detection - CD
If a receiver can distinguish receiving nothing from receiving from more than one peer.
Initialization
The process of obtaining ids 1 \dots n
is called initialization. It can be achieved in the following ways:
Without CD, n known
Just do slotted aloha, each node that transmitted successfully gets the next ID.
With CD, n unknown
Sort peers into a binary tree, where each peer ends in a leaf. First all nodes are in the root node. In a node each peer selects either 1 or 0, and then sends either i n the slot 1 or 0. If a collision happens, peers move to the child node, corresponding to the slot they selected. If nobody transmitted in a slot, the corresponding child node can be ignored. If only one peer transmitted, it gets the next free ID. The tree is traversed until there are no collisions anymore.
Without CD, n unknown
Same as above, but each slot is split into two transmissions, one where only the leader l
transmits, and one where everybody who wants to transmit in this slot S
and l
transmit. Like this it can be distinguish if S
is empty or contains more than two peers. But a leader has to be determined first.
Leader Election
Without CD
Transmit in each round k
transmit ck
times with probability 1/k
, the first one to transmit alone becomes the leader.
With CD
Every node transmit in each round with probability 1/2
, if more than one node transmits, all nodes that did not transmit quit the protocol.