Concurrent Reading and Writing using Mobile Agents

An example

• Consider initializing the values of a variable x at the nodes of an n-cube. Process 0 is the leader, broadcasting a value v to initialize the cube. Here n=3 and N = total number of processes = 2n = 8

• source

• Each process j > 0 has a variable x[j], whose initial value is arbitrary.
• Finally, x[0] = x[1] = x[2] = … = x[7] = v

Broadcasting using message passing

• {Process 0} m.value := x[0];
• send m to all neighbors
• {Process i > 0}
• repeat
• receive m {m contains the value};
• if m is received for the first time
• then x[i] := m.value;
• send x[i] to each neighbor j > I
• else discard m
• end if
• forever
• What is the (1) message complexity
• (2) space complexity per process?

• m

• m

• m

• Number of edges
• log2N

Broadcasting using shared memory

• {Process 0} x[0] := v
• {Process i > 0}
• repeat
• if there exists a neighbor j < i : x[i] ≠ x[j]
• then x[i] := x[j] (PULL DATA)
• {this is a step}
• else skip
• end if
• forever
• What is the time complexity?
• (i.e. how many steps are needed?)

• Arbitrarily large. Why?

Broadcasting using shared memory

• {Process 0} x[0] := v
• {Process i > 0}
• repeat
• if there exists a neighbor j < i : x[i] ≠ x[j]
• then x[i] := x[j] (PULL DATA)
• {this is a step}
• else skip
• end if
• forever

• 15

• 10

• 12

• 27

• 99

• 32

• 14

• 53

• Node 7 can keep copying from 5, 6, 4 indefinitely long before the value in node 0
• is eventually copied into it.

Broadcasting using shared memory

• Now, use “large atomicity”, where
• in one step, a process j reads the state x[k]
• of each neighbor k < j, and updates x[j]
• only when these are equal, but
• different from x[j].
• What is the time complexity?
• How many steps are needed?
• Time complexity is now O(n3) = O(log2N)3
• (n = dimension of the cube)

• Why?

Time complexity in rounds

• Rounds are truly defined for synchronous
• systems. An asynchronous round consists
• of a number of steps where every eligible
• process (including the slowest one)
• takes at least one step. How many rounds
• will you need to complete the broadcast
• using the large atomicity model?

• An easier way to measure complexity in rounds is to assume
• that processes executing their steps in lock-step synchrony