Bug in calculation of quorum duration - has_quorum_at_time doesn't consider stale_limit

[ghost]

The current client_policy.js for inspection with additional comments:

get_quorum_duration : function(test_key, results, quorum_size, stale_limit_secs, unixtime) {
    if(quorum_size < 1) {
        return 0;
    }

    // do a pre-check if the quorum can at least be reached with the most recent keys without considering a duration
    if(!Pers_client_policy.check_current_consistency(test_key, results, quorum_size, stale_limit_secs, unixtime)) {
        return -1;
    }

    // get all time changes (list of timestamp.start and timestamp.end) and sort them in descending order
    var time_changes       = Pers_client_policy.get_all_key_changes(results);
    Pers_client_policy.sort_number_list_desc(time_changes);

    // oldest by timestamp.end and non-stale
    var oldest_most_recent = Pers_client_policy.find_oldest_most_recent(results, stale_limit_secs, unixtime);

    var test_time          = null;
    var oldest_valid_ts    = unixtime;
    for(var i = 0; i < time_changes.length; i++) {
        test_time = time_changes[i];
        // skip all newer timestamps. a quorum should exist (see pre-check) thus
        // the duration it is atleast unixtime - oldest_most_recent long
        if(time_changes[i] > oldest_most_recent) {
            continue;
        }
        // this is false the first time (see pre-check)
        // note that the function doesn't consider the stale_limit(!)
        if(!Pers_client_policy.has_quorum_at_time(test_key, results, quorum_size, test_time)) {
            break;
        }
        oldest_valid_ts = test_time;
    }
    if(oldest_valid_ts === null) {
        return 0;
    }
    var diff = unixtime - oldest_valid_ts + 1;
    return (diff > 0) ? diff : 0;
},

Bug: Quorum duration grows indefinitely as long as the quorum size is reached at each test time. (because the stale_limit is ignored).

Situation:

This is a ASCII-art of a time graph and notary results. |---| are keys. ^ displays the quorum duration. Also note that the past is on the left as opposed to Perspectives history graph.

              stale limit   now (unixtime = 100)
                   .         .
result0:        |--+--|      .
result1:    |------+------|  .
result2:  |---|    .         .

     <-- 098765432109876543210 [seconds]
        -20 ^     -10        0

var unixtime         = 100;
var quorum_size      =   2;
var stale_limit_secs =  10;
var key = "key";

var results = 
[ { "server": "0", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 13, "end": unixtime -  7 } ] } ] }
, { "server": "1", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 17, "end": unixtime -  3 } ] } ] }
, { "server": "2", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 19, "end": unixtime - 15 } ] } ] }
];

Pers_client_policy.get_quorum_duration(key, results, quorum_size, stale_limit_secs, unixtime);

Result : 18 Expected: much less

Problem: Because has_quorum_at_time doesn't check for stale_limit (see code above) the quorum size is true for the set (result0, result1). But it's true again for a different set (result1, result2) although test_time passed beyond stale_limit. This could go on indefinitely if there were more results with this property.

Ambigious quorum duration issues The following issues are not an actual bug but I think it's also ambigious what should actually be included in the quorum duration. At least it goes against intuition.

Situation:

              stale limit   now (unixtime = 100)
                   .         .
result0:        |--+----|    .
result1:        |--+-------| .
result2:  |---|    .         .

     <-- 098765432109876543210 [seconds]
        -20     ^ -10        0

var results = 
[ { "server": "0", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 13, "end": unixtime -  5 } ] } ] }
, { "server": "1", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 13, "end": unixtime -  2 } ] } ] }
, { "server": "2", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 19, "end": unixtime - 15 } ] } ] }
];

Pers_client_policy.get_quorum_duration(key, results, quorum_size, stale_limit_secs, unixtime);

Result: 14

But why should the quorum duration not...

1. start earliest at stale_limit? (100 - 90 + 1 = 11)
2. only make up the actual overlap (union) between timespans? (95 - 87 + 1 = 9)
3. extend towards now considering there are no actual timestamps there? (98 - 87 + 1 = 12)

Putting it all together it would shrink to 90 - 95 + 1 = 6 :)

Question 3 is again contradictory to the following.

Bug: Quorum duration is just 1 in the following condition

Situation:

              stale limit   now (unixtime = 100)
                   .         .
result0:        |--+--|      .
result1:           .    |---|.
result2:  |---|    .         .

     <-- 098765432109876543210 [seconds]
        -20       -10   ^    0

var results = 
[ { "server": "0", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 13, "end": unixtime -  7 } ] } ] }
, { "server": "1", "obs": [ { "key": key, "timestamps": [ { "start": unixtime -  5, "end": unixtime -  1 } ] } ] }
, { "server": "2", "obs": [ { "key": key, "timestamps": [ { "start": unixtime - 19, "end": unixtime - 15 } ] } ] }
];

Result: Just 1(!)

Problem: In this situation the results pass the pre-check because two of the most recent keys are non-stale (result0, result1) and thus reach the quorum size. Because there is no actual overlap the for-loop in get_quorum_duration() breaks, oldest_valid_ts is still unixtime and the result is 1. But if in the successful case above the quorum duration extends to now there should be a virtual overlap if the most recent non-stale keys are extended to now.

              stale limit   now (unixtime = 100)
                   .         .
result0:        |--+---......|
result1:           .    |---.|
result2:  |---|    .         .
                        ^

[ghost]

Related to #129