This paper presents two basic building blocks in an asynchronous environment, one in the shared-memory model and one in the message-passing model, that help to translate algorithms between the two models. These buildi...
详细信息
ISBN:
(纸本)0897913264
This paper presents two basic building blocks in an asynchronous environment, one in the shared-memory model and one in the message-passing model, that help to translate algorithms between the two models. These building blocks are equivalent in the following sense: given an algorithm in one model that utilises its appropriate building block, we are able to construct an algorithm in the other model that utilizes the equivalent building block. We demonstrate this idea by two applications. First, we solve the processor renaming problems in the shared-memory model based on the solutions of in the message-passing model. The solution is deterministic wait-free and employs atomic read and write registers. Second, we provide a randomized algorithm for flipping a biased global coin in the message-passing model based on an algorithm in the shared-memory model. Using this coin, we achieve the 'fastest' randomized algorithm solving the consensus problem against the strongest adversary with one half resilience.
Various distributed algorithms are presented, that allow nodes in a distributed system to recover from crash failures efficiently. The algorithms are independent of the application programs running on the nodes. The a...
详细信息
ISBN:
(纸本)0897913264
Various distributed algorithms are presented, that allow nodes in a distributed system to recover from crash failures efficiently. The algorithms are independent of the application programs running on the nodes. The algorithms log messages and checkpoint states of the processes to stable storage at each node. Both logging of messages and checkpointing of process states can be done asynchronously with the execution of the application. Upon restarting after a failure, a node initiates a procedure in which the nodes use the logs and checkpoints on stable storage to roll back to earlier local states, such that the resulting global state is maximal and consistent. The first algorithm requires adding extra information of size O(n) to each application message (where n is the number of nodes);for each failure, O(n2) messages are exchanged, but no node rolls back more than once. The second algorithm only requires extra information of size O(1) on each application message, but requires O(n3) messages per failure. Both the above algorithms require that each process should be able to send messages to each of the other processes. We also present algorithms for recovery on networks, in which each process only communicates with its neighbors. Finally, we show how to decompose large networks into smaller networks so that each of the smaller network can use a different recovery procedure.
Let f(x1, ..., xn) be computed by a circuit C with bounded fanin. There are non-cryptographic protocols by which a network of n processors can evaluate C at secret inputs x1, ..., xn, revealing the final value f(x1, ....
详细信息
ISBN:
(纸本)0897913264
Let f(x1, ..., xn) be computed by a circuit C with bounded fanin. There are non-cryptographic protocols by which a network of n processors can evaluate C at secret inputs x1, ..., xn, revealing the final value f(x1, ..., xn) without revealing any information about the inputs except what the final result provides. Current methods require O(depth(C)) rounds of communication and messages of size polynomial in size(C) and n. In practical terms, such a degree of interaction is unacceptable. We show how to secretly evaluate any finite function in a constant expected number of rounds, regardless of the minimal depth of a circuit for that function. We provide a means to simulate unbounded fanin multiplicative (or AND) gates using constant rounds. Using our new methods, any function can be evaluated in a constant number of rounds, using messages of size proportional to the size of a constant-depth, unbounded-fanin circuit describing the function. We also show how to secretly evaluate any function described by an algebraic formula of polynomial size (or an NC1 circuit), using a constant number of rounds yet requiring messages of only polynomial size. This provides a speedup over original methods by a factor of log n, while incurring only a polynomial number of bits.
The proceedings contain 21 papers. The topics discussed include: viewstamped replication: a new primary copy method to support highly-available distributed systems;DCF: distributed communication with fault tolerance;o...
ISBN:
(纸本)0897912772
The proceedings contain 21 papers. The topics discussed include: viewstamped replication: a new primary copy method to support highly-available distributed systems;DCF: distributed communication with fault tolerance;one-bit algorithms;the power of multimedia: combining point-to-point and multiaccess networks;recovery in distributed systems using optimistic message logging and checkpointing;the data link layer: two impossibility results;improved algorithms for distributed resource allocation;end-to-end communication in unreliable networks;the cost of messages;a lattice-structured proof technique applied to a minimum spanning tree algorithm;computing on anonymous networks;understanding and verifying distributed algorithms using stratified decomposition;detecting stable properties of networks in concurrent logic programming languages;concurrent common knowledge: a new definition of agreement for asynchronous systems;secure and verifiable schemes for election and general distributedcomputing problems;process semantics: global axioms, compositional rules, and applications;the global time assumption and semantics for concurrent systems;and a combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor.
Chor, Israeli and Li recently published three randomized algorithms for a version of the consensus problem for a shared memory model of distributedcomputing. Their model requires, as atomic instructions on the shared...
详细信息
A network consists of a set of processors and a set of communication links connecting pairs of processors. In the past, dozens of papers have been written on the subject of efficient distributed algorithms for various...
详细信息
We describe a relatively simple fault tolerant distributed directory and communication service providing both connectionless and session services between applications that conform to a client server model. The directo...
详细信息
暂无评论