检索结果-内蒙古大学图书馆

Optimal, distributed decision-making: The case of no communication 12th

12th International symposium on Fundamentals of Computation Theory

作者： Georgiades, S Mavronicolas, M Spirakis, P Univ Cyprus Dept Comp Sci CY-1678 Nicosia Cyprus Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA AT&T Labs Res Murray Hill NJ 07974 USA Univ Patras Dept Comp Engn & Informat Patras Greece Inst Comp Technol Patras Greece

ISBN: (纸本)3540664122

We present a combinatorial framework;for the study of a natural class of distributed optimization problems that involve decisionmaking by a collection of n distributed agents in the presence of incomplete information;such problems were originally considered in a load balancing setting by Papadimitriou and Yannakakis (proceedings of the 10th annual acm symposium on principles of distributed computing, pp. 61-64, August 1991). For any given decision protocol and assuming no communication among the agents, our framework allows to obtain a combinatorial inclusion-exclusion expression for the probability that no "overflow" occurs, called the winning probability, in terms of the volume of some simple combinatorial polytope. Within our general framework, we offer a complete resolution to the special cases of oblivious algorithms, for which agents do not "look at" their inputs, and non-oblivious algorithms, for which they do, of the general optimization problem. In either case, we derive optimality conditions in the form of combinatorial polynomial equations. For oblivious algorithms, we explicitly solve these equations to show that the optimal algorithm is simple and uniform, in the sense that agents need not "know" n. Most interestingly, we shaw that optimal non-oblivious algorithms must be non-uniform: we demonstrate that the optimality conditions admit different solutions for particular, different "small" values of n;however, these solutions improve in terms of the winning probability over the optimal, oblivious algorithm. Our results demonstrate an interesting tradeoff between the amount of knowledge used by agents and uniformity for optimal, distributed decision-making with no communication.

关键词： Decision making

来源：评论

学校读者我要写书评

暂无评论

Optimal and efficient clock synchronization under drifting clocks

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 3-12页

作者： Ostrovsky, Rafail Patt-Shamir, Boaz Bellcore Morristown NJ United States

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are non-drifting, i.e., only for systems where all clocks advance at the rate of real time. In this paper, we present a new algorithm for systems with drifting clocks, which is the first optimal algorithm to solve the problem efficiently: clock drift bounds and message latency bounds may be arbitrary;the computational complexity depends on the communication pattern of the system in a way which is bounded by a polynomial in the network size for most systems. More specifically, the complexity is polynomial in the maximal number of messages known to be sent but not received, the relative system speed, and time-stamp size. Our result has two consequences. From the theoretical standpoint, it refines the known bounds for optimal synchronization. But even more importantly, it enables us to derive new optimal algorithms that are reasonably efficient for most practical systems.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Resource discovery in distributed networks

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 229-237页

作者： Harchol-Balter, Mor Leighton, Tom Lewin, Daniel MIT Lab for Computer Science Cambridge MA United States

In large distributed networks of computers, it is often the case that a subset of machines wants to cooperate to perform a task. Before they can do so, these machines need to learn of the existence of each other. In this paper we are interested in distributed algorithms whereby machines in a network learn of other machines in the network by making queries to machines they already know. The algorithms should be efficient both in terms of the time required and in terms of the total network communication required until all machines have discovered all other machines. We propose a very simple algorithm called Name-Dropper whereby all machines learn about each other within O(log2 n) rounds with high probability, where n is the number of machines in the network. The total number of connections required is O(n log2 n) and the total number of pointers which must be communicated is O(n2 log2 n), with high probability. Each of the preceding bounds is optimal to within polylogarithmic factors.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

LOTEC: A simple DSM consistency protocol for nested object transactions

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 153-162页

作者： Graham, Peter Sui, Yahong Univ of Manitoba Winnipeg Canada

In this paper, we describe an efficient software-only distributed Shared Memory (DSM) consistency protocol for an unconventional but important application domain - object transactional processing. Designers of transactional applications, while sensitive to performance issues, already accept significant overhead for the added functionality provided by transactions and, we speculate, would be willing to accept some small additional overhead for the benefit of `easy' distributed parallel execution. This is in contrast to the performance critical needs of the high-end scientific applications typically targetted by DSM system designers. While, after 10 years of performance enhancement, software DSMs are still considered inadequate by a large part of the parallel computing community, we believe they are now more than sufficiently mature to support distributed transactional environments. The key to making DSM attractive to the developers of transactional applications is ease of use. The much touted simplification offered by the use of shared memory instead of message passing is not enough. It must be possible to hide the needed synchronization operations from the programmer. To achieve this goal, we have developed a system for nested object transactions that supports the automatic insertion of synchronization primitives. These primitives are then used to drive the operation of an improved form of Bershad's Entry Consistency (EC) protocol to maintain memory consistency between the processors/nodes in a distributed computing system. The protocol described is also compatible with a number of performance enhancements for DSM systems that have been described in the literature.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Simple local-spin group mutual exclusion algorithm

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 23-32页

作者： Keane, Patrick Moir, Mark Univ of Pittsburgh Pittsburgh United States

This paper presents a new solution to the group mutual exclusion problem, recently posed by Joung. In this problem, processes repeatedly request access to various `sessions'. It is required that distinct processes are not in different sessions concurrently, that multiple processes may be in the same session concurrently, and that each process that tries to enter a session is eventually able to do so. This problem is a generalization of the mutual exclusion and readers-writers problems. Our algorithm and its correctness proof are substantially simpler than Joung's. This simplicity is achieved in part by building upon known solutions to the more specific mutual exclusion problem. Our algorithm also has various advantages over Joung's, depending on the choice of mutual exclusion algorithm used. These advantages include admitting a process to its session in constant time in the absence of contention, spinning locally in Cache Coherent (CC) and Non-Uniform Memory Access (NUMA) systems, and improvements in the complexity measures proposed by Joung.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Backward consistency and sense of direction in advanced distributed systems

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 189-198页

