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

Localized client-server load balancing without global information

SIAM JOURNAL ON computing 2007年第4期37卷 1259-1279页

作者： Awerbuch, Baruch Hajiaghayi, Mohammad T. Kleinberg, Robert Leighton, Tom Johns Hopkins Univ Ctr Networking & Distibruted Syst Baltimore MD 21218 USA MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Cornell Univ Dept Comp Sci Ithaca NY 14850 USA MIT Dept Math & Comp Sci Cambridge MA 02139 USA MIT Artificial Intelligence Lab Cambridge MA 02139 USA

We consider distributed algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. We seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. Our problem is analogous to recent work on oblivious routing [ M. Bienkowski, M. Korzeniowski, and H. Racke, proceedings of the 15th Annual acm symposium on Parallel Algorithms and Architectures, 2003, pp. 24-33, C. Harrelson, K. Hildrum, and S. Rao, proceedings of the 15th Annual acm symposium on Parallel Algorithms and Architectures, 2003, pp. 34-43, H. Racke, proceedings of the 43rd Annual IEEE symposium on Foundations of Computer Science, 2002, pp. 43-52] but with the objective of maximizing throughput rather than minimizing congestion. In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. This is accompanied by simple algorithms achieving upper bounds which are tight in terms of k, the maximum throughput achievable by an omniscient algorithm, and are also tight in terms of m, the number of servers. Finally, we investigate an online version of the problem, in a restricted model which requires that clients, upon becoming active, must remain so for at least log(n) time steps. In contrast to our primarily negative results in the oblivious case, here we present an algorithm which is constant- competitive. Our lower bounds justify the intuition, implicit in earlier work on the subject [B. Awerbuch and Y. Azar, proceedings of the 35th Annual IEEE symposium on Foundations of Computer Science, 1994, pp. 240 - 249], that some such restriction (i. e., requiring some stability in the demand pattern over time) is necessary in order to achieve a constant - or even polylogarithmic - competitive ratio.

关键词： distributed algorithms maximum matching multicommodity flow oblivious routing

来源：评论

学校读者我要写书评

暂无评论

Integrating elementary computational modeling and programming principles (abstract only) 12

Integrating elementary computational modeling and programmin...

引用

proceedings of the 43rd acm technical symposium on Computer Science Education

作者： Jose M. Garrido Kennesaw State University Kennesaw GA USA

ISBN: (纸本)9781450310987

We propose an approach to introduce computational models and basic programming principles in an integrated manner and as early as possible in the computing curricula. Our goal is to help educate students of computer science, mathematics, and the various science disciplines, in computational modeling. For this, we have developed a sequence of four courses in computational modeling, the first of which integrates computational modeling with programming principles and includes elementary numerical methods for solving the models. This entry-level course is described and a URL is provided with details of the four courses. Developing a computational model of a problem includes formulating the mathematical representation and implementing it by applying Computer Science concepts, principles and methods.

关键词： computational modeling

来源：评论

学校读者我要写书评

暂无评论

AP CS principles and the 'beauty and joy of computing' curriculum (abstract only) 12

AP CS principles and the 'beauty and joy of computing' curri...

引用

proceedings of the 43rd acm technical symposium on Computer Science Education

作者： Brian Harvey Tiffany Barnes Luke Segars University of California Berkeley CA USA University of North Carolina Charlotte NC USA

ISBN: (纸本)9781450310987

The College Board's guidelines for the coming AP CS principles course are broad enough to allow many different interpretations. In particular, different courses have different levels of technical depth. The "Beauty and Joy of computing" curriculum, used by two of the initial five pilot sites, aims high, with recursion and higher order functions included in the programming half of the course. This session is for high school or college level instructors considering teaching an AP CS principles course and interested in using the BJC curriculum, and/or the Snap! (formerly BYOB) visual programming language used in the curriculum. See http://*** for the curriculum and http://*** for the language.

关键词： higher order functions BJC snap! recursion AP CS principles

来源：评论

学校读者我要写书评

暂无评论

Investigation of candidate techniques for high-frequency AC distributed power systems

Investigation of candidate techniques for high-frequency AC ...

引用

Midwest symposium on Circuits and Systems (MWSCAS)

作者： Shiguo Luo Wei Gu I. Batarseh T. Wu Power Electronics Laboratory Electrical and Computer Engineering Department University of Central Florida Orlando FL USA

DC distributed power systems (DPSs) have been used extensively and a considerable amount of information is available on the subject. The AC DPSs are still in research of conceptual stage. Candidate techniques of high-frequency AC DPSs are investigated in this paper, including bus frequency, bus waveform shapes, front-end inverter topologies and post regulator types. Finally, The major technical issues and challenges are addressed and outlined in this paper.

关键词： Power systems Power conversion Frequency Costs Shape distributed computing Regulators Phased arrays Power system stability Power distribution

来源：评论

学校读者我要写书评

暂无评论

Jean-Claude Laprie Award in dependable computing [3 awardees]

Jean-Claude Laprie Award in dependable computing [3 awardees...

引用

International Conference on Dependable Systems and Networks Workshops (DSN-W)

Dr. Jean-Claude Laprie was Directeur de Recherche at LAAS-CNRS, Toulouse, France. He devoted his entire career to research on the dependability of computing systems. His unique capability of abstraction and formalization, and his contributions to the formulation of the concepts and methodologies of dependability, rapidly led to national and international recognition. He received the IFIP Silver Core in 1992, the Silver Medal of French Scientific Research in 1993, and the Grand Prize in Informatics of the French Academy of Science in 2009. He was made Chevalier de l'Ordre National du Mérite in 2002. The IFIP 10.4 working group on Dependable computing created the award in his honor in 2011. It recognizes outstanding papers that have significantly influenced the theory and/or practice of Dependable computing. For 2013, the award committee decided to recognize three seminal papers, one in each of the award's impact categories: (1) L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem," acm Transactions on Programming Languages and Systems, vol. 4, no. 3, July 1982 pp. 382-401 . (2) J. Gray, "Why Do Computers Stop and What Can Be Done About It?," In symposium on reliability in distributed software and database systems, pp. 3-12. IEEE, 1986. (3) W.G. Bouricius, W.C. Carter and P.R. Schneider, "Reliability Modeling Techniques for Self" Repairing Computer Systems," In proceedings of the 24th acm National Conference, pp. 295-309. acm, 1969.

关键词： Awards

来源：评论

学校读者我要写书评

暂无评论

PSYNC: A Partially Synchronous Language for Fault-Tolerant distributed Algorithms

引用

acm SIGPLAN NOTICES 2016年第1期51卷 400-415页

作者： Dragoi, Cezara Henzinger, Thomas A. Zufferey, Damien CNRS ENS INRIA F-75700 Paris France IST Austria Vienna Austria MIT CSAIL Boston MA USA

Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. We introduce PSYNC, a domain specific language based on the Heard-Of model, which views asynchronous faulty systems as synchronous ones with an adversarial environment that simulates asynchrony and faults by dropping messages. We define a runtime system for PSYNC that efficiently executes on asynchronous networks. We formalize the relation between the runtime system and PSYNC in terms of observational refinement. The high-level lockstep abstraction introduced by PSYNC simplifies the design and implementation of fault-tolerant distributed algorithms and enables automated formal verification. We have implemented an embedding of PSYNC in the SCALA programming language with a runtime system for asynchronous networks. We show the applicability of PSYNC by implementing several important fault-tolerant distributed algorithms and we compare the implementation of consensus algorithms in PSYNC against implementations in other languages in terms of code size, runtime efficiency, and verification.

关键词： Fault-tolerant distributed algorithms Round model Partial synchrony Automated verification Consensus

来源：评论

学校读者我要写书评

暂无评论

Auctions with severely bounded communication

Auctions with severely bounded communication

引用

Annual IEEE symposium on Foundations of Computer Science

作者： L. Blumrosen N. Nisan School of Engineering and Computer Science Hebrew University of Jerusalem Israel

We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare-maximizing and revenue-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove unsurprising properties of these kinds of auctions, e.g. that discrete prices are informationally efficient, as well as some surprising properties, e.g. that asymmetric auctions are better than symmetric ones.

关键词： Computer science Resource management Internet distributed computing Bandwidth Loss measurement Humans Routing Electronic commerce Game theory

来源：评论

学校读者我要写书评

暂无评论

'Cause I'm Strong Enough: Reasoning about Consistency Choices in distributed Systems

引用

acm SIGPLAN NOTICES 2016年第1期51卷 371-384页

作者： Gotsman, Alexey Yang, Hongseok Ferreira, Carla Najafzadeh, Mahsa Shapiro, Marc IMDEA Software Inst Madrid Spain Univ Oxford Oxford OX1 2JD England Univ Nova Lisboa NOVA LINCS DI FCT P-1200 Lisbon Portugal Univ Paris 06 Univ Sorbonne Inria F-75252 Paris 05 France

Large-scale distributed systems often rely on replicated databases that allow a programmer to request different data consistency guarantees for different operations, and thereby control their performance. Using such databases is far from trivial: requesting stronger consistency in too many places may hurt performance, and requesting it in too few places may violate correctness. To help programmers in this task, we propose the first proof rule for establishing that a particular choice of consistency guarantees for various operations on a replicated database is enough to ensure the preservation of a given data integrity invariant. Our rule is modular: it allows reasoning about the behaviour of every operation separately under some assumption on the behaviour of other operations. This leads to simple reasoning, which we have automated in an SMT-based tool. We present a nontrivial proof of soundness of our rule and illustrate its use on several examples.

关键词： Replication causal consistency integrity invariants

来源：评论

学校读者我要写书评

暂无评论

Velocity distributions from the Fourier transforms of Ramsey line shapes

Velocity distributions from the Fourier transforms of Ramsey...

引用

IEEE International Frequency Control symposium

作者： J.H. Shirley Consultant to Time and Frequency Division National Institute for Standards and Technology Boulder CO USA

A computerized method for finding velocity distributions from the Fourier transforms of Ramsey line shapes has been developed. Ramsey lineshape data taken at different excitation powers is used; a weighted average of data from three powers gives satisfactory results. The excitation amplitude parameter b is found by minimizing a quality-of-fit criterion. The method is limited to long standards by the assumption that the excitation length l is much less than the drift region length L. However, the addition of first order l/L corrections to the theory make the method usable for shorter standards. The method has been successfully tested with lineshapes theoretically generated from known velocity distributions.< >

关键词： Fourier transforms Shape Optical beams Interference Frequency conversion NIST distributed computing Testing Optical pumping Laser excitation

来源：评论

学校读者我要写书评

暂无评论

Global information from local observation

Global information from local observation

引用

Annual IEEE symposium on Foundations of Computer Science

作者： I. Benjamini L. Lovasz Microsoft Research Limited Redmond WA USA

We observe a certain random process on a graph "locally", i.e., in the neighborhood of a node, and would like to derive information about "global" properties of the graph. For example, what can we know about a graph based on observing the returns of a random walk to a given node? Our main result concerns a graph embedded in an orientable surface with genus g, and a process, consisting of random excitations of edges and random balancing around nodes and faces. It is shown how to obtain the genus of the surface in polynomial time from local observations of the process restricted to a connected subgraph whose size is (essentially) O(g/sup 2/).

关键词： Random processes Polynomials Birds Information retrieval Sampling methods Physics computing distributed algorithms Computer science Algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：