I found this interesting: According to Culler, Singh and Gupta, another implication of contention is that it "can hold up other resources and stall transactions that don't even need the resource that is the source of the contention. This is similar to the way contention for a single-land exit off a multilane highway causes congestion on the entire stretch of highway. The resulting congestion also affects cars that don't need that exit, but want to keep going on the highway since they may be stuck behind cars that do need that exit. The backup of cars covers up other unrelated resources (like previous exits), making them inaccessible and ultimately clogging up the highway."
FarmerScrub
In the flat communication example, all the processes are trying to update the same variable. If the updates all start in the same time window, there will be a queue of updates, which would cause a linear runtime.
In the tree structured communication example, processes in different branches are able to update a variable at the same time, even when there is contention.
stee
However, in the tree structured communication example, it will take longer for each leaf to update a variable (the path from the leaf to the actual resource is longer than that in the flat communication). Therefore, it is important to consider the request frequencies when designing either communication structure.
ok
I am confused about how the tree structured communication reduces contention, could someone clarify this please?
CaptainBlueBear
@ok Instead of every process trying to update the same variable which leads to a long queue, in the tree structure, there is a smaller set of processes interacting directly with the shared variable. So for example, in the image on the slide, the two leaf nodes on the left don't have to contend with the 2 leaf nodes on the right. Instead of having to wait for all 4 other nodes to access the root, they now only have to wait for 2 (their parent node and then each other).
I found this interesting: According to Culler, Singh and Gupta, another implication of contention is that it "can hold up other resources and stall transactions that don't even need the resource that is the source of the contention. This is similar to the way contention for a single-land exit off a multilane highway causes congestion on the entire stretch of highway. The resulting congestion also affects cars that don't need that exit, but want to keep going on the highway since they may be stuck behind cars that do need that exit. The backup of cars covers up other unrelated resources (like previous exits), making them inaccessible and ultimately clogging up the highway."
In the flat communication example, all the processes are trying to update the same variable. If the updates all start in the same time window, there will be a queue of updates, which would cause a linear runtime.
In the tree structured communication example, processes in different branches are able to update a variable at the same time, even when there is contention.
However, in the tree structured communication example, it will take longer for each leaf to update a variable (the path from the leaf to the actual resource is longer than that in the flat communication). Therefore, it is important to consider the request frequencies when designing either communication structure.
I am confused about how the tree structured communication reduces contention, could someone clarify this please?
@ok Instead of every process trying to update the same variable which leads to a long queue, in the tree structure, there is a smaller set of processes interacting directly with the shared variable. So for example, in the image on the slide, the two leaf nodes on the left don't have to contend with the 2 leaf nodes on the right. Instead of having to wait for all 4 other nodes to access the root, they now only have to wait for 2 (their parent node and then each other).