作者： Flocchini, Paola Roncato, Alessandro Santoro, Nicola Universite du Quebec a Hull Hull Que Canada

The studies on the relationship between label consistency, computability and complexity assume the existence of local orientation;this assumption is in fact at the basis of the point-to-point model and is realistic for systems where a communication link can connect only two entities. However, in systems which use more advanced communication and interconnection technology such as buses, optical networks, wireless communication media, etc., and more importantly, heterogeneous systems (such as internet) which include any combination of the above, local orientation can not be assumed. In this paper we consider a new type of consistency which we shall call backward consistency and which, unlike sense of direction, can exist even without local orientation. Thus, unlike all previous forms of consistency, it can be found (or designed) in advanced distributed systems. We study backward consistency both in terms of its relationship with the traditional properties of local orientation and (weak) sense of direction, and with respect to symmetries of the edge labelings and of the naming functions. We prove that backward consistency is computationally equivalent to sense of direction;in other words, it is possible to take advantage of the computational power of sense of direction even in absence of local orientation.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

On k-set consensus problems in asynchronous systems

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 257-265页

作者： De Prisco, Roberto Malkhi, Dahlia Reiter, Michael K. MIT Lab for Computer Science Cambridge MA United States

In this paper we investigate the k-set consensus problem in asynchronous, message-passing distributed systems. In this problem, each participating process begins the protocol with an input value and by the end of the protocol must decide on one value so that at most k different values are decided by all correct processes. We extend previous work by exploring several variations of the problem definition and model, including for the first time investigation of Byzantine failures. We show that the precise definition of the validity requirement, which characterizes what decision values are allowed as a function of the input values and whether failures occur, is crucial to the solvability of the problem. For example, we show that allowing default decisions in case of failures makes the problem solvable for most values of k despite a minority of failures, even for the most severe type of failures (Byzantine). We introduce six validity conditions for this problem (all considered in various contexts in the literature), and demarcate the line between possible and impossible for each case. In many cases this line is different from the one of the originally studied k-set consensus problem.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Matching events in a content-based subscription system

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 53-60页

作者： Aguilera, Marcos K. Strom, Robert E. Sturman, Daniel C. Astley, Mark Chandra, Tushar D. Cornell Univ Ithaca United States

Content-based subscription systems are an emerging alternative to traditional publish-subscribe systems, because they permit more flexible subscriptions along multiple dimensions. In these systems, each subscription is a predicate which may test arbitrary attributes within an event. However, the matching problem for content-based systems - determining for each event the subset of all subscriptions whose predicates match the event - is still an open problem. We present an efficient, scalable solution to the matching problem. Our solution has an expected time complexity that is sub-linear in the number of subscriptions, and it has a space complexity that is linear. Specifically, we prove that for predicates reducible to conjunctions of elementary tests, the expected time to match a random event is no greater than O(N1-λ) where N is the number of subscriptions, and λ is a closed-form expression that depends on the number and type of attributes (in some cases, λ1/2). We present some optimizations to our algorithms that improve the search time. We also present the results of simulations that validate the theoretical bounds and that show acceptable performance levels for tens of thousands of subscriptions.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Decentralized replicated-object protocols

Proceedings of the Annual ACM Symposium on Principles of Dis...

引用

proceedings of the annual acm symposium on principles of distributed computing 1999年 143-151页

作者： Keleher, Peter J. Univ of Maryland College Park MD United States

We describe a new replicated-object protocol designed for use in mobile and weakly-connected environments. The protocol differs from previous protocols in combining epidemic information propagation with voting, and in using fixed per-object currencies for voting. The advantage of epidemic protocols is that data movement only requires pairwise communication. Hence, there is no need for a majority quorum to be available and simultaneously connected at any single time. The protocols increase availability by using voting, rather than primary copy or primary commit schemes. Finally, the use of per-object voting currencies allows votes to take place in an entirely decentralized fashion, without any server having complete knowledge of group membership. We show that currency allocation can be used to implement diverse policies. For example, uniform currency distributions emulate traditional dynamic voting schemes, while allocating all currency to a single server emulates a primary-copy scheme. We present simulation results showing both schemes, as well as the performance advantages of using currency proxies to temporarily reallocate currency during planned disconnections.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Timed consistency for shared distributed objects 99

Timed consistency for shared distributed objects

引用

proceedings of the eighteenth annual acm symposium on principles of distributed computing

作者： Francisco J. Torres-Rojas Mustaque Ahamad Michel Raynal College of Computing Georgia Institute of Technology IRISA University of Rennes France

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：