English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This work is a continuation of efforts to define and understand competitiveanalysis of algorithms in a distributed shared memory setting, which issurprisingly different from the classical online setting. In fact, in adistributed shared memory setting, we find a counter-example to the theoremconcerning classical randomized online algorithms which shows that, if there isa $c$-competitive randomized algorithm against an adaptive offline adversary,then there is a $c$-competitive deterministic algorithm [Ben-David, Borodin,Karp, Tardos, Wigderson, 1994]. In a distributed setting, there is additionallack of knowledge concerning what the other processes have done. There is alsoadditional power for the adversary, having control of the scheduler whichdecides when each process is allowed to take steps.  We consider the list accessing problem, which is a benchmark problem forsequential online algorithms. In the distributed version of this problem, eachprocess has its own finite sequence of requests to a shared list. The schedulerarises as a major issue in its competitive analysis. We introduce two differentadversaries, which differ in how they are allowed to schedule processes, anduse them to perform competitive analysis of distributed list accessing. Weprove tight upper and lower bounds on combinatorial properties of merges of therequest sequences, which we use in the analysis. Our analysis shows that theeffects of the adversarial scheduler can be quite significant, dominating theusual quality loss due to lack of information about the future.

The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing