On Wed, Dec 7, 2016 at 5:17 PM, Masahiko Sawada <sawada.mshk@gmail.com> wrote:
> On Wed, Dec 7, 2016 at 4:05 PM, Michael Paquier
> <michael.paquier@gmail.com> wrote:
>> Indeed, I haven't thought about that, and that's a no-brainer. That
>> would remove the need to allocate and sort each array, what is simply
>> needed is to track the number of times a newest value has been found.
>> So what this processing would do is updating the write/flush/apply
>> values for the first k loops if the new value is *older* than the
>> current one, where k is the quorum number, and between k+1 and N the
>> value gets updated only if the value compared is newer. No need to
>> take the mutex lock for a long time as well.
>
> Sorry, I could not understand this algorithm. Could you elaborate
> this? It takes only O(n) times?
Nah, please forget that, that was a random useless thought. There is
no way to be able to select the k-th element without knowing the
hierarchy induced by the others, which is what the partial sort would
help with here.
--
Michael