In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node. We prove that for every shortest path routing scheme, ...
详细信息
ISBN:
(纸本)9780897918008
In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node. We prove that for every shortest path routing scheme, for any constant Ε, 0
This paper is an answer to the question: 'What is unique and conceptually different about mobile computing?' The paper begins by describing a set of constraints intrinsic to mobile computing, and examining the...
详细信息
ISBN:
(纸本)9780897918008
This paper is an answer to the question: 'What is unique and conceptually different about mobile computing?' The paper begins by describing a set of constraints intrinsic to mobile computing, and examining the impact of these constraints on the design of distributed systems. Next, it summarizes the key results of the Coda and Odyssey systems. Finally, it describes the research opportunities in five important topics relevant to mobile computing: caching metrics, semantic callbacks and validators, resource revocation, analysis of adaptation, and global estimation from local observations.
We prove that the primary-partition group membership problem cannot be solved in asynchronous systems with crash failures, even if one allows the removal or killing of non-faulty processes that are erroneously suspect...
详细信息
We prove that the primary-partition group membership problem cannot be solved in asynchronous systems with crash failures, even if one allows the removal or killing of non-faulty processes that are erroneously suspected to have crashed.
This paper presents an indexed computation tree logic formula template that encodes under certain mild restrictions and provides a format for specifying safety and progress properties for the system as a whole. It the...
详细信息
ISBN:
(纸本)9780897918008
This paper presents an indexed computation tree logic formula template that encodes under certain mild restrictions and provides a format for specifying safety and progress properties for the system as a whole. It then presents a simple method of converting a synthesized finite-state model of such a formula into a message-passing controller and a communication protocol for its clients. Finally, it proves the correctness of the resulting distributed control system.
The proceedings contains 71 papers. Topics discussed include self stabilization algorithms, shared memory multiprocessors, message ordering, routing, random bit generators, random processes, real time object sharing, ...
详细信息
The proceedings contains 71 papers. Topics discussed include self stabilization algorithms, shared memory multiprocessors, message ordering, routing, random bit generators, random processes, real time object sharing, nonblocking and blocking algorithms, partitionable membership services, equivalence completions, and counting networks.
This paper studies the problem of making distributed decisions with the goal of maximizing a given utility function. The focus is entirely on the design and performance of the voting strategy and complete abstract fro...
详细信息
ISBN:
(纸本)9780897918008
This paper studies the problem of making distributed decisions with the goal of maximizing a given utility function. The focus is entirely on the design and performance of the voting strategy and complete abstract from implementational details, such as how ballots are collected from the voters and how the results of the election is communicated to the voters. The main interest is in giving a tight estimate of the cumulative profit achievable in a worst-case setting.
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.
Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are used for distributed and replicated databases, name servers, mutual exclusion, and di...
详细信息
Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are used for distributed and replicated databases, name servers, mutual exclusion, and distributed access control and signatures. Traditionally, two basic methods have used to evaluate quorum systems: the first is the analytical approach. The second approach is simulation. This paper proposes an empirical approach to evaluate systems. The results of the evaluation are presented.
This paper introduces two consistency criteria, causal consistency and causal serializability, in the context of systems composed of sequential processes that execute transactions. Causal consistency is the weaker cri...
详细信息
This paper introduces two consistency criteria, causal consistency and causal serializability, in the context of systems composed of sequential processes that execute transactions. Causal consistency is the weaker criterion: in addition to the sequentiality on transactions issued by each process, it considers only dependency on transactions due to a read-from relation. The second criterion, causal serializability, lies between causal consistency and serializability and is a consistency criterion strong enough to satisfy a wide range of applications.
暂无评论