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

28th annual acm symposium on principles of distributed computing

作者： Aspnes, James Attiya, Hagit Censor, Keren Yale Univ Dept Comp Sci New Haven CT 06520 USA

ISBN: (纸本)9781605583969

A method is given for constructing a max register, a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously written. For fixed m, art m-valued max register can be constructed from one-bit multi-writer multi-reader registers at a cost of at most [lg m] atomic register operations per write or read. The construction takes the form of a binary search tree: applying classic techniques for building unbalanced search trees gives an unbounded max register with cost O(min(log v, n)) to read or write a value v, where n is the number of processes. It is also shown how a max register can be used to transform any monotone circuit into a wait-free concurrent data structure that provides write operations setting the inputs to the circuit and a read operation that returns the value of the circuit on the largest input values previously supplied. The cost of a write is bounded by O(Sd min(inverted right perpendicularlg minverted left perpendicular, n), where m is the size of the alphabet for the circuit, S is the number of gates whose value changes as the result of the write, and d is the number of inputs to each gate, the cost of a read is min(inverted right perpendicularlg minverted left perpendicular, O(n)). While the resulting data structure is not linearizable in general, it satisfies a weaker but natural consistency condition. As an application, we obtain a simple, linearizable, wait-free counter implementation with a cost of O(min(log n log v,n)) to perform an increment and O(min(log v, n)) to perform a read, where v is the current value of the counter. For polynomially-many increments, this becomes O(log(2) n), an exponential improvement on the best previously known upper bounds of O(n) for an exact counting and O(n(4/5+epsilon)) for approximate counting. Finally, it is shown that the upper bounds are almost optimal. We prove that min(inverted right perpendicularlg minverted left perpend

关键词： distributed computing shared memory max registers counters monotone circuits

来源：评论

学校读者我要写书评

暂无评论

Greedy distributed optimization of multi-commodity flows

Greedy distributed optimization of multi-commodity flows

引用

26th annual acm symposium on principles of distributed computing

作者： Awerbuch, Baruch Khandekar, Rohit IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA

The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in connection-oriented network architectures. We consider solutions for distributed multi-commodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We provide the first stateless greedy distributed algorithm for the concurrent multi-commodity flow problem with poly-logarithmic convergence. More precisely, our algorithm achieves 1 + epsilon approximation, with running time O(H center dot log(O(1)) m center dot (1/epsilon)(O(1))) where H is the number of edges on any allowed flow-path. No prior results exist for our model. Our algorithm is a reasonable alternative to existing polynomial sequential approximation algorithms, such as Garg-Konemann (proceedings of the 39th annual symposium on Foundations of Computer Science, Palo Alto, CA, USA, pp. 300-309, 1998). The algorithm is simple and can be easily implemented or taught in a classroom. Remarkably, our algorithm requires that the increase in the flow rate on a link is more aggressive than the decrease in the rate. Essentially all of the existing flow-control heuristics are variations of TCP, which uses a conservative cap on the increase (e. g., additive), and a rather liberal cap on the decrease (e. g., multiplicative). In contrast, our algorithm requires the increase to be multiplicative, and that this increase is dramatically more aggressive than the decrease.

关键词： Multi-commodity flows distributed algorithms Statelessness Self-stabilization

来源：评论

学校读者我要写书评

暂无评论

Weak Graph Colorings: distributed Algorithms and Applications 09

Weak Graph Colorings: Distributed Algorithms and Application...

引用

21st acm symposium on Parallelism in Algorithms and Architectures

作者： Kuhn, Fabian MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)9781605586069

We study deterministic, distributed algorithms for two weak variants of the standard graph coloring problem. We consider defective colorings, i.e., colorings where nodes of a color class may induce a graph of maximum degree d for some parameter d > 0. We also look at colorings where a minimum number of multi-chromatic edges is required. For an integer k > 0, we call a coloring k-partially proper if every node v has at least min {k, deg(v)} neighbors with a different color We show that for all d is an element of {1, ... , Delta}, it is possible to compute a O(Delta(2)/d(2))-coloring with defect d in time O(log* n) where Delta is the largest degree of the network graph. Similarly, for all k is an element of {1, ... , Delta}, a k-partially proper O(k(2))-coloring can be computed in O(log* n) rounds. As an application of our weak defective coloring algorithm, we obtain a faster deterministic algorithm for the standard vertex coloring problem on graphs with moderate degrees. We show that in time O(Delta + log* n), a (Delta + 1)-coloring can be computed, a task for which the best previous algorithm required time O(Delta log Delta + log* n). The same result holds for the problem of computing a maximal independent set.

关键词： distributed algorithms graph coloring locality deterministic symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

proceedings of the annual acm symposium on principles of distributed computing 2009: Foreword

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

引用

proceedings of the annual acm symposium on principles of distributed computing 2009年 iii页

作者： Alvisi, Lorenzo University of Texas Austin TX United States

来源：评论

学校读者我要写书评

暂无评论

Simple and Efficient Asynchronous Byzantine Agreement with Optimal Resilience

Simple and Efficient Asynchronous Byzantine Agreement with O...

引用

28th annual acm symposium on principles of distributed computing

作者： Patra, Arpita Choudhary, Ashish Rangan, C. Pandu Indian Inst Technol Dept Comp Sci & Engn Chennai 600036 Tamil Nadu India

ISBN: (纸本)9781605583969

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A(t) with unbounded computing power actively controls at most t = (inverted right perpendicularn/3inverted left perpendicular - 1) out of n parties in Byzantine fashion. In this setting, we say that pi is a t-resilient, (1 - epsilon)-terminating Asynchronous Byzantine Agreement (ABA) protocol, if pi satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating A(t) and terminates (i.e every honest party terminates pi) with probability at least (1 - epsilon). In this work, we present a new t-resilient, (1 - epsilon)-terminating ABA protocol which privately communicates O(Cn(6) kappa) bits and A-casts(1) O(Cn(6) kappa) bits, where epsilon = 2(-Omega(kappa)) and C is the expected running time of the protocol. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time;i.e., C = O(1). Our ABA protocol is to be compared with the only known t-resilient, (1 - epsilon)-terminating ABA protocol of [5] in the same settings, which privately communicates O(Cn(11) kappa(4)) bits and A-casts O(Cn(11) kappa(2) log(n)) bits, where epsilon = 2(-Omega(kappa)) and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of [5], while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al [1] proposed a t-resilient. 1-terminating (called as almost-surely terminating in [1]) ABA protocol which privately communicates O(Cn(6) log n) bits and A-casts O(Cn(6) log n) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n(2))) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any kappa < n(2) log n, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in co

