8 - Tokenloss and traversal

Question 1

What is the purpose of tokens (in a ring topo)?

Answer 1

It is used in termination detection.

Question 2

In what kind of DA network structure do we expect to use tokens?

Answer 2

unidirectional ring topologies

Question 3

How many tokens are required to detect tokenlosses?

Answer 3

at least two.

Question 4

Explain the main idea of token loss detection.

Answer 4

• when token t0 passes through some node P for the second time in a row
• while in the meantime t1 has not passed through P
• and in the meantime t0 and t1 have not met in another node
• then t1 has been los

Question 5

What value(s) need to be tracked by each node in order to detect missing tokens?

Answer 5

1. The counter value of the last token that has passed through the node
2. Which tokens are currently present in the node.

Question 6

What is the psudo code for receiving a token in a ring.

Answer 6

upon receipt of (token;j,c) do
    token_present[j]= 1
    m[j] = c
    if ( (token_present[1-j]) or (l=c) ) then
        m[j] = c + sign(c) 
        m[1-j] = -m[j] 
        token_present[1-j] = 1
    endif
enddo

Question 7

What is the psudo code for sending a token in a ring.

Answer 7

when (token_present[j] and C(i,j)) do
    token_present[j]= 0
    send(token;j,m[j])
    l = m[j]

Question 8

Explain why tokens are only noticed by one node to be ‘missing’, and not by all nodes.

Answer 8

That node will regenerate new counter value for both tokens, meaning that the counter comparison in the other nodes will not ‘fail’ again.

Question 9

What is the goal of a traversal algorithm?

Answer 9

To construct a subnetwork of a network that contains all nodes and is a spanning tree.

Question 10

In traversal algorithms, what is set U ?

Answer 10

It is a set of a node’s links on which it has not yet sent the token. Set U also excludes any parent links (/nodes).

Question 11

Explain the rules of Tarry’s algorithm.

Answer 11

Upon node receival:
1. if U is not empty, it sends the token on any link in U
2. if U is empty, it sends the token to its parent

Question 12

How many times is a token send in the graph using Tarry’s algorithm? explain

Answer 12

2 |E|
Each node will receive a token over a link at least once, and therefor also has to send a token over each node once. Hence each link is used twice.

Question 13

What is the time complexity of Tarrys algorithm?

Answer 13

2 |E|

Question 14

In Traversal algorithms, how does a node decide its parent?

Answer 14

It decides that from whoever it receives a token first, becomes that node’s parent

Question 15

What is the biggest drawback for tarry’s algorithm?

Answer 15

Number of messages send is very large, which makes it innefficient and time consuming.

Question 16

What is an DFS algorithm?

Answer 16

Depth-First Search algorithm

Question 17

Explain the rules of Cheung’s DFS (v1) algorithm.

Answer 17

1. Upon receiving the token for the first time or
   on a link not in U:
   a. if U is not empty, send the token on any link in U
   b. if U is empty, return the token to parent.
2. Upon receiving the token not for the first time and on a link in U: reflect the token back on the same link.

Question 18

Explain what reflecting is in cheung’s DFS (v1) algorithm.

Answer 18

Upon receiving the token not for the first time and on a link in U (so on an unused link), it sends the token back on the same link.

Question 19

How many messages are send in Cheung’s DFS algorithm?

Answer 19

2|E|

Question 20

Explain the rules of Cheung’s DFS (v2) algorithms

Answer 20

1. Upon receiving the token for the first time or receiving an echo:
   a. if U is not empty, send the token an any link in U
   b. if U is empty, send an echo to its parent
2. Upon receiving the token not for the first time, send an echo back

Question 21

Wha tis the time complexity of Cheung’s DFS algorithm?

Answer 21

2|E|

Question 22

Explain Awerbuch’s DFS algorithm.

Answer 22

It is an adaption from Cheung’s DFS algorithm. Each node will ask some of its neighbours if a token has already visited that neighbour. It will only forward the token to neighbours that have not yet had the token.

Question 23

What are the consequences of Awerbuch’s DFS algorithm? (compared to Cheung’s)

Answer 23

1. It reduces the amount of times the token is transferred (only meaningful transfers happen).
2. Each node can conclude if it has received the token for the second time, its from its child.
3. Higher message complexity overall.

Question 24

What is the message complexity of Awerbuch’s DFS algorithm?

Answer 24

2(|V|-1) + 4 |E|

(The first part describes the token traversion through the tree, the second part describes the ‘visited’ messages)

Question 25

What is the time complexity of Awerbuch’s DFS algorithm?

Answer 25

4(|V|-1)

Question 26

Explain Cidon’s DFS algorithm.

Answer 26

Its an adaption of Awerbuch.
Whenever a process receives the token, it sends a “visited” signal to its neighbours. It then forwards the token to a link it has not received a “visited” from. ( And not its parent. ). The token still gets returned to the parent after no links are suitable for token transfer.

Question 27

How is Cidon’s DFS algorithm protected against deadlocks?

Answer 27

When process Q sends the token to R, it sends a “visited” to P. R then sends the token to P. However, the token arrives earlier to P then the “visited” from Q. In this case P could send the token to Q. Afterwards it receives the visited. This normally would result in a incomplete tree/deadlock. However, P tracks its sents and visited, thus realising its mistake. It generates a new token and continues building the spanning tree.