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

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

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: BMobi-Causal: A causal broadcast protocol in mobile dynamic groups

Brief announcement: BMobi-Causal: A causal broadcast protoco...

引用

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

作者： Benzaïd, Chafika Badache, Nadjib LSI USTHB B.P. 32 El Alia Bab Ezzouar Alger Algeria

ISBN: (纸本)9781595939890

In this paper, we propose a simple and optimal causal broadcast protocol which copes with the dynamically changing groups in mobile environments. The protocol depends on two simples, yet powerful ideas. The first consists in the use of the immediate dependency relationship (IDR) in the construction of control information (CI), resulting in O(1) message overhead. When the second original idea consists in considering the join/leave requests as data messages. This ensures a consistent perception within a group and makes no need to a coordination phase in the installation of a view.

关键词： distributed computer systems

来源：评论

学校读者我要写书评

暂无评论

Failure detectors as type boosters

引用

distributed computing 2008年第5期20卷 343-358页

作者： Guerraoui, Rachid Kouznetsov, Petr Ecole Polytech Fed Lausanne Distributed Programming Lab CH-1015 Lausanne Switzerland Max Planck Inst Software Syst D-66123 Saarbrucken Germany

The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the weakest failure detector to solve consensus among a number k > n of processes that communicate using shared objects of a type T with consensus power n. In other words, we seek for a failure detector that is sufficient and necessary to "boost" the consensus power of a type T from n to k. It was shown in Neiger (proceedings of the 14th annual ACM symposium on principles of distributed computing (PODC), pp. 100-109, 1995) that a certain failure detector, denoted Omega (n) , is sufficient to boost the power of a type T from n to k, and it was conjectured that Omega (n) was also necessary. In this paper, we prove this conjecture for one-shot deterministic types. We first show that, for any one-shot deterministic type T with cons(T) <= n, Omega (n) is necessary to boost the power of T from n to n + 1. Then we go a step further and show that Omega(n) is also the weakest to boost the power of (n + 1)-ported one-shot deterministic types from n to any k > n. Our result generalizes, in a precise sense, the result of the weakest failure detector to solve consensus in asynchronous message-passing systems (Chandra et al. in J ACM 43(4):685-722, 1996). As a corollary, we show that Omega (t) is the weakest failure detector to boost the resilience level of a distributed shared memory system, i.e., to solve consensus among n > t processes using (t - 1)-resilient objects of consensus power t.

关键词： ALGORITHMS STANDARDS MEMORY REGISTERS (Computers) COMPUTER file sharing

来源：评论

学校读者我要写书评

暂无评论

distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons

Distributed Algorithms for Ultrasparse Spanners and Linear S...

引用

27th annual ACM symposium on principles of distributed computing

作者： Pettie, Seth Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48104 USA

ISBN: (纸本)9781595939890

We present efficient algorithms for computing very sparse low distortion spanners in distributed networks and prove some non-trivial lower bounds on the tradeoff between time sparseness, and distortion. All of our algorithms assume it synchronized distributed network, where relatively short, messages may be communicated in each time step. Our first result is an O(log n)(1+0(1))-time algorithm for finding it (2(O(log)* (n)) log n)-spanner with size O(n). Besides being nearly optimal in time and distortion, this algorithm appears to be the first, that constructs a O(a)-size skeleton without requiring unbounded length messages or time proportional to the diameter of the network. Our second result is a, new Class Of efficiently constructible (alpha, beta)-spanners. called Fibonacci spanners whose distortion improves with Hie distance being approximated. At then, sparsest Fibonacci spanners can have nearly linear size O(n(log log n)(phi)) where phi = 1+root 5/2 is the golden ratio. As the distance increases the Fibonacci spanner's Multiplicative distortion passes through four discrete stages, moving front logarithmic to doubly log-arithmic then into a period where it;is constant, tending to 3, followed by, another period tending to 1. On the lower bound side, we prove that many recent sequential spanner constructions have no efficient counterparts in distributed networks, event if the desired distortion only needs to be achieved oil the average or for a tiny fraction of the vertices. In particular, any distance preservers, purely additive spanners, or spanners with sublinear additive distortion must either be very dense, slow to construct, or have very weak guarantees oil distortion.

