We consider a generalization of the dining philosophers problem to arbitrary connection topologies. We focus on symmetric, fully distributed systems, and we address the problem of guaranteeing progress and lockout-fre...
详细信息
ISBN:
(纸本)9781581133837
We consider a generalization of the dining philosophers problem to arbitrary connection topologies. We focus on symmetric, fully distributed systems, and we address the problem of guaranteeing progress and lockout-freedom, even in presence of adversary schedulers, by using randomized algorithms. We show that the well-known algorithms of Lehmann and Rabin do not work in the generalized case, and we propose an alternative algorithm based on the idea of letting the philosophers assign a random priority to their adjacent forks.
作者：
Abadi, M.InterTrust
Strategic Technologies and Architectural Research Lab.
Since the 1970s, Leslie Lamport has done substantial work on specification and verification methods. This work might be regarded as complementary to his other celebrated research on concurrency and distributed computi...
详细信息
ISBN:
(纸本)9781581133837
Since the 1970s, Leslie Lamport has done substantial work on specification and verification methods. This work might be regarded as complementary to his other celebrated research on concurrency and distributedcomputing, perhaps sometimes even as secondary. However, this work is excellent in its own right. It introduces (or distills) many original and useful ideas. These include the important definitions of safety and liveness properties, and later the insightful conception of a temporal logic of actions. This talk will describe some of Lamport's ideas and results on specification and verification methods. It will touch on the impact of some of those ideas on the speaker (who collaborated closely with Lamport for several years) and on the field.
This paper presents a specification of a randomized shared queue that can lose some elements or return them out of order (not in FIFO), shows that the specification can be implemented over the probabilistic quorum alg...
详细信息
This paper presents a specification of a randomized shared queue that can lose some elements or return them out of order (not in FIFO), shows that the specification can be implemented over the probabilistic quorum algorithm of [4,3], and analyzes the behavior of this implementation. distributed algorithms that can tolerate some lost and out-of-order messages are candidates for replacing the message queues with random queues. The modified algorithms will inherit positive attributes concerning load and availability from the underlying queue implementation. The behavior of an application - a class of combinatorial optimization algorithms - when it is implemented using random queues is analyzed.
In this paper, we show the connection between vector clocks used in distributedcomputing and dimension theory of partially ordered sets. Based on this connection, we provide lower bounds on the number of coordinates ...
详细信息
ISBN:
(纸本)9781581133837
In this paper, we show the connection between vector clocks used in distributedcomputing and dimension theory of partially ordered sets. Based on this connection, we provide lower bounds on the number of coordinates for timestamping events in a distributed computation for capturing the happened-before relation. To this end, we introduce the notion of a string realizer and the string dimension of a poset. For distributedcomputing and other applications, the concept of string realizer is more natural than the chain realizer used in the classical dimension theory. We establish the relationship between the string dimension and the chain dimension of a poset. Using this relationship and Dilworth's theorem for the chain dimension of finite distributive lattices, we obtain the desired lower bound. The concept of strings also has applications in efficient encoding of partial orders because it requires fewer bits to encode a string realizer than a chain realizer.
Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures. However, this assumption limits their applicability. We present a methodology that, for a significa...
详细信息
ISBN:
(纸本)9781581133837
Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures. However, this assumption limits their applicability. We present a methodology that, for a significant class of data structures, allows designers to first tackle the easier problem of designing a garbage-collection-dependent implementation, and then apply our methodology to achieve a garbage-collection-independent one. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
The purpose of compact routing is to provide a labeling of the nodes of a network and a way to encode the routing tables, so that routing can be performed efficiently (e.g., on shortest paths) whilst keeping the memor...
详细信息
The purpose of compact routing is to provide a labeling of the nodes of a network and a way to encode the routing tables, so that routing can be performed efficiently (e.g., on shortest paths) whilst keeping the memory-space required to store the routing tables as small as possible, In this paper, we answer a long-standing conjecture by showing that compact routing may also assist in the performance of distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows broadcasting, with a message-complexity of O(n), where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving the previous known bound of O(m + n). A general consequence of our result is that a shortest path interval routing scheme contains ample structural information to avoid developing ad-hoe or network-specific solutions for basic problems that distributed systems must handle repeatedly.
The second edition of The Manual [23] begins: 'LATEX is a system for typesetting documents. Its first widely available version, mysteriously numbered 2.09, appeared in 1985.' It is too early for a complete cri...
详细信息
The second edition of The Manual [23] begins: 'LATEX is a system for typesetting documents. Its first widely available version, mysteriously numbered 2.09, appeared in 1985.' It is too early for a complete critical assessment of the impact of LATEX 2.09 because its world-wide effects on many aspects of many cultures, not least scientific publication, remain strong after 15 years - and that itself is significant in a technological world where a mere 15 months of fame can make and break an idea. Therefore this paper provides simply a review and evaluation of the relationship between TEX, LATEX and some of the major technical developments in the world of quality automated formatting since the publication of LATEX 2.09 in 1985. It is neither definitive nor comprehensive but I hope it is informative.
We describe a novel approach to log-based reconciliation called IceCube. It is general and is parameterised by application and object semantics. IceCube considers more flexible orderings and is designed to ease the bu...
详细信息
ISBN:
(纸本)9781581133837
We describe a novel approach to log-based reconciliation called IceCube. It is general and is parameterised by application and object semantics. IceCube considers more flexible orderings and is designed to ease the burden of reconciliation on the application programmers. IceCube captures the static and dynamic reconciliation constraints between all pairs of actions, proposes schedules that satisfy the static constraints, and validates them against the dynamic constraints. Preliminary experience indicates that strong static constraints successfully contain the potential combinatorial explosion of the simulation stage. With weaker static constraints, the system still finds good solutions in a reasonable time.
This paper discusses the probe complexity of randomized algorithms and the deterministic average case probe complexity for some classes of non-dominated coteries, including majority, crumbling walls, tree, wheel and h...
详细信息
ISBN:
(纸本)9781581133837
This paper discusses the probe complexity of randomized algorithms and the deterministic average case probe complexity for some classes of non-dominated coteries, including majority, crumbling walls, tree, wheel and hierarchical quorum systems, and presents upper and lower bounds for the probe complexity of quorum systems in these classes.
The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributedcomputing. If the tasks are similar and independent and the processors communic...
详细信息
ISBN:
(纸本)9781581133837
The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributedcomputing. If the tasks are similar and independent and the processors communicate by sending messages then the problem is called Do-All. In our work the communication is over a multiple-access channel, and the attached stations may fail by crashing. The measure of performance is work, defined as the number of the available processor steps. Algorithms are required to be reliable in that they perform all the tasks as long as at least one station remains operational. We show that each reliable algorithm always needs to perform at least the minimum amount Ω(t+p√t) of work. We develop an optimal deterministic algorithm for the channel with collision detection performing only the minimum work Θ(t+p√t). Another algorithm is given for the channel without collision detection, it performs work O(t+p√t+p · min{f,t}), where f
暂无评论