►zthomae’s SICP solutions
▼3 Chapter 3
3.1 Exercise 3.1
3.2 Exercise 3.2
3.3 Exercise 3.3
3.4 Exercise 3.4
3.5 Exercise 3.5
3.6 Exercise 3.6
3.7 Exercise 3.7
3.8 Exercise 3.8
3.9 Exercise 3.9
3.10 Exercise 3.10
3.11 Exercise 3.11
3.12 Exercise 3.12
3.13 Exercise 3.13
3.14 Exercise 3.14
3.15 Exercise 3.15
3.16 Exercise 3.16
3.17 Exercise 3.17
3.18 Exercise 3.18
3.19 Exercise 3.19
3.20 Exercise 3.20
3.21 Exercise 3.21
3.22 Exercise 3.22
3.23 Exercise 3.23
3.24 Exercise 3.24
3.25 Exercise 3.25
3.26 Exercise 3.26
3.27 Exercise 3.27
3.28 Exercise 3.28
3.29 Exercise 3.29
3.30 Exercise 3.30
3.31 Exercise 3.31
3.32 Exercise 3.32
3.33 Exercise 3.33
3.34 Exercise 3.34
3.35 Exercise 3.35
3.36 Exercise 3.36
3.37 Exercise 3.37
3.38 Exercise 3.38
3.39 Exercise 3.39
3.40 Exercise 3.40
3.41 Exercise 3.41
3.42 Exercise 3.42
3.43 Exercise 3.43
3.44 Exercise 3.44
3.45 Exercise 3.45
3.46 Exercise 3.46
3.47 Exercise 3.47
3.48 Exercise 3.48
3.49 Exercise 3.49
3.50 Exercise 3.50
3.51 Exercise 3.51
3.52 Exercise 3.52
3.53 Exercise 3.53
3.54 Exercise 3.54
3.55 Exercise 3.55
3.56 Exercise 3.56
3.57 Exercise 3.57
3.58 Exercise 3.58
3.59 Exercise 3.59
3.60 Exercise 3.60
3.61 Exercise 3.61
3.62 Exercise 3.62
3.63 Exercise 3.63
3.64 Exercise 3.64
3.65 Exercise 3.65
3.66 Exercise 3.66
3.67 Exercise 3.67
3.68 Exercise 3.68
3.69 Exercise 3.69
3.70 Exercise 3.70
3.71 Exercise 3.71
3.72 Exercise 3.72
3.73 Exercise 3.73
3.74 Exercise 3.74
3.75 Exercise 3.75
3.76 Exercise 3.76
3.77 Exercise 3.77
3.78 Exercise 3.78
3.79 Exercise 3.79
3.80 Exercise 3.80
3.81 Exercise 3.81
3.82 Exercise 3.82
    ← prev  up  next → 

3.43 Exercise 3.43

It should be the case that any number of concurrent exchanges between accounts should not violate the condition that each account always has a balance that one of the accounts originally had, and that every unique balance is represented once. This is essentially intuitively true: if the accounts are only allowed to swap values with one another, it should not be the case that any account ends up with a new value.

However, if the entire exchange is not serialized, this can happen. The difference between accounts A and B can be calculated before another transaction changes the balance in A, meaning that the withdrawal from A will be withdrawing from a balance that is not necessarily the same as it was when the difference was calculated. In essence:

a = 5

b = 10

c = 15

 

exchange(a, b):

  difference = 5 - 10

<-- set a to 15

  a = 15 + 5 = 20

  b = 10 - 5 = 5

If the entire exchange is serialized, as in the refined example, the second exchange cannot interrupt the first, making this situation impossible.

However, note that the sum of the balances is still preserved – that is, 5 + 10 + 15 == 20 + 5 + 5. This is a simple consequence of the fact that the net effect on the total balance of the accounts of an exchange is always zero, as long as transactions on the individual accounts are serialized. In other words, no new money is being introduced into the system as long as you only exchange balances – exchanging is a zero sum operation. If this were still not the case, then any withdrawal or deposit could be interrupted, causing the same sorts of problems we saw before.

    ← prev  up  next →