关键词： Unbounded computing Power VSS Byzantine Agreement Asynchronous Networks

来源：评论

学校读者我要写书评

暂无评论

Special issue on PODC 2007

引用

distributed computing 2009年第5期21卷 315-315页

作者： Wattenhofer, Roger Swiss Fed Inst Technol Zurich Switzerland

This special issue of distributed computing is based on papers that originally appeared, in preliminary and abbreviated form, in the proceedings of the 26th annual acm symposium on principles of distributed computing (PODC 2007), held in Portland, Oregon on 12-15 August 2007. The papers were chosen by the Program Committee from the 32 full-length papers presented at the symposium, based on their quality and representation of the range of topics addressed in the symposium. In addition to being reviewed, in preliminary form, by the Program Committee of PODC 2007, the papers selected for this special issue were subsequently refereed according to the standard practices of distributed computing. I wish to thank both the referees and the authors of these papers. Due to time constraints, some of the papers invited to the special issue could not appear in this volume; these will appear in a future volume of this journal.

关键词： journals Time constraints distributed computing referee

来源：评论

学校读者我要写书评

暂无评论

Emerging challenges and opportunities in parallel computing: the cretaceous redux? 09

Emerging challenges and opportunities in parallel computing:...

引用

proceedings of the 28th acm symposium on principles of distributed computing

作者： Bruce Hendrickson Sandia National Laboratories Albuquerque NM USA

ISBN: (纸本)9781605583969

Despite decades of activity, parallel computing remains immature. Like much of computer science, advances in the field are driven by a mixture of theoretical insights and technological advances. But in parallel computing, the gap between theory and practice remains disconcertingly *** theoretical concepts in parallel computing were developed in the seventies including P-completeness, PRAMs, boolean circuits, and more. A rich set of algorithms and complexity classes was built on top of these models, and these ideas influenced early thinking about parallel machines. But applied parallel computing today is little influenced by these *** the past twenty years computational scientists and engineers have embraced parallelism as an essential computational tool for solving ever larger and more complex problems. By the mid-nineties, the computational science community had settled on a computing paradigm involving distributed memory machines programmed with explicit message passing. Although not elegant, this approach allows for portability and the use of inexpensive commodity hardware. This hardware is sufficiently different from the abstract models proposed in the seventies that insights from the theory community have had minimal impact on mainstream parallel computing practice.A variety of alternative theoretical models have been proposed in the interim that are more reflective of hardware realities than their counterparts from the seventies. These include the Bulk Synchronous Processing and LogP complexity models as well as computational abstractions like Active Messages partitioned global address space languages. But these concepts and tools have been consigned to niche roles within the larger MPI-dominated parallel computing ***, several forces are rearranging the parallel computing landscape and will raise the importance of ideas and techniques from the theory community. The most familiar change is the rise of multi-core processors. The need for

关键词： parallel computing

来源：评论

学校读者我要写书评

暂无评论

Fast Self-Stabilizing Byzantine Tolerant Digital Clock Synchronization

Fast Self-Stabilizing Byzantine Tolerant Digital Clock Synch...

引用

27th annual acm symposium on principles of distributed computing

作者： Ben-Or, Michael Dolev, Danny Hoch, Ezra N. Hebrew Univ Jerusalem IL-91905 Jerusalem Israel

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.

关键词： distributed computing fault tolerance self-stabilization Byzantine failures clock synchronization digital clock synchronization

来源：评论

学校读者我要写书评

暂无评论

On Tradeoff Between Network Connectivity, Phase Complexity and Communication Complexity of Reliable Communication Tolerating Mixed Adversary

On Tradeoff Between Network Connectivity, Phase Complexity a...

引用

27th annual acm symposium on principles of distributed computing

作者： Ashwinkumar, B., V Patra, Arpita Choudhary, Ashish Srinathan, Kannan Rangan, C. Pandu Indian Inst Technol Dept Comp Sci & Engn Madras Tamil Nadu India Ctr Secur IIIT Theory & Algorithm Res Hyderabad Andhra Pradesh India

ISBN: (纸本)9781595939890

In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous, network, tolerating a mixed adversary A(t(b), t(f)), who has unbounded computing power and can corrupt t(b) and t(f) nodes in the network in Byzantine and fail-stop fashion respectively.

关键词： Unbounded computing Power

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: distributed churn measurement in arbitrary networks

Brief announcement: Distributed churn measurement in arbitra...

引用

27th acm SIGACT-SIGOPS symposium on principles of distributed computing

作者： Gramoli, Vincent Kermarrec, Anne-Marie Merrer, Erwan Le EPFL and Univ. of Neuchtel Switzerland INRIA Rennes France

No abstract available

ISBN: (纸本)9781595939890

No abstract available

关键词： Churn Dynamics Gossip Large-scale

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：