This paper is a summary of an invited talk presented at the 12th acmsymposium on principles of distributedcomputing in August 1993. The talk gave a brief introduction to the Ubiquitious computing vision, described s...
详细信息
Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient, faults that alter their memory in air arbitrary fashion. Within the c...
详细信息
ISBN:
(纸本)9781595939890
Consider a distributed network in which up to a third of the nodes may be Byzantine, and in which the non-faulty nodes may be subject to transient, faults that alter their memory in air arbitrary fashion. Within the context of this model. we are interested in the digital clock synchronization problem;which consists of agreeing oil bounded integer counters, and increasing these counters regularly. It has been postulated in the past that, synchronization cannot be solved in a Byzantine tolerant and self-stabilizing first. solution to this problem tu had an expected manner. exponential convergence time. Later, a deterministic solution was, published with linear convergence time, which is optimal for deterministic solutions. In the current paper we achieve an expected constant convergence time. We thus obtain the optimal probabilistic solution, both in terms of convergence time and in terms of resilience to Byzantine adversaries.
This paper summarizes a talk given at the Twelfth annualacmsymposium on distributedcomputing. It presents a perspective on the evolving National Information Infrastructure, focussing on some of the multimedia appli...
详细信息
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.
The proceedings contain 39 papers from the proceedings of the 23rd annualacmsymposium on principles of distributedcomputing. The topics discussed include: completely fair SFE and coalition-safe cheap talk;mechanism...
详细信息
The proceedings contain 39 papers from the proceedings of the 23rd annualacmsymposium on principles of distributedcomputing. The topics discussed include: completely fair SFE and coalition-safe cheap talk;mechanism design for policy routing;selfish caching in distributed systems: a game-theoretic analysis;bringing practical lock-free synchronization to 64-bit applications;an almost non-blocking stack and lock-free linked lists and skip lists.
The problem of designing a server subsystem in an application allowing an arbitrary large number of geographically dispersed clients to remotely access the server to which they are connected through a network is addre...
详细信息
The problem of designing a server subsystem in an application allowing an arbitrary large number of geographically dispersed clients to remotely access the server to which they are connected through a network is addressed. Two results are discussed. The first one is a Σ-ordering protocol, built above an Ordered Timed Atomic Broadcast protocol (OTAB) implemented on top of the TMR subsystem. The second result is an impossibility theorem: "Let-Δ be the minimum timeliness of any reliable broadcast protocol implemented on top of the TM server. If ΣΔ, then there is no Σ-ordering protocol".
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.
暂无评论