Zobrazeno 1 - 10
of 131
pro vyhledávání: '"Ellen, Faith"'
Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of
Externí odkaz:
http://arxiv.org/abs/2103.08949
Publikováno v:
In Theoretical Computer Science 28 February 2023 948
We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impo
Externí odkaz:
http://arxiv.org/abs/1811.01421
This work is a continuation of efforts to define and understand competitive analysis of algorithms in a distributed shared memory setting, which is surprisingly different from the classical online setting. In fact, in a distributed shared memory sett
Externí odkaz:
http://arxiv.org/abs/1807.06820
We describe a general technique for obtaining provably correct, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to children. Updates are permitted to modify any contiguous portion of the
Externí odkaz:
http://arxiv.org/abs/1712.06687
We define a new set of primitive operations that greatly simplify the implementation of non-blocking data structures in asynchronous shared-memory systems. The new operations operate on a set of Data-records, each of which contains multiple fields. T
Externí odkaz:
http://arxiv.org/abs/1712.06688
Determining the space complexity of $x$-obstruction-free $k$-set agreement for $x\leq k$ is an open problem. In $x$-obstruction-free protocols, processes are required to return in executions where at most $x$ processes take steps. The best known uppe
Externí odkaz:
http://arxiv.org/abs/1711.02455
Broadcast is one of the fundamental network communication primitives. One node of a network, called the $\mathit{source}$, has a message that has to be learned by all other nodes. We consider the feasibility of deterministic broadcast in radio networ
Externí odkaz:
http://arxiv.org/abs/1710.03178
Simulating a shared register can mask the intricacies of designing algorithms for asynchronous message-passing systems subject to crash failures, since it allows them to run algorithms designed for the simpler shared-memory model. Typically such simu
Externí odkaz:
http://arxiv.org/abs/1708.03274