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

34th annual acm symposium on principles of distributed computing (PODC)

作者： Ostrovsky, Rafail Rosenbaum, Will Univ Calif Los Angeles Dept Comp Sci 4732 Boelter Hall Los Angeles CA 90095 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

ISBN: (纸本)9781450336178

In their seminal work on the Stable Marriage Problem, Gale and Shapley [4] describe an algorithm which finds a stable matching in O (n(2)) communication rounds. Their algorithm has a natural interpretation as a distributed algorithm where each player is represented by a single processor. In this distributed model, Floreen, Kaski, Polishchuk, and Suomela [3] recently showed that for bounded preference lists, terminating the Gale-Shapley algorithm after a constant number of rounds results in an almost stable matching. In this paper, we describe a new deterministic distributed algorithm which finds an almost stable matching in O(log(5) n) communication rounds for arbitrary preferences. We also present a faster randomized variant which requires O(log(2) n) rounds. This run-time can be improved to O(1) rounds for "almost regular" (and in particular complete) preferences. To our knowledge, these are the first sub-polynomial round distributed algorithms for any variant of the stable marriage problem with unbounded preferences.

关键词： stable marriage problem stable matchings distributed algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimal Synchrony for Byzantine Consensus 15

Minimal Synchrony for Byzantine Consensus

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： Bouzid, Zohir Mostfaoui, Achour Raynal, Michel Univ Rennes IRISA Rennes France Univ Nantes LINA F-44322 Nantes France Inst Univ France Paris France

ISBN: (纸本)9781450336178

Solving the consensus problem requires in one way or another that the underlying system satisfies some synchrony assumption. Considering an asynchronous message-passing system of n processes where (a) up to t < n/3 may commit Byzantine failures, and (b) each pair of processes is connected by two uni-directional channels (with possibly different timing properties), this paper investigates the synchrony assumption required to solve consensus, and presents a signature-free consensus algorithm whose synchrony requirement is the existence of a process that is an eventual < t + 1 > bisource. Such a process p is a correct process that eventually has (a) timely input channels from t correct processes and (b) timely output channels to t correct processes ( these input and output channels can connect p to different subsets of processes). As this synchrony condition was shown to be necessary and sufficient in the stronger asynchronous system model (a) enriched with message authentication, and (b) where the channels are bidirectional and have the same timing properties in both directions, it follows that it is also necessary and sufficient in the weaker system model considered in the paper. In addition to the fact that it closes a long-lasting problem related to Byzantine agreement, a noteworthy feature of the proposed algorithm lies in its design simplicity, which is a first-class property.

关键词： Adopt-commit Asynchronous message-passing Byzantine process Consensus distributed algorithm Eventual timely channel Feasibility condition Lower bound Optimal resilience Reliable broadcast Signature-free algorithm Synchrony assumption

来源：评论

学校读者我要写书评

暂无评论

computing Weak Consistency in Polynomial Time

Computing Weak Consistency in Polynomial Time

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： Golab, Wojciech Li, Xiaozhou (Steve) Lopez-Ortiz, Alejandro Nishimura, Naomi Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada Google Inc Mountain View CA USA Univ Waterloo Sch Comp Sci Waterloo ON Canada

ISBN: (纸本)9781450336178

The k-atomicity property can be used to describe the consistency of data operations in large distributed storage systems. The weak consistency guarantees offered by such systems are seen as a necessary compromise in view of Brewer's CAP principle. The k-atomicity property requires that every read operation obtains a value that is at most k updates (writes) old, and becomes a useful way to quantify weak consistency if k is treated as a variable that can be computed from a history of operations. Specifically, the value of k quantifies how far the history deviates from Lamport's atomicity property for read/write registers. We address the problem of computing k indirectly by solving the k-atomicity verification problem (k-AV): given a history of read/write operations and a positive integer k, decide whether the history is k-atomic. Gibbons and Korach showed that in general this problem is NP-complete when k = 1, and hence not solvable in polynomial time unless P = NP. In this paper we present two algorithms that solve the k-AV problem for any k >= 2 in special cases. Similarly to known solutions for k = 1 and k = 2, both algorithms assume that all the values written to a given object are distinct. The first algorithm places an additional restriction on the structure of the input history and solves k-AV in O(n(2) +n center dot k log k) time. The second algorithm does not place any additional restrictions on the input but is efficient only when k is small and when concurrency among write operations is limited. Its time complexity is O(n(2)) if both k and our particular measure of write concurrency are bounded by constants.

关键词： Consistency atomicity verification distributed storage

来源：评论

学校读者我要写书评

暂无评论

Construction and Impromptu Repair of an MST in a distributed Network with o(m) Communication 15

Construction and Impromptu Repair of an MST in a Distributed...

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： King, Valerie Kutten, Shay Thorup, Mikkel Univ Victoria Comp Sci Victoria BC Canada Technion Fac IE & M IL-32000 Haifa Israel Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450336178

