Wave Algorithms

Question 1

What are the fallacies of distributed computing? (Description)

Answer 1

Assertions describing false assumptions.

Question 2

List the 8 fallacies of distributed computing

Answer 2

1. Network is reliable
2. Network Latency is zero
3. Bandwidth is infinite
4. Network is secure
5. Topology doesn’t change
6. One administrator
7. Transport cost is zero
8. Network is homogenous

Question 3

What are the 2 assumptions made throughout?

Answer 3

1. System is asynchronous
2. Process identity is unique

Question 4

A process is abstracted as a ____ of _____

Answer 4

Sequence of Events

Question 5

If event A has precedence over event B, how do we write it?

Answer 5

a < b

Question 6

What is a meaningless system?

Answer 6

Each process executes at least one event and no event is related to another.

Question 7

Describe a simple wave algorithm

Answer 7

P broadcasts M; decides after every process has acknowledged M to P.

Question 8

When is a wave algorithm centralised?

Answer 8

If there must be exactly one initiator per execution.

Question 9

Describe a Tree Algorithm’s principles

Answer 9

• A process waits until it receives a <tok> from all but its silent neighbour</tok>
• The process sends a <tok> to it's silent neighbour</tok>
• If process receives <tok> from SN, it decides.</tok>

Question 10

Is an echo algorithm centralised or decentralised?

Answer 10

Centralised.

Question 11

What are the principles of an echo algorithm?

Answer 11

• Initiator sends token to all its neighbours
• When a non-initiator FIRST receives a token, it:
  1. Notes down token sender as father.
  2. Sends token to all neighbours except father
  3. After receiving token from all neighbours, it sends a token to father.
• When initiator receives token from all neighbours, it decides.