Registers

Question 1

how does the interface for registers look?

Answer 1

publicinterface Register<T>{
T read();
void write(T v);
}</T>

Question 2

What are the types of registers usually?

Answer 2

either boolead or m-bit nteger

Question 3

When is implementation wait-free

Answer 3

if every method call completes in a finite number of steps
no mutual exlusion

Question 4

What are the degrees of consistency

Answer 4

Safe,regular,atomic

Question 5

When is a register safe

Answer 5

Read that doesnt overlap write return last value
if overlap return any value within the registers range

Question 6

when is a register regular?

Answer 6

if no overlap return last value
else return either new/old value
(may flicker between old + new value until done)

Question 7

Regular = linearizable?

Answer 7

No

Question 8

When is a register atomic?

Answer 8

when each read returns last written value

Question 9

safeBoolMRSWRegister class

Answer 9

public class SafeBoolMRSWRegister
implements Register<Boolean> {
public boolean read() { … }
public void write(boolean x) { … }
}
(naming should be in that order)</Boolean>

Question 10

A safe boolean MRSW register can be created from safe boolean SRSW register how?

Answer 10

Make an array of SRSW registers

Question 11

Whats the difference between Safe and Regular BooleanMRSW?

Answer 11

only difference when new value is same as old value(safe can return either Boolean value, Regular can only return x since they are the same)

Question 12

How can we use SafeBoolMRSW to build Regular BoolMRSW?

Answer 12

(in the RegBoolMRSW class)
private SafeBoolMRSWRegister value;
public void write(boolean x) {
if (old != x) {
value.write(x);
old = x;
}}
and then the read is just return value.read() and old is just a bool value

Question 13

How does the read and write work for Regular M-Valued MRSW Register

Answer 13

read: read locations from lower to higher values until it reaches a value that is true
write: writes true to location x which is a regular Bool MRSW register

Question 14

Read and write for RegularMRSWRegister

Answer 14

public class RegMRSWRegister implements Register{
RegBoolMRSWRegister[M] bit;
public void write(int x) {
this.bit[x].write(true);
for (int i=x-1; i>=0; i–)
this.bit[i].write(false);
}
public int read() {
for (int i=0; i < M; i++)
if (this.bit[i].read())
return i;
}}

Question 15

What are some further conditions for a register to be regular?

Answer 15

no read should return a value from distant past/future. only most recent written non-overlapping value

Question 16

How should the stamped value class look like?

Answer 16

public class StampedValue<T> {
public long stamp;
public T value;
public StampedValue (T init) {
stamp = 0;
value = init;
}
public StampedValue max (StampedValue x,StampedValue y)
{
if (x.stamp > y.stamp)
return x;
else return y;
}
}</T>

Question 17

how should read + write look for Atomic SRSW register?

Answer 17

public T read() {
StampedValue<T> result = StampedValue.max(value,
lastRead);
lastRead = result;
return result.value;
}
public void write(T v) {
long stamp = lastStamp + 1;
value = new StampedValue(stamp, v);
lastStamp = stamp;
}</T>

Question 18

What type of array does a AtomicMRSWRegister use and why

Answer 18

2d of stamped values. to check if any of the other registers has written to the array while the read is taking place

Question 19

how does the write +read look for MRSW Atomic

Answer 19

public void write(T v) {
long stamp = lastStamp + 1;
lastStamp = stamp;
StampedValue<T> value = new StampedValue<T>(stamp,
v);
for (int i = 0; i < n; i++)
a_table[i][i] = value;
}</T></T>

Question 20

Can you construct a wait-free MRMW atomic register from SRSW safe boolean registers?

Answer 20

yes