Proving algorithms

Question 1

Prove that First-BFS Construction is self-stabilizing.

Answer 1

Lemma:
d = the maximum number of links adjacent to a processor

For every k > 0 and for every configuration that follows d + 4kd rounds, it holds that:
Assertion 1: If there exists a floating distance, then the value of the smallest floating distance is at least k.
Assertion 2: The value in the registers of every processor that is within distance k from the root is equal to its distance from the root.

Prove lemma by induction on the number of rounds (base case k=1).

Lemma implies that algorithm is self-stabilizing.

Question 2

Correctness proof for Self-stabilizing Maximal Matching

Answer 2

Assume central daemon.

Use variant function VF(c) = (m + s, w, f, c).

Show that every change of a pointer value increases the value of VF. Shit is safe when VF(c) = (n,0,0,0)

“We can conclude that, indeed, every change in a pointer value increments the value of VF . The number of such pointer-value changes is bounded by the number of all possible vector values. The fact that m + s + w + f + c = n implies that the number of possible vector values is O(n3). A rough analysis uses the following argument. One can choose n + 1 possible values for m + s and then n+1 values for w and f . The value of n and the first three elements of the vector (m + s, w, f, c) imply the value of c. Therefore the system reaches a safe configuration within O(n3) pointer-value changes.

Question 3

Correctness proof for Leader election in a General Communication Network

Answer 3

Convergence stairs,

A1:

LEMMA 2.5: Every fair execution that starts from any arbitrary configuration has a suffix in which no floating identifier exists.

If a floating identifier exists, its minimal distance increases every O(d) rounds. A processor Pi, with the shortest-distance floating identifier, will in its loop choose a distance either the same or one greater than its neighbor’s (from line 8). Hence, if Pi opts for a floating identifier, the distance is at least one more than before. When this distance equals N, processors cease selecting floating identifiers, resulting in their termination.

A2: i don’t have a fucking clue

Every fair execution that starts from any arbitrary configu- ration reaches a safe configuration.

Question 4

Correctness proof of Leader election in a complete graph

Answer 4

THEOREM 2.4: If luck has an (cp,r)-strategy, then reaches a safe con- figuration within, at most, r/cp expected number of rounds.

Proof: Utilizing theorem 2.4, we demonstrate that the algorithm stabilizes in no more than 2n rounds. We introduce a (1/2^n, 2n)-strategy where luck ensures victory in the sl-game defined by the algorithm across all configurations and safe configurations. The strategy dictates: if a processor Pi flips a coin and all other processors j (where j ≠ i) have leaderj = 0, luck sets the coin toss to 1; otherwise, it’s set to 0. Within 2n rounds, every processor Pi reads all leader registers, and if necessary, flips a coin to update leaderi. If no coin is tossed in these 2n rounds, the system attains a safe configuration.

Question 5

Correctness proof of Self-stabilizing counting

Answer 5

Induction on the height of the tree, show that counti is correct for base case k=1

Question 6

Correctnees proof of Self-stabilizing naming

Answer 6

Induction on the distance of the processors from the root.

Base case: A tree with a single processor (the root).

Inductive Step: Assume that the algorithm correctly names processors up to distance k from the root. This means that every processor at distance k from the root has a unique identifier.

Prove that processors at distance k+1 from the root will also have a unique identifier.

Question 7

Correctness proof of The Update Algorithm

Answer 7

LEMMA 4.6: After the kth cycle, for every processor pair Pi and Pj distanced l with l < min(k,d + 1), two conditions hold:

• The tuple ⟨j,l⟩ is in Processorsi.
• For any tuple ⟨x,y⟩ in Processorsi with y ≤ l, there’s a processor Px distanced y from Pi.

Proof: By induction on the cycle number k.

LEMMA 4.7: In every arbitrary execution following d + 2 cycles, it holds for every tuple ⟨x, y⟩ in every Processorsi variable that a processor x exists in the system.

Proof: In accordance by Lemma 4.6.

COROLLARY 4.1: In any execution, any configuration that follows the first d + 3 cycles is a safe configuration.

Implied by Lemma 4.6 & Lemma 4.7