Go backward to Termination Go up to B.5 Verification

Time Complexity

Another question is the time complexity of the algorithm, i.e., when will have all nodes determined the network value (and correspondingly terminate)? The time complexity of the algorithm is the time from when node 0 triggers the snapshot until the time that the last node has determined the total result. This time is the sum of three components:

1. The time from the triggering of the snapshot until the node is notified about the snapshot.
2. The time from the node's notification of the snapshot until it has determined its snapValue.
3. The time from the determination of the node's snapValue until it has received all other node's snapValues to yield totalResult.

One should note that different nodes may be in different phases, i.e., one node may have not yet been notified about the snapshot while another is already broadcasting its snap value.

The algorithm's time complexity can be estimated by considering the maximum number of messages that an individual node has to process in a network of size n: the node has to receive at most i + i(n-1) + 1 input messages (where i is the input degree of the node) and to send send o + o n output messages (where o is the output degree of the node). Assuming i = o = d, the total number of messages processed is bounded by

2nd + d +1

235 = 2*19*6 + 6 + 1