关键词： Spanner

来源：评论

学校读者我要写书评

暂无评论

New Combinatorial Topology Upper and Lower Bounds for Renaming

New Combinatorial Topology Upper and Lower Bounds for Renami...

引用

27th annual ACM symposium on principles of distributed computing

作者： Castaneda, Armando Rajsbaum, Sergio Univ Nacl Autonoma Mexico Inst Matemat Mexico City 04510 DF Mexico

ISBN: (纸本)9781595939890

In the renaming task n+1 processes start with unique input names front a large space and must choose unique output names taken front a smaller name space, namely 0, 1,..., K. To rule out trivial solutions, a protocol niust be anonymous: the value chosen by a process can depend on its input name and on the execution, but not oil the specific process id. Attiya et, al. showed in 1990 that renaming has a wait-free solution when K >= 2n. Several proofs of a lower bound stating that, no such protocol exists when K < 2n have been published. In this paper we prove that, for certain values of n, this lower bound is incorrect, exhibiting a wait-free renaming protocol for K = 2n - 1. For the other values of n, we present the first completely combinatorial lower bound proof stating that no such protocol exists when K < 2n. More precisely, our main theorem states that there exists a wait-free renaming protocol for K < 2n if and only if the set of integers {(n+1 i+1) : 0 <= i <= [n-1/2]} are relatively prime. Thus, such protocol exists for six processes, and not for less. The proof of the theorem uses combinatorial topology techniques, both for the lower bound and to derive the renaming protocol.

关键词： Combinatorial topology distributed systems renaming shared memory systems wait-free computation

来源：评论

学校读者我要写书评

暂无评论

distributed Network Monitoring and Multicommodity Flows: A Primal-Dual Approach

Distributed Network Monitoring and Multicommodity Flows: A P...

引用

16th annual ACM symposium on principles of distributed computing

作者： Awerbuch, Baruch Khandekar, Rohit Johns Hopkins Univ Baltimore MD 21218 USA

ISBN: (纸本)9781595936165

A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper, we consider the following covering and packing problems, which are the dual of each other: Passive Commodity Monitoring: minimize the total cost of monitoring devices used to measure the network traffic on all paths. Maximum Throughput Multicommodity flow: maximize the total value of the flow with bounded edge capacities. We present the first known distributed algorithms for both of these problems that converge to (1 + epsilon)-approximate solutions in poly-logarithmic time with communication and space overheads that depend on the maximal path length but are almost independent of the size of the entire network. Previous distributed solutions achieving similar approximations required convergence time, communication, or space overheads that depend polynomially on the size of the entire network. The sequential simulation of our algorithm is more efficient than the fastest known approximation algorithms for multicommodity flows, e.g., Garg-Konemann [14], when the maximal path length is small.

关键词： distributed algorithms multi-commodity flows passive network measurement

来源：评论

学校读者我要写书评

暂无评论

Time-Decaying Sketches for Sensor Data Aggregation

Time-Decaying Sketches for Sensor Data Aggregation

引用

16th annual ACM symposium on principles of distributed computing

作者： Cormode, Graham Tirthapura, Srikanta Xu, Bojian AT&T Labs Res Florham Pk NJ 07932 USA

ISBN: (纸本)9781595936165

We present a new sketch for summarizing network data. The sketch has the following properties which make it useful in communication-efficient aggregation in distributed streaming scenarios, such as sensor networks: the sketch is duplicate-insensitive, i.e. re-insertions of the same data will not affect the sketch, and hence the estimates of aggregates. Unlike previous duplicate-insensitive sketches for sensor data aggregation [26, 12]: it is also time-decaying, so that the weight of a data item in the sketch can decrease with time according to a user-specified decay function. The sketch can give provably approximate guarantees for various aggregates of data, including the sum, median, quantiles, and frequent elements. The size of the sketch and the time taken to update it are both polylogarithmic in the size of the relevant data. Further, multiple sketches computed over distributed data can be combined without losing the accuracy guarantees. To our knowledge, this is the first sketch that combines all the above properties.