In the CONGEST model, a communications network is an undirected graph whose n nodes are processors and whose m edges are the communications links between processors. At any given time step, a message of size O(log n) may be sent by each node to each of its neighbours. We show for the synchronous model: If all nodes start in the same round, and each node knows its ID and the ID's of its neighbors, or in the case of MST, the distinct weights of its incident edges and knows n, then there are Monte Carlo algorithms which succeed w.h.p. to determine a minimum spanning forest (MST) and a spanning forest (ST) using O(n log(2) n/log log n) messages for MST and O (n log n) messages for ST, resp. These results contradict the "folk theorem" noted in Awerbuch, ***., Jacm 1990 that the distributed construction of a broadcast tree requires Omega(m) messages. This lower bound has been shown there and in other papers for some CONGEST models;our protocol demonstrates the limits of these models. A dynamic distributed network is one which undergoes online edge insertions or deletions. We also show how to repair an MST or ST in a dynamic network with asynchronous communication. An edge deletion can be processed in O(n log n= log log n) expected messages in the MST, and O(n) expected messages for the ST problem, while an edge insertion uses O(n) messages in the worst case. We call this "impromptu" updating as we assume that between processing of edge updates there is no preprocessing or storage of additional information. Previous algorithms for this problem that use an amortized o(m) messages per update require substantial preprocessing and additional local storage between updates.

