The most significant strategic development in information technology over the past year has been 'trusted computing'. This is popularly associated with Microsoft's 'Palladium' project, recently ren...
详细信息
The most significant strategic development in information technology over the past year has been 'trusted computing'. This is popularly associated with Microsoft's 'Palladium' project, recently renamed 'NGSCB'. In this paper, I give an outline of the technical aspects of 'trusted computing' and sketch some of the public policy consequences.
The latest specifications for dynamic group communication in a distributed system are discussed. The reliable broadcast in a dynamic system is called reliable multicast, which is defined by the two primitives rmultica...
详细信息
The latest specifications for dynamic group communication in a distributed system are discussed. The reliable broadcast in a dynamic system is called reliable multicast, which is defined by the two primitives rmulticast and rdeliver. The properties of the reliable multicast include validity, uniform agreement, uniform integrity and uniform same view delivery. For the validity property, if a correct process executes rmulticast(m), then it eventually rdelivers m.
The notions of refinement for branching time based on stuttering simulation and bisimulation are developed. A local proof rule called well-founded simulation is introduced. It is shown that if one system refines anoth...
详细信息
The notions of refinement for branching time based on stuttering simulation and bisimulation are developed. A local proof rule called well-founded simulation is introduced. It is shown that if one system refines another, then a refinement map always exists. The added generality is obtained by using relations to relate implementation states with specification states and by requiring the use of well-founded relations.
The extension of Structured Query Language (SQL) access control approaches in deriving data from distributed systems was discussed. The three component features of the discussed SQL model included: applicability of de...
详细信息
The extension of Structured Query Language (SQL) access control approaches in deriving data from distributed systems was discussed. The three component features of the discussed SQL model included: applicability of derived object concept in any architecture;privileges usable only within a particular derivation;and the use of factored privileges in modeling different execution concerns. The stated features were combined in representing the policies specifiable in researchers' models. The use of the three components of the model in exporting the data of a national network of hospitals to a data warehouse was discussed.
Routing topologies for distributed hashing in peer-to-peer networks are classified into two categories: deterministic and randomized. A general technique for constructing deterministic routing topologies is presented....
详细信息
ISBN:
(纸本)9781581137088
Routing topologies for distributed hashing in peer-to-peer networks are classified into two categories: deterministic and randomized. A general technique for constructing deterministic routing topologies is presented. Using this technique, classical parallel interconnection networks can be adapted to handle the dynamic nature of participants in peer-to-peer networks. A unified picture of randomized routing topologies is also presented. Two new protocols are described which improve average latency as a function of out-degree. One of the protocols can be shown to be optimal with high probability. Finally, routing networks for distributed hashing are revisited from a systems perspective and several open design problems are listed.
This paper presents a general methodology for building message-passing peer-to-peer systems capable of performing prefix search for arbitrary user-defined names. Our methodology allows to achieve even load distributio...
详细信息
ISBN:
(纸本)9781581137088
This paper presents a general methodology for building message-passing peer-to-peer systems capable of performing prefix search for arbitrary user-defined names. Our methodology allows to achieve even load distribution, high fault-tolerance, and low-congestion concurrent query execution. This is the first known peer-to-peer system for prefix search with such properties. The essence of this methodology is a plug and play paradigm for designing a peer-to-peer system as a modular composition of arbitrary concurrent data structures.
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.
The distinction between safety and liveness properties is due to Lamport who gave the following informal characterization. Safety properties assert that nothing bad ever happens while liveness properties assert that s...
详细信息
ISBN:
(纸本)9781581137088
The distinction between safety and liveness properties is due to Lamport who gave the following informal characterization. Safety properties assert that nothing bad ever happens while liveness properties assert that something good happens eventually. In a well-known paper Alpern and Schneider gave a topological characterization of safety and liveness for the linear time framework. Gumm has stated these notions in the more abstract setting of V-complete Boolean algebras. Recently, we characterized safety and liveness for the branching time framework and found that neither the topological characterization nor Gumm's characterization were general enough for our needs. We present a lattice-theoretic characterization that allows us to unify previous results on safety and liveness, including the results for the linear time and branching time frameworks and for ω-regular string and tree languages.
In this paper we consider the following two variants of the consensus problem. First, the strong consensus problem, where n players attempt to reach agreement on a value initially held by one of the correct players, d...
详细信息
ISBN:
(纸本)9781581137088
In this paper we consider the following two variants of the consensus problem. First, the strong consensus problem, where n players attempt to reach agreement on a value initially held by one of the correct players, despite the (malicious) behavior of up to t of them. (Recall that in the standard version of the problem, the players are also required to decide on one of the correct players' input values, but only when they all start with the same value;otherwise, they can decide on a default.) Although the problem is closely related to the standard problem, the only known solution with the optimal number of players requires exponential computation and communication in the unconditional setting. Even though the decision would be a value originally held by a correct player, strong consensus allows for a decision value that is the least common among the correct players. We also formulate the δ-differential consensus problem, which specifies that the value agreed on must be of a certain plurality among the correct players - specifically, that the plurality of any other value cannot exceed the plurality of the decision value by more than δ. In this paper we study these problems, and present efficient protocols and tight lower bounds for several standard distributed computation models - unconditional, computational, synchronous, and asynchronous.
Consider a dynamic, large-scale communication infrastructure (e.g., the Internet) where nodes (e.g., in a peer to peer system) can communicate only with nodes whose id (e.g., IP address) are known to them. One of the ...
详细信息
ISBN:
(纸本)9781581137088
Consider a dynamic, large-scale communication infrastructure (e.g., the Internet) where nodes (e.g., in a peer to peer system) can communicate only with nodes whose id (e.g., IP address) are known to them. One of the basic building blocks of such a distributed system is resource discovery efficiently discovering the ids of the nodes that currently exist in the system. We present both upper and lower bounds for the resource discovery problem. For the original problem raised by Harchol-Balter, Leighton, and Lewin we present an ω(n log n) message complexity lower bound for asynchronous networks whose size is unknown. For this model, we give an asymptotically message optimal algorithm that improves the bit complexity of Kutten and Peleg. When each node knows the size of its connected component, we provide a novel and highly efficient algorithm with near linear O(nα(n, n)) message complexity (where α is the inverse of Ackerman's function). In addition, we define and study the Ad-hoc Resource Discovery Problem, which is a practical relaxation of the original problem. Our algorithm for ad-hoc resource discovery has near linear O(nα(n, n)) message complexity. The algorithm efficiently deals with dynamic node additions to the system, thus addressing an open question of [3], We present a ω(nα(n, n)) lower bound for the Ad-hoc Resource Discovery Problem, showing that our algorithm is asymptotically message optimal.
暂无评论