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

A time-optimal distributed sorting algorithm on a line network

INFORMATION PROCESSING LETTERS 2002年第1期83卷 21-26页

作者： Sasaki, A NTT Corp NTT Commun Sci Labs Kyoto Japan

We have achieved a strict lower time bound of n - 1 for distributed sorting on a line network, where n is the number of processes. The lower time bound has traditionally been considered to be n because it is proved based on the number of disjoint comparison-exchange operations in parallel sorting on a linear array. Our result has overthrown the traditional common belief. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： distributed sorting algorithms computational complexity distributed computing line network

来源：评论

学校读者我要写书评

暂无评论

The bit complexity of distributed sorting

引用

ALGORITHMICA 1997年第3期18卷 405-416页

作者： Gerstel, O Zaks, S TECHNION ISRAEL INST TECHNOL DEPT COMP SCIIL-32000 HAIFAISRAEL

We study the bit complexity of the sorting problem for asynchronous distributed systems. We show that for every network with a tree topology T, every sorting algorithm must send at least Omega(Delta(T) log(L/N)) bits in the worst case, where {1, 2,..., L} is the set of possible initial values, and Delta(T) is the sum of distances from all the vertices to a median of the tree. In addition, we present an algorithm that sends at most O (Delta(T) log((L.N)/Delta(T))) bits for such trees. These bounds are tight if either L = Omega(N1+epsilon) or Delta(T) = Omega(N-2). We also present results regarding average distributions. These results suggest that sorting is an inherently nondistributive problem, since it requires an amount of information transfer that is equal to the concentration of all the data in a single processor, which then distributes the final results to the whole network. The importance of bit complexity-as opposed to message complexity-stems also from the fact that, in the lower bound discussion, no assumptions are made as to the nature of the algorithm.

关键词： distributed system distributed sorting bit complexity

来源：评论

学校读者我要写书评

暂无评论

The Round Complexity of distributed sorting [Extended Abstract] 11

The Round Complexity of Distributed Sorting [Extended Abstra...

引用

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

作者： Patt-Shamir, Boaz Teplitsky, Marat Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

ISBN: (纸本)9781450307192

We consider the model of fully connected networks, where in each round each node can send an O(log n)-bit message to each other node (this is the CONGEST model with diameter 1). It is known that in this model, min-weight spanning trees can be found in O(log log n) rounds. In this paper we show that distributed sorting, where each node has at most n items, can be done in time O(log log n) as well. It is also shown that selection can be done in O(1) time. (Using a concurrent result by Lenzen and Wattenhofer, the complexity of sorting is further reduced to constant.) Our algorithms are randomized, and the stated complexity bounds hold with high probability.

关键词： network algorithms communication complexity distributed sorting CONGEST model

来源：评论

学校读者我要写书评

暂无评论

SELF-STABILIZING distributed sorting IN TREE NETWORKS

引用

Parallel Algorithms and Applications 2001年第1期16卷 1-15页

作者： Ajoy K. Datta[a] Sbastien Tixeuil[b] [a] Department of Computer Science University of Nevada Las Vegas France [b] Laboratoire de Recherche en Informatique Universite de Paris-Sud France

This paper presents a self-stabilizing distributed sorting algorithm for tree networks. The distributed sorting problem can be informally described as follows: Nodes cooperate to reach a global configuration where every node, depending on its identifier, is assigned a specific final value taken from a set of input values distributed across all nodes. The input values may change in time. In our solution, the system reaches its final configuration in a finite time after the input values are stable and the faults cease. The fault-tolerance and the adaptivity to changing input is achieved using Dijkstra's paradigm of self-stabilization. A self-stabilizing algorithm, regardless of the initial system state, will converge in finite time to a set oflegitimatestates without the need for explicit exception handlers or backward recovery. Our solution is based on a continuous broadcast with acknowledgment along the tree edges to achieve the synchronization among processes in the system. It has 0(n×h) time complexity and only 0(log(n) × ) memory requirement wherehis the degree of the tree and h is the height of the tree.

关键词： distributed algorithm distributed sorting Self-stabilization

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for selection and sorting of large distributed files on de bruijn and hypercube structures

引用

International Journal of Foundations of Computer Science 2003年第6期14.0卷 1129-1146页

作者： Wei, David S. L. Rajasekaran, Sanguthevar Naik, Kshirasagar Kuo, Sy-Yen Dept. of Comp. and Info. Sc. Fordham University Bronx NY 10458 United States Dept. of Comp. and Info. Sc. University of Florida Gainesville FL 32611 United States Dept. of Elect. and Comp. Eng. University of Waterloo Waterloo ON N2L 3G1 Canada Dept. of Elect. Eng. National Taiwan University Taipei Taiwan

In this paper we show the power of sampling techniques in designing efficient distributed algorithms. In particular, we apply sampling techniques in the design of selection algorithms on the hypercube and de Bruijn networks, and show that the message complexity of selecting an item from a set (file) is less sensitive to the cardinality of the set (file). Given a file with n keys, our algorithm performs a selection on a p-node de Bruijn network or hypercube using only O(p log log n) messages and suffering a delay of O(τ log p log log n), with high probability. Our selection scheme outperforms the existing approaches in terms of both message complexity and communication delay. Because of the lesser sensitivity of message complexity and communication delay of our algorithms to the file size, our distributed selection schemes are very attractive in applications where very large database systems are involved. Using our selection algorithms, we also show that both quicksort-based sorting scheme and enumeration sorting scheme can be developed for sorting large distributed files on the hypercube and de Bruijn networks. Both of our sorting algorithms outperform the existing distributed sorting schemes in terms of both message complexity and communication delay. © 2003 World Scientific Publishing Company.

关键词： de Bruijn network distributed selection distributed sorting hypercube large distributed files

来源：评论

学校读者我要写书评

暂无评论

Efficient stochastic successive cancellation list decoder for polar codes

引用

Science China(Information Sciences) 2020年第10期63卷 133-151页

作者： Xiao LIANG Huizheng WANG Yifei SHEN Zaichen ZHANG Xiaohu YOU Chuan ZHANG Laboratory of Efficient Architectures for Digital-communication and Signal-processing (LEADS) Southeast University National Mobile Communications Research Laboratory Southeast University Quantum Information Center of Southeast University

Polar codes are one of the most favorable capacity-achieving codes owing to their simple structures and low decoding complexity. Successive cancellation list(SCL) decoders with large list sizes achieve performances very close to those of maximum-likelihood(ML) decoders. However, hardware cost is a severe problem because an SCL decoder with list size L consists of L copies of a successive cancellation(SC)decoder. To address this issue, a stochastic SCL(SSCL) polar decoder is proposed. Although stochastic computing can achieve a good hardware reduction compared with the deterministic one, its straightforward application to an SCL decoder is not well-suited owing to the precision loss and severe latency. Therefore,a doubling probability approach and adaptive distributed sorting(DS) are introduced. A corresponding hardware architecture is also developed. Field programmable gate array(FPGA) results demonstrate that the proposed stochastic SCL polar decoder can achieve a good performance and complexity tradeoff.

关键词： SCL polar decoder stochastic computing 2-bit decoding distributed sorting hardware

来源：评论

学校读者我要写书评

暂无评论

Hierarchical distributed Frequency Regulation Strategy of Electric Vehicle Cluster Considering Demand Charging Load Optimization

引用

IEEE TRANSACTIONS ON INDUSTRY APPLICATIONS 2022年第1期58卷 720-731页

作者： Deng, Xiaosong Zhang, Qian Li, Yan Sun, Tao Yue, Huanzhan Chongqing Univ State Key Lab Power Transmiss Equipment & Syst Se Chongqing 400044 Peoples R China State Grid Chongqing Elect Power Co Customer Serv Ctr Chongqing 400010 Peoples R China

In view of the problems that the disorderly demand charging load increases the power supply pressure and the control of large-scale cluster is difficult, which will appear during the process of large-scale electric vehicle cluster participating in frequency regulation, this article proposes a hierarchical distributed frequency regulation strategy of electric vehicle cluster considering the optimization of demand charging load. First, the demand charging plans of electric vehicles are optimized to suppress the fluctuation of wind power generation and system load, and the reserve capacity of electric vehicle cluster is predicted in real time. Then, in order to improve the control performance of large-scale cluster, a hierarchically distributed control framework is established, which enables the traditional unit to assist the electric vehicle through the real-time assignment of system frequency regulation task, and realizes the individual-level orderly scheduling of electric vehicles based on the distributed sorting. The simulation results of two-area interconnected system show that the proposed frequency regulation strategy can not only adjust automatically for ensuring expected frequency regulation effect but also reduce the power supply pressure on the grid side, as well as achieve efficient and reliable scheduling of electric vehicle cluster.

关键词： State of charge Batteries Frequency control Optimization Vehicle-to-grid Wind power generation sorting distributed sorting electric vehicles (EVs) frequency regulation (FR) hierarchical distributed control two-way merge algorithm

来源：评论

学校读者我要写书评

暂无评论

Hierarchical distributed Frequency Regulation Strategy of Electric Vehicle Cluster Considering Demand Charging Load Optimization

Hierarchical Distributed Frequency Regulation Strategy of El...

引用

3rd IEEE Student Conference on Electrical Machines and Systems (SCEMS)

作者： Deng, Xiaosong Zhang, Qian Li, Yan Sun, Tao Yue, Huanzhan Chongqing Univ State Key Lab Power Transmiss Equipment & Syst Se Chongqing Peoples R China State Grid Chongqing Elect Power Co Customer Serv Ctr Chongqing Peoples R China

ISBN: (纸本)9781728156224

In view of the problems that the disorderly demand charging load increases the power supply pressure and the control of large-scale cluster is difficult, which will appear during the process of large-scale electric vehicle cluster participating in frequency regulation, this paper proposes a hierarchical distributed frequency regulation strategy of electric vehicle cluster considering the optimization of demand charging load. Firstly, the demand charging plans of electric vehicles are optimized to minimize the system load variance, and the reserve capacity of electric vehicle cluster is predicted in real-time. Then, in order to improve the control performance of large-scale cluster, a hierarchically distributed control framework is established, which enables the traditional unit to assist the electric vehicle through the real-time assignment of system frequency regulation task, and realizes the individual-level orderly scheduling of electric vehicles based on the distributed sorting. The simulation results show that the proposed frequency regulation strategy can not only adjust automatically for ensuring expected frequency regulation effect, but also reduce the power supply pressure on the grid side, as well as achieve efficient and reliable scheduling of electric vehicle cluster.

关键词： electric vehicles frequency regulation hierarchical distributed control distributed sorting 2-way merge algorithm

来源：评论

学校读者我要写书评

暂无评论

Strongly Minimal MapReduce Algorithms: A TeraSort Case Study 1

引用

11th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)

作者： Xia, Daniel Simpson, Michael Srinivasan, Venkatesh Thomo, Alex Univ Victoria Victoria BC Canada

ISBN: (数字)9783030399511

ISBN: (纸本)9783030399511;9783030399504

MapReduce is a widely used parallel computing paradigm for the big data realm on the scale of terabytes and higher. The introduction of minimal MapReduce algorithms promised efficiency in load balancing among participating machines by ensuring that partition skew (where some machines end up processing a significantly larger fraction of the input than other machines) is prevented. Despite minimal MapReduce algorithms guarantee of load-balancing within constant multiplicative factors, the constants are relatively large which severely diminishes the theoretical appeal for true efficiency at scale. We introduce the notion of strongly minimal MapReduce algorithms that provide strong guarantees of parallelization up to a small additive factor that diminishes with an increasing number of machines. We show that a strongly minimal MapReduce algorithm exists for sorting;this leads to strongly minimal algorithms for several fundamental database algorithms and operations that crucially rely on sorting as a primitive. Our techniques are general and apply beyond the analysis of strongly minimal MapReduce algorithms;we show that given a sufficiently high, but still realistic, sampling rate, the approximate partitions obtained from a particular sampling strategy are almost as good as the partitions produced by an ideal partitioning.

关键词： distributed sorting Minimal MapReduce algorithms Sample-Partition problem

来源：评论

学校读者我要写书评

暂无评论

distributed network infrastructure for a search engine

Distributed network infrastructure for a search engine

引用

International Conference on Parallel and distributed Processing Techniques and Applications

作者： Davis, E Kalal, M Tousignant, S Davis, J Wren, B More Informat St Paul MN USA

ISBN: (纸本)1932415262

We are simulating systems with a distributed command function over nodes organized into trusted neighborhoods. An application of this architecture could support a new generation of search engines. Today's Internet search engines use a central command and control function within an Internet environment, whose mark of modernity is the absence of such a centralized structure. We discuss how a query could be answered from distributed data stores using HeteroSort, a sorting technique we described in past papers. A query initiates a cycle of a broadcast to and receives responses from a potentially large number of nodes self organized into an emergent HeteroSort network following the locally determined path of the broadcast. This initial query and the returning responses involve minimal messages. The second cycle consists of the transmission of a more complex query to a specific subset of the initially responding nodes.

关键词： emergent networks distributed sorting information retrieval

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：