This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simula...
详细信息
ISBN:
(纸本)0897914953
This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.
distributed consensus can be achieved on asynchronous communication networks when assisted by quantum mechanics. This contradicts the FLP impossibility result by achieving consensus in the presence of faults.
ISBN:
(纸本)9781595939890
distributed consensus can be achieved on asynchronous communication networks when assisted by quantum mechanics. This contradicts the FLP impossibility result by achieving consensus in the presence of faults.
This paper presents an efficient asynchronous protocol to compute RSA inverses with respect to a public RSA modulus N whose factorization is secret and shared among a group of parties. Given two numbers x and e, the p...
详细信息
ISBN:
(纸本)9781581137088
This paper presents an efficient asynchronous protocol to compute RSA inverses with respect to a public RSA modulus N whose factorization is secret and shared among a group of parties. Given two numbers x and e, the protocol computes y such that ye ≡ x (mod N). A synchronous protocol for this task has been presented by Catalano, Gennaro, and Halevi (Eurocrypt 2000), but the standard approach for turning this into an asynchronous protocol would require a Byzantine-agreement sub-protocol. Our protocol adopts their approach, but exploits a feature of the problem in order to avoid the use of a Byzantine agreement primitive. Hence, it leads to efficient asynchronous protocols for threshold signatures and for Byzantine agreement based on the strong RSA assumption, without the use of random oracles.
In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree problems that achieved optimal time and message complexity through the introduction of several advanced fea...
详细信息
ISBN:
(纸本)9780897917100
In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm.
distributed problems that can be solved with so-called k-ftss protocols that combine two types of failure resilience: k-fault-tolerance (k-ft) and self-stabilization (ss) is investigated. The protocol guarantees that,...
详细信息
ISBN:
(纸本)9780897919524
distributed problems that can be solved with so-called k-ftss protocols that combine two types of failure resilience: k-fault-tolerance (k-ft) and self-stabilization (ss) is investigated. The protocol guarantees that, whether the network is a ring or a descending order of identifiers. Once stabilized, the correct processes do not change their solutions even if a crash fault breaks the ring to a line.
The existing analyses of distributed Shared Memory (DSM) consistency conditions is extended by investigating achievable levels of fault tolerance. It is shown that in many cases there is a tradeoff - increasing the re...
详细信息
ISBN:
(纸本)9780897919524
The existing analyses of distributed Shared Memory (DSM) consistency conditions is extended by investigating achievable levels of fault tolerance. It is shown that in many cases there is a tradeoff - increasing the resilience of one operation necessitates a decrease in the resilience of the other. This result implies that, in practice, it may be possible to increase the resilience of critical or oft-used operations at the expense of other operations.
Recently, a new paradigm was proposed in which synchronization is accomplished by linking independent read and write operations separated by an arbitrary computation. The linking is such that the write operation will ...
详细信息
ISBN:
(纸本)9780897918008
Recently, a new paradigm was proposed in which synchronization is accomplished by linking independent read and write operations separated by an arbitrary computation. The linking is such that the write operation will succeed only if the shared memory has not been modified since the read. This is called transactional synchronization. With transactional synchronization, any RMW primitive using optimal time and space can be simulated.
暂无评论