关键词： spanning tree distributed algorithms message complexity network algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic (Δ+1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks 15

Deterministic (Δ+1)-Coloring in Sublinear (in Δ) Time in S...

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： Barenboim, Leonid Open Univ Israel Dept Math & Comp Sci Raanana Israel

ISBN: (纸本)9781450336178

In the distributed message passing model a communication network is represented by an n-vertex graph G = (V, E) of maximum degree Delta. Computation proceeds in discrete synchronous rounds consisting of sending and receiving messages and performing local computations. The running time of an algorithm is the number of rounds it requires. In the static setting the network remains unchanged throughout the entire execution. In the dynamic setting the topology of the network changes, and a new solution has to be computed after each change. In the faulty setting the network is static, but some vertices or edges may lose the computed solution as a result of faults. The goal of an algorithm in this setting is fixing the solution. The problems of (Delta + 1)-vertex-coloring and (2 Delta - 1)-edge-coloring are among the most important and intensively studied problems in distributed computing. Despite a very intensive research in the last 30 years, no deterministic algorithms for these problems with sublinear (in Delta) time have been known so far. Moreover, for more restricted scenarios and some related problems there are lower bounds of Omega(Delta) [13, 14, 20, 27]. The question of the possibility to devise algorithms that overcome this challenging barrier is one of the most fundamental questions in distributed symmetry breaking [4, 6, 13, 14, 19, 24]. In this paper we settle this question for (Delta+1)-vertex-coloring and (2 Delta-1)-edge-coloring by devising deterministic algorithms that require O(Delta(3/4) log Delta+log* n) time in the static, dynamic and faulty settings. (The term log* n is unavoidable in view of the lower bound of Linial [21].) Moreover, for (1+ o(1))Delta-vertex-coloring and (2+ o(1))Delta-edge-coloring we devise algorithms with (O) over tilde (root Delta + log* n) deterministic time. This is roughly a quadratic improvement comparing to the state-of-the-art that requires O(Delta + log* n) time [4, 19, 24]. Our results are actually more general than t

关键词： distributed Algorithms Coloring Partitions Polynomials

来源：评论

学校读者我要写书评

暂无评论

Terminating distributed Construction of Shapes and Patterns in a Fair Solution of Automata 15

Terminating Distributed Construction of Shapes and Patterns ...

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： Michail, Othon Comp Technol Inst & Press Diophantus CTI Patras Greece

ISBN: (纸本)9781450336178

In this work, we consider a solution of automata similar to Population Protocols and Network Constructors. The automata, also called nodes, move passively in a well-mixed solution and can cooperate by interacting in pairs. During every such interaction, the nodes, apart from updating their states, may also choose to connect to each other in order to start forming some required structure. The model introduced here is a more applied version of Network Constructors, imposing geometrical constraints on the permissible connections. Each node can connect to other nodes only via a very limited number of local ports, which implies that at any given time it has only a bounded number of neighbors. Connections are always made at unit distance and are perpendicular to connections of neighboring ports. Though this variation can no longer form abstract networks, it is still capable of forming very practical 2D or 3D shapes. We develop new techniques for determining the computational and constructive capabilities of our model. One of the main novelties, concerns our attempt to overcome the inherent inability of such systems to terminate. In particular, exploiting the assumptions that the system is well-mixed and has a unique leader, we give terminating protocols that are correct with high probability (w.h.p.). This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols. One of our main results is a terminating protocol counting the size n of the system w.h.p.. We then use this protocol as a subroutine in order to develop our universal constructors, establishing that it is possible for the nodes to self-organize w.h.p. into arbitrarily complex shapes and additionally always terminate

关键词： network construction programmable matter shape formation population distributed protocol interacting automata fairness random schedule self-organization

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: A Hierarchy of Congested Clique Models, from Broadcast to Unicast 15

Brief Announcement: A Hierarchy of Congested Clique Models, ...

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： Becker, Florent Fernandez Anta, Antonio Rapaport, Ivan Reemila, Eric Univ Orleans Orleans France IMDEA Networks Inst Madrid Spain Univ Chile DIM CMM UMI CNRS 2807 Santiago Chile Univ Lyon GATE LSE UMR CNRS 5824 St Etienne France

ISBN: (纸本)9781450336178

The CONGEST model is a synchronous, message-passing model of distributed computation in which each node can send (possibly different) messages of O(log n) bits along each of its incident communication links in each round, where n is the number of computing nodes in the system. In the particular case where the communication network is a complete graph, we have the unicast congested clique model. On the other end is the broadcast version of the congested clique model, in which each node can only broadcast a single message over all its links in each round. In this paper we explore the space, in terms of round complexity, that lies between these two congested clique models. Hence, we parametrize the congested clique model with the range r, the maximum number of different messages a node can send over its incident links in one round. Additionally, we study the effect of the bandwidth b, the maximum size in bits of these messages. We show that the space between the unicast and broadcast congested clique models is very rich and interesting. For instance, we show that a problem (especially designed for this work) takes Omega(n/log n) rounds in the broadcast model (r = 1), while it can be solved in two rounds if two messages can be sent (r = 2). Other gaps are found in other parts of the spectrum of values of r. We do this by providing techniques to simulate protocols with different parameters. Therefore, we conclude that, with respect to their power to solve certain problems, there is a strict hierarchy of congested clique models.

关键词： CONGEST model congested clique model message passing distributed computation

来源：评论

学校读者我要写书评

暂无评论

Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems [Extended Abstract] 15

Stabilizing Server-Based Storage in Byzantine Asynchronous M...

引用

34th annual acm symposium on principles of distributed computing (PODC)

作者： Bonomi, Silvia Dolev, Shlomi Potop-Butucaru, Maria Raynal, Michel Univ Roma La Sapienza DIAG Rome Italy Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Univ P&M Curie LIP6 Paris France Univ Rennes IRISA Inst Univ France Rennes France

ISBN: (纸本)9781450336178

A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of n servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t < n/8 Byzantine servers if communication is asynchronous, and t < n/3 Byzantine servers if it is synchronous. The noteworthy feature of the proposed algorithms is that (to our knowledge) these are the first that build an atomic read/write storage on top of asynchronous servers prone to transient failures, and where up to t of them can be Byzantine.

关键词： Asynchronous message-passing system Atomic read/write register Byzantine server Clients/servers architecture distributed algorithm Fault-tolerance Read/write register Regular register Self-stabilization Transient failures

来源：评论

学校读者我要写书评

暂无评论

distributed (Δ+1)-COLORING IN LINEAR (IN Δ) TIME

引用

SIAM JOURNAL ON computing 2014年第1期43卷 72-95页

作者： Barenboim, Leonid Elkin, Michael Kuhn, Fabian Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Univ Freiburg Dept Comp Sci D-79110 Freiburg Germany

The distributed (Delta + 1)-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving algorithms has been published. The state-of-the-art running time, prior to our work, is O(Delta log Delta + log* n), due to Kuhn and Wattenhofer [proceedings of the 25th annual acm symposium on principles of distributed computing, Denver, CO, 2006, pp. 7-15]. Linial [proceedings of the 28th annual IEEE symposium on Foundation of Computer Science, Los Angeles, CA, 1987, pp. 331-335] proved a lower bound of 1/2 log* n for the problem, and Szegedy and Vishwanathan [proceedings of the 25th annual acm symposium on Theory of computing, San Diego, CA, 1993, pp. 201-207] provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve a running time smaller than Theta(Delta log Delta). We present a deterministic (Delta + 1)-coloring distributed algorithm with running time O(Delta) + 1/2 log* n. We also present a trade-off between the running time and the number of colors, and devise an O(***)-coloring algorithm, with running time O(Delta/lambda + log* n), for any parameter lambda > 1. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan and achieves running time which is linear in the maximum degree Delta. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm does not belong to the family of locally iterative algorithms. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring [L. Cowen, R. Cowen, and D. Woodall, J. Graph Theory, 10 (1986), pp. 187-195]. In an m-defective p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-defective p-coloring with reasonably small m and p can be compute

关键词： legal-coloring defective-coloring distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

PODC 2014 - proceedings of the 2014 acm symposium on principles of distributed computing

PODC 2014 - Proceedings of the 2014 ACM Symposium on Princip...

引用

2014 acm symposium on principles of distributed computing, PODC 2014

ISBN: (纸本)9781450329446

The proceedings contain 51 papers. The topics discussed include: asynchronous MPC with a strict honest majority using non-equivocation;distributing the setup in universally composable multi-party computation;the future(s) of shared data structures;a paradox of eventual linearizability in shared memory;brief announcement: are lock-free concurrent algorithms practically wait-free?;brief announcement: a generic construction for nonblocking dual containers;multi-message broadcast with abstract MAC layers and unreliable links;simple and efficient local codes for distributed stable network construction;beyond set disjointness: the communication complexity of finding the intersection;breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication;and estimation for monotone sampling: competitiveness and customization.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：