Basic Read/Write Algorithm

The basic write algorithm can be described as ``write to many, wait for a few to reply.'' Conceptually, the stub writes to more bricks than are necessary, namely $W$, and only waits for $WQ$ bricks to reply. Sending to more bricks than are necessary allows us to harness redundancy to avoid performance coupling; a degraded brick will not slow down a request. In the case where $WQ$ bricks do not reply within the timeout, the stub throws an exception so that the caller can handle the exception and act accordingly (e.g., signal to the end user to come back later), rather than being forced to wait indefinitely. This is part of the system applying backpressure. The algorithm is described below:

Cookie Write(HashKey H, Object v, Expiry E) 
    throws SystemOverloadedException

0  Time wakeup = getCurrentTime() + timeout;
1  int cs = checksum(H, v, E);
2  Brick[] repliedBricks = {};
3  Brick[] targetBricks = chooseRandomBricks(W);
4  foreach brick in targetBricks
5     do WriteBrick(H, v, E, cs);
6  while (repliedBricks.size < WQ)  
7     Time timeleft = wakeup - getCurrentTime();
8     Brick replied = receiveReply(timeleft);
9     if (replied == null) break;
10     repliedBricks.add(replied);   
11 if (repliedBricks.size < WQ) 
12    throw new SystemOverloadedException();
13 int check = checksum(H, repliedBricks, cs, E);
14 return new Cookie(check, H, repliedBricks, cs, E);

The stub handles a read by sending the read to $R$ bricks, waiting for only 1 brick to reply:

Object Read(Cookie c) throws CookieCorruptedExcept,
   SystemOverloadedExcept, StateExpiredExcept,
   StateCorruptedExcept

0  int check = c.checksum;
1  int c2 = checksum(c.H, c.repliedbricks, c.cs, c.E); 
2  if (c2 != check)
3     throw new CookieCorruptedException();
4  if (isExpired(c.E)) 
5     throw new StateExpiredException();
6  Brick[] targetBricks = c.repliedBricks;
7  foreach brick in targetBricks
8    do RequestBrickRead(H, E, cs);
9
10 Brick replied = receiveReply(timeout);
11 if (replied == null) 
12    throw new SystemOverloadedException();
13 retval = replied.objectValue;
14 if (c.cs != checksum(retval)) 
15    throw new StateCorruptedException();
16 return retval;