关键词： Sensor network data aggregation data stream processing time decay sliding windows asynchronous streams distributed streams duplicate insensitive sketch

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Minimizing the total cost of network measurements in a distributed manner: A primal-dual approach

Brief announcement: Minimizing the total cost of network mea...

引用

PODC'07: 26th annual ACM symposium on principles of distributed computing

作者： Awerbuch, Baruch Khandekar, Rohit Johns Hopkins University IBM T.J. Watson Research Center

ISBN: (纸本)1595936165

We consider the Active Min-Cost Measurement problem to minimize the cost incurred by measuring network link delays. Although the problem has a polynomial representation, its covering LP formulation, for which most of the previous distributed algorithms apply, has an exponential number of variables, one for each path. We present first known distributed (1+) approximation algorithm for this problem that converges in time that is linear in the maximal path length and poly-logarithmic in the size of the entire network and has polynomial computational overhead. Previous distributed solutions achieving similar approximations required either convergence time that is polynomial or computational overhead that is exponential in the size of the entire network. Copyright © 2007 ACM.

关键词： Computer networks

来源：评论

学校读者我要写书评

暂无评论

Greedy distributed Optimization of Multi-Commodity Flows

Greedy Distributed Optimization of Multi-Commodity Flows

引用

16th annual ACM symposium on principles of distributed computing

作者： Awerbuch, Baruch Khandekar, Rohit Johns Hopkins Univ Baltimore MD 21218 USA

ISBN: (纸本)9781595936165

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(log ***(O(1)) m.(1/epsilon)(O(1))) where P is the number of flow-paths in the network. No prior results exist for our model. Our algorithm is a reasonable alternative to existing polynomial sequential approximation algorithms, such as Garg-Konemann [17]. 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

来源：评论

学校读者我要写书评

暂无评论

Controller and Estimator for Dynamic Networks

Controller and Estimator for Dynamic Networks

引用

16th annual ACM symposium on principles of distributed computing

作者： Korman, Amos Kutten, Shay Technion Israel Inst Technol Fac IE&M Haifa Israel

ISBN: (纸本)9781595936165

Afek, Awerbuch, Plotkin, and Saks identified an important fundamental problem inherent to distributed networks, which they called the Resource Controller problem. Consider, first, the problem in which one node (called the 'root') is required to estimate the number of events that occurred all over the network. This counting problem can be viewed as a useful variant of the heavily studied and used task of topology update (that deals with collecting all remote information). The Resource Controller problem generalizes the counting problem: such remote events are considered as requests, and the counting node, i.e., the 'root', also issues permits for the requests. That way, the number of request granted can be controlled (bounded). An efficient Resource Controller was constructed in the paper by Afek et al., which can operate oil a dynamic network assuming that the network is spanned by a tree that may only grow, and only by allowing leaves to join the tree. In contrast, the Resource Controller presented here can operate tinder a more general dynamic model, allowing the spanning tree of the network to undergo both insertions and deletions of both leaves and internal nodes. Despite the more dynamic network model we allow, the message complexity of our controller is always at most the message complexity of the more restricted controller. All the applications for the controller of Afek et al. apply also for our controller. Moreover, with the same message complexity, our controller can handle these applications under the more general dynamic model mentioned above. In particular, under the more general dynamic model, the new controller can be transformed into an efficient size-estimation protocol, i.e.;a protocol allowing the root to maintain a constant estimation of the number of nodes in the dynamically changing network. Informally, the resulted new size-estimation protocol uses O(log(2) n) amortized message complexity per topological change (assuming that the number of cha

关键词： distributed algorithms Labeling schemes Asynchronous protocols

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：