README.md

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

1. Assign a random number to all vertexes.
2. If a vertex's number is strictly larger than the ones of its neighbors, remove all neighbors.
3. 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 ith input with the i+n/2th 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.

10. Lecture

TODO

11. Lecture

TODO

12. Lecture

Setup

Messages have to be routed in a fully connected graph with n nodes. Each edge can only deliver one message per round.

Solution

Construct graph with all nodes once on the left and once on the right side. For each message that has to be sent, add an edge that connects the sender edge on the left and the receiver on the right. Do a 2\Delta +1 coloring of the edges, and use the node corresponding to the color as a relay for this message.

Coloring

The coloring can be randomized. However, since the colors are random, it is possible that edges from sender to relay or relay to target are double assigned. Therefore 5\log n copies of each message are sent. Assuming each node only sends and receives at max \frac{n}{20\log n} messages, all messages are successfully transmitted with probability 1-\frac{1}{n^3}.

13. 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 in 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

In each round k, transmit ck times with probability \frac{1}{2^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.