#547 new defect

mapupdate(MODE_WRITE) triggers on a false boundary

Reported by: warner Owned by:
Priority: major Milestone: soon
Component: code-mutable Version: 1.2.0
Keywords: availability mutable mapupdate ucwe Cc:
Launchpad Bug:


"problem 1" in #546, is that the mapupdate code has a bug, in which it triggers too early. The MODE_WRITE logic waits for the following conditions:

  1. for the highest sequence number we've ever seen, we can recover all versions that have that sequence number
  2. we've received responses from at least k+epsilon servers
  3. we've seen a contiguous range of epsilon servers who do not have a share

The last criteria is intended to help us find the edge of the "active set": the boundary between servers who have shares (at the beginning of the permuted list) and those who do not (at the end of the list). The bug is in the way this last criteria is tested.

If we've queried 10 servers and received responses from 9 of them, in the pattern "00100010?1", the logic that looks for "1000" will fire:


Instead, the logic should be more like "1000$". At least it should not be allowed to fire if there are any share-holding servers beyond the match.

The consequence of this bug is to exacerbate the problems in #546: sending shares to servers which already have other shares, triggering inappropriate UncoordinatedWriteErrors.

Attachments (1)

cryptic_notes.txt (1.6 KB) - added by warner at 2008-12-05T07:05:35Z.

Download all attachments as: .zip

Change History (6)

Changed at 2008-12-05T07:05:35Z by warner

comment:1 Changed at 2010-03-24T23:11:48Z by davidsarah

  • Keywords availability added

comment:2 Changed at 2010-03-24T23:12:10Z by davidsarah

  • Milestone changed from undecided to 1.7.0

comment:3 Changed at 2010-05-27T22:07:41Z by zooko

  • Milestone changed from 1.7.0 to 1.8.0

It's really bothering me that mutable file upload and download behavior is so finicky, buggy, inefficient, hard to understand, different from immutable file upload and download behavior, etc. So I'm putting a bunch of tickets into the "1.8" Milestone. I am not, however, at this time, volunteering to work on these tickets, so it might be a mistake to put them into the 1.8 Milestone, but I really hope that someone else will volunteer or that I will decide to do it myself. :-)

comment:4 Changed at 2010-08-10T04:09:11Z by davidsarah

  • Keywords mutable mapupdate ucwe added
  • Milestone changed from 1.8.0 to soon

comment:5 Changed at 2010-08-10T04:28:24Z by zooko

If you like this ticket, you might like #540 (inappropriate "uncoordinated write error" after handling a server failure).

Note: See TracTickets for help on using tickets.