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

31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS)

作者： Lempiainen, Tuomo Aalto Univ Dept Comp Sci Helsinki Inst Informat Technol Espoo Finland

ISBN: (纸本)9781450343916

Hella et al. (PODC 2012, Distributed Computing 2015) identified seven different message-passing models of distributed computing one of which is the port-numbering model-and provided a complete classification of their computational power relative to each other. However, their method for simulating the ability to count incoming messages causes an additive overhead of 2 Delta - 2 communication rounds, and it was not clear if this is actually optimal. In this paper we give a positive answer, by using bisimulation as our main tool: there is a matching linear-in-Delta lower bound. This closes the final gap in our understanding of the models, with respect to the number of communication rounds. By a previously identified connection to modal logic, our result has implications to the relationship between multimodal logic and graded multimodal logic.

关键词： distributed computing port-numbering model local algorithms lower bounds bisimulation

来源：评论

学校读者我要写书评

暂无评论

Energy-efficient strategies for building short chains of mobile robots locally

Energy-efficient strategies for building short chains of mob...

引用

18th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Brandes, Philipp Degener, Bastian Kempkes, Barbara der Heide, Friedhelm Meyer Auf Univ Paderborn CS Dept Heinz Nixdorf Inst D-33098 Paderborn Germany

We are given a winding chain of n mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. The goal is to let the robots converge to the line between the stations. The robots are modeled as points in the plane which cannot collide. We use a discrete and synchronous time model, but we restrict the movement of each mobile robot to a distance of 8 in each round. This restriction fills the gap between the previously used discrete time model with an unbounded step length and the continuous time model which was introduced in [Bastian Degener, Barbara Kempkes, Peter Kling, Friedhelm Meyer auf der Heide, A continuous, local strategy for constructing a short chain of mobile robots, in: SIROCCO'10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, 2010, pp. 168-182]. We adapt the Go-To-The-Middle strategy by Dynia, Kutylowski, Lorek and Meyer auf der Heide (BICC 2006): In each round, each robot first observes the positions of its neighbors and then moves towards the midpoint between them until it reaches the point or has moved a distance of B. The main energy consumers in this scenario are the number of observations of positions of neighbors, which equals the number of rounds, and the distance to be traveled by the robots. We analyze the strategy with respect to both quality measures and provide asymptotically tight bounds. We show that the best choice for 8 for this strategy is 8 E e(D, since this minimizes (up to constant factors) both energy consumers, the number of rounds as well as the maximum traveled distance, at the same time. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Mobile robots local algorithms Dynamics Robot formation problems Convergence speed Distributed algorithms Geometric networks

来源：评论

学校读者我要写书评

暂无评论

Scalable algorithms in the Age of Big Data and Network Sciences: Characterization, Primitives, and Techniques 18

Scalable Algorithms in the Age of Big Data and Network Scien...

引用

11th ACM International Conference on Web Search and Data Mining

作者： Teng, Shang-Hua Univ Southern Calif Los Angeles CA 90007 USA

ISBN: (纸本)9781450355810

In the age of network sciences and machine learning, efficient algorithms are now in higher demand more than ever before. Big Data fundamentally challenges the classical notion of efficient algorithms: algorithms that used to be considered efficient, according to polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation. Using several basic tasks in network analysis, machine learning, and optimization as examples - in this talk - I will highlight a family of fundamental algorithmic techniques for designing provably-good scalable algorithms.

关键词： scalable algorithms graph sparsification local algorithms advanced sampling big data network sciences machine learning

来源：评论

学校读者我要写书评

暂无评论

Distributed Learning of Hop Count Distributions in Ad Hoc Networks 17

Distributed Learning of Hop Count Distributions in Ad Hoc Ne...

引用

17th ACM International Symposium on Mobility Management and Wireless Access (MobiWac)

作者： Shamoun, Simon CUNY New York NY 10021 USA Bar Ilan Univ Ramat Gan Israel

ISBN: (纸本)9781450369053

This is a study of the feasibility of learning the hop count distribution of a mobile ad hoc network using in-network data. The nodes maintain a histogram of the hop count from the source of all packets received and share the histograms with one another. This can be used to learn the distribution between all pairs of nodes or groups of nodes. The effectiveness of this method and the effect of various factors is shown by simulation. The advantage of this method over theoretical and experimental analysis of the hop count distribution is that it is not tied to specific models of node distribution, propagation, and network protocols, and can be used to learn the distribution in real time. It is useful for the dynamic optimization of methods needed for the efficient and effective operation of an ad hoc network.

关键词： hop count distribution distributed learning mobile ad hoc networks local algorithms nonparametric statistics distribution functions

来源：评论

学校读者我要写书评

暂无评论

CARRE: Cellular Automaton based Redundant Readers Elimination in RFID Networks

CARRE: Cellular Automaton based Redundant Readers Eliminatio...

引用

IEEE International Conference on Communications (ICC)

作者： Rashid, Nafiul Choudhury, Salimur Salomaa, Kai Islamic Univ Technol Dept Comp Sci & Engn Dhaka Bangladesh Algoma Univ Dept Math & Comp Sci Sault Ste Marie ON Canada Queens Univ Sch Comp Kingston ON Canada

ISBN: (纸本)9781479966646

Redundant readers elimination is one of the fundamental optimization research problems in RFID networks. The problem is NP-hard and can be solved approximately using best known centralized set cover algorithms. However, either distributed or localized solutions for this problem are much more realistic and useful in practice. Different distributed and a few local algorithms are known in the literature. In this paper, we propose a cellular automaton based local algorithm for the redundant readers elimination optimization problem. To the best of our knowledge, this is the first cellular automaton based algorithm (that is, a strictly local algorithm) to solve this problem. We compare the performance of our algorithm with other local algorithms and establish that our algorithm gives much better results. We also compare our algorithm with the best known centralized approximation algorithm and find very competitive results even though our algorithm is a local one.

关键词： RFID Networks Readers Tags local algorithms Cellular Automata

来源：评论

学校读者我要写书评

暂无评论

Coloring Unstructured Wireless Multi-Hop Networks

Coloring Unstructured Wireless Multi-Hop Networks

引用

28th Annual ACM Symposium on Principles of Distributed Computing

作者： Schneider, Johannes Wattenhofer, Roger ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland

ISBN: (纸本)9781605583969

We present a randomized coloring algorithm for the unstructured radio network model, a model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric network topology. The current state-of-the-art coloring algorithm needs with high probability O(Delta . log n) time and uses O(Delta) colors, where n and Delta are the number of nodes in the network and the maximum degree, respectively;this algorithm requires knowledge of a linear bound on n and Delta. We improve this result in three ways: Firstly, we improve the time complexity, instead of the logarithmic factor we just need a polylogarithmic additive term, more specifically, our time complexity is O(Delta + log Delta . log n) given an estimate of n and Delta, and O(Delta + log(2) n) without knowledge of Delta. Secondly, our vertex coloring algorithm needs Delta + 1 colors only. Thirdly, our algorithm manages to do a distance-d coloring with asymptotically optimal O(Delta) colors for a constant d.

关键词： Ad Hoc Networks Sensor Networks Unstructured Radio Networks Unit Disk Graphs Growth Bounded Graphs Bounded Independence Graphs local algorithms Parallel algorithms Distributed algorithms Coloring

来源：评论

学校读者我要写书评

暂无评论

A fast network-decomposition algorithm and its applications to constant-time distributed computation 1

引用

22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Barenboim, Leonid Elkin, Michael Gavoille, Cyril Open Univ Israel Raanana Israel Ben Gurion Univ Negev Beer Sheva Israel Univ Bordeaux LaBRI Bordeaux France

ISBN: (数字)9783319252582

ISBN: (纸本)9783319252575

A partition (C-1, C-2, . . . ,C-q) of G = (V, E) into clusters of strong (respectively, weak) diameter d, such that the supergraph obtained by contracting each C-i is l-colorable is called a strong (resp., weak) (d, l)-network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong (d, l)-network-decompositions with d = l = exp {O(root logn log logn)} can be computed in distributed deterministic time O(d). Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of Awerbuch et al. was improved by Panconesi and Srinivasan in 1992: in the latter result d = l = exp{O(root logn)}, and the running time is O(d) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak (O(logn), O(logn))-network-decompositions can be computed in distributed randomized time O(log(2)n). Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O(1). However, the parameter l in his result is O (n(1/2+epsilon)). In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong (O(1), O(n(epsilon)))-network-decompositions. As a corollary we derive a constant-time randomized O(n(epsilon))-approximation algorithm for the distributed minimum coloring problem, improving the previously bestknown O(n(1/2+epsilon)) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open proble

关键词： Distributed algorithms local algorithms Dominating sets Coloring Spanners

来源：评论

学校读者我要写书评

暂无评论

A local algorithm and its percolation analysis of bipartite z-matching problem

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2023年第5期2023卷 053401-053401页

作者： Zhao, Jin-Hua South China Normal Univ Sch Data Sci & Engn Shanwei 516600 Peoples R China South China Normal Univ Inst Quantum Matter Guangdong Prov Key Lab Nucl Sci Guangzhou 510006 Peoples R China South China Normal Univ Southern Nucl Sci Comp Ctr Guangdong Hong Kong Joint Lab Quantum Matter Guangzhou 510006 Peoples R China

A z-matching on a bipartite graph is a set of edges, among which each vertex of two types of the graph is adjacent to at most 1 and at most z (>= 1) edges, respectively. The z-matching problem concerns finding z-matchings with the maximum size. Our approach to this combinatorial optimization problem is twofold. From an algorithmic perspective, we adopt a local algorithm as a linear approximate solver to find z-matchings on any graph instance, whose basic component is a generalized greedy leaf removal procedure in graph theory. From a theoretical perspective, on uncorrelated random bipartite graphs, we develop a mean-field theory for the percolation phenomenon underlying the local algorithm, leading to an analytical estimation of z-matching sizes on random graphs. Our analytical theory corrects the prediction by belief propagation algorithm at zero-temperature limit in (*** ' c and Bianconi 2019 ***. 126 028001). Besides, our theoretical framework extends a core percolation analysis of kappa-XORSAT problems to a general context of uncorrelated random hypergraphs with arbitrary degree distributions of factor and variable nodes.

关键词： random graphs combinatorial optimization local algorithms percolation theory

来源：评论

学校读者我要写书评

暂无评论

A New Technique For Distributed Symmetry Breaking

A New Technique For Distributed Symmetry Breaking

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Schneider, Johannes Wattenhofer, Roger ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland

ISBN: (纸本)9781605588889

We introduce MULTI-TRIALS, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time/color trade-off. To get a Delta + 1 coloring takes time O(log Delta + root log n). To obtain an O(Delta + log(1+1/log)*(n) n) coloring takes time O(log* n). This is more than an exponential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Delta log((c)) n + log(1+1/c) n) colors, where c denotes an arbitrary constant and log((c)) n denotes the c times (recursively) applied logarithm to n. We also use the MULTI-TRIALS technique to compute network decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes.

关键词： local algorithms Parallel algorithms Coloring Symmetry Breaking Network Decomposition

来源：评论

学校读者我要写书评

暂无评论

locally Checkable Proofs 11

Locally Checkable Proofs

引用

30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Goos, Mika Suomela, Jukka Univ Helsinki Helsinki Inst Informat Technol HIIT FI-00014 Helsinki Finland

ISBN: (纸本)9781450307192

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node: However, it is more difficult to prove that a graph is not bipartite-it turns out that any locally checkable proof requires Omega(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, circle minus(1), circle minus(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Omega(n(2)) bits per node, and non-3-colourable graphs, which require Omega(n(2)/log n) bits per node-any pure graph property admits a trivial proof of size O(n(2)).

关键词： local algorithms proof complexity graph properties nondeterministic algorithms decision problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：