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

31st ACM International Conference on Information and Knowledge Management (CIKM)

作者： Zhou, Jun Qi, Feng Hua, Zhigang Jian, Daohong Liu, Ziqi Wu, Hua Zhejiang Univ Coll Comp Sci Hangzhou Peoples R China Ant Grp Hangzhou Peoples R China Ant Grp Sunnyvale CA USA Ant Grp Beijing Peoples R China

ISBN: (纸本)9781450392365

Assigning items to owners is a common problem found in various real-world applications, for example, audience-channel matching in marketing campaigns, borrower-lender matching in loan management, and shopper-merchant matching in e-commerce. Given an objective and multiple constraints, an assignment problem can be formulated as a constrained optimization problem. Such assignment problems are usually NP-hard [21], so when the number of items or the number of owners is large, solving for exact solutions becomes challenging. In this paper, we are interested in solving constrained assignment problems with hundreds of millions of items. Thus, with just tens of owners, the number of decision variables is at billion-scale. This scale is usually seen in the internet industry, which makes decisions for large groups of users. We relax the possible integer constraint, and formulate a general optimization problem that covers commonly seen assignment problems. Its objective function is convex. Its constraints are either linear, or convex and separable by items. We study to solve our generalized assignment problems in the Bregman Alternating Direction Method of Multipliers (BADMM) framework where we exploit Bregman divergence to transform the Augmented Lagrangian into a separable form, and solve many subproblems in parallel. The entire solution can thus be implemented using a MapReduce-style distributed computation framework. We present experiment results on both synthetic and real-world datasets to verify its accuracy and scalability.

关键词： Assignment Problem ADMM Large-Scale Optimization distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

The topology of local computing in networks

引用

Journal of Applied and Computational Topology 2024年第4期8卷 1069-1098页

作者： Fraigniaud, Pierre Paz, Ami Institut de Recherche en Informatique Fondamentale CNRS Université Paris Cité Laboratoire Interdisciplinaire des Sciences du Numérique CNRS Université Paris-Saclay

For more than three decades, distributed systems have been described and analyzed using topological tools, primarily using two techniques: protocol complexes and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects (typically a shared memory consisting of a collection of read-write registers) or message-passing enabling direct communication between any pair of processes. This paper aims to examine the use of protocol complexes in the study of network computing. In this case, processes are located at the network nodes and communicate by exchanging messages only along the network’s edges (i.e., not every pair of processes can directly communicate). There are several reasons why applying the topological approach to network computing can be challenging, and a prominent one is that node identifiers yield protocol complexes whose sizes grow exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or the network size. We leverage this independence to meet the above challenge and present local protocol complexes, whose sizes do not depend on the network size. As an application of the “compacted” protocol complexes, we reformulate the celebrated lower bound of Ω(log^∗n) rounds for 3-coloring the n-node ring in the topological framework. © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2024.

关键词： Combinatorial topology distributed algorithms distributed computing distributed graph algorithms Theory of computation

来源：评论

学校读者我要写书评

暂无评论

Partition Detection in Byzantine Networks 44

Partition Detection in Byzantine Networks

引用

44th IEEE International Conference on distributed Computing Systems (ICDCS)

作者： Bromberg, Yerom-David Decouchant, Jeremie Sourisseau, Manon Taiani, Francois Univ Rennes IRISA CNRS INRIA Rennes France Delft Univ Technol Delft Netherlands

ISBN: (纸本)9798350386066;9798350386059

Detecting and handling network partitions is a fundamental requirement of distributed systems. Although existing partition detection methods in arbitrary graphs tolerate unreliable networks, they either assume that all nodes are correct or that a limited number of nodes might crash. In particular, Byzantine behaviors are out of the scope of these algorithms despite Byzantine fault tolerance being an active research topic for important problems such as consensus. Moreover, Byzantine-tolerant protocols, such as broadcast or consensus, always rely on the assumption of connected networks. This paper addresses the problem of detecting partition in Byzantine networks (without connectivity assumption). We present a novel algorithm, which we call NECTAR, that safely detects partitioned and possibly partitionable networks and prove its correctness. NECTAR allows all correct nodes to detect whether a network could suffer from Byzantine nodes. We evaluate NECTAR's performance and compare it to two existing baselines using up to 100 nodes running real code, on various realistic topologies. Our results confirm that NECTAR maintains a 100% accuracy while the accuracy of the various existing baselines decreases by at least 40% as soon as one participant is Byzantine. Although NECTAR's network cost increases with the number of nodes and decreases with the network's diameter, it does not go above around 500KB in the worst cases.

关键词： Byzantine Fault Network Partition Digital Signatures distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed predefined-time constrained social cost minimization problem under the partial information setting

引用

SYSTEMS & CONTROL LETTERS 2024年 191卷

作者： Liu, Dongxin Nian, Xiaohong Li, Fan Cent South Univ Sch Automat Changsha 410075 Peoples R China

In this letter, the social cost minimization problem with coupled equality constraints is studied, where the agents endeavor to collaboratively minimize the sum of all local cost functions, and each local cost function depends on a global decision variable consisting of the decisions of all participants. In a setting where only partial information about one's own decisions and cost function is available, the first single-time scale predefined-time distributed algorithm based on the time-based-generator scheme is designed to tackle the problem. With the help of the Lyapunov stability theory, it is demonstrated that the algorithm can converge to the optimal solution in an arbitrarily specified time independent of the initial state and control parameters. Finally, the effectiveness of the proposed algorithm is verified by numerical simulations.

关键词： distributed algorithms Predefined-time convergence Social cost minimization Partial information setting Coupled constraints

来源：评论

学校读者我要写书评

暂无评论

A Linear Push-Pull Average Consensus Algorithm for Delay-Prone Networks

A Linear Push-Pull Average Consensus Algorithm for Delay-Pro...

引用

European Control Conference (ECC)

作者： Makridis, Evagoras Charalambous, Themistoklis Univ Cyprus Sch Engn Dept Elect & Comp Engn CY-1678 Nicosia Cyprus Aalto Univ Sch Elect Engn Dept Elect Engn & Automat Espoo 02150 Finland

ISBN: (纸本)9798331540920;9783907144107

In this paper, we address the average consensus problem of multi-agent systems for possibly unbalanced and delay-prone networks with directional information flow. We propose a linear distributed algorithm (referred to as RP-PAC) that handles asynchronous updates and time-varying heterogeneous information delays. Our proposed distributed algorithm utilizes a surplus-consensus mechanism and information regarding the number of incoming and outgoing links to guarantee state averaging, despite the imbalanced and delayed information flow in directional networks. The convergence of the RPPAC algorithm is examined using key properties of the backward product of time-varying matrices that correspond to different snapshots of the directional augmented network.

关键词： distributed algorithms push-pull consensus average consensus directed graphs time-varying heterogeneous delays

来源：评论

学校读者我要写书评

暂无评论

distributed K-Clustering with Exponential Convergence

Distributed K-Clustering with Exponential Convergence

引用

American Control Conference (ACC)

作者： Wang, L. Tron, R. Univ Calif Irvine Samueli Sch Engn Irvine CA 92697 USA Boston Univ Coll Engn Boston MA 02215 USA

ISBN: (数字)9781665451963

ISBN: (纸本)9781665451963

We consider the problem of distributed K-clustering in a network of N agents where each agent holds a part of a dataset. The goal for the agents is to agree, in a distributed manner, on a set of K cluster centers that effectively summarize the entire dataset (e.g., by identifying points where the data is most concentrated), without explicitly exchanging all the data between all the agents or with a central node. First, we consider the special case when there is only one cluster (K = 1). We propose the distributed 1-clustering Multiplier Algorithm (Di 1MA), which ensures exponential convergence of all the copies of the cluster center at each agent to a common value by combining the properties of consensus algorithms and of the augmented Lagrangian method. Second, based on the previous case, we propose an algorithm called distributed K-clustering Multiplier Algorithm (DiKMA) to solve the case with K > 1 cluster centers. For this case, using ideas from switching algorithms, our solution alternates q steps of updates of the cluster centers with one update of the local assignments of data to cluster centers. We show that there must exist a q large enough such that the algorithm ensures the exponential convergence of the K cluster centers. We provide simulations to verify the proposed algorithms, and illustrate some of their properties.

关键词： Clustering algorithms distributed databases Switches Consensus algorithm Approximation algorithms Trajectory distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond 2024

Optimal Communication Bounds for Classic Functions in the Co...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Esfandiari, Hossein Kacham, Praneeth Mirrokni, Vahab Woodruff, David P. Zhong, Peilin Google London England Carnegie Mellon Univ Pittsburgh PA USA Google Res New York NY USA

ISBN: (纸本)9798400703836

In the coordinator model of communication with B servers, given an arbitrary non-negative function f, we study the problem of approximating the sum Sigma i([n]) f(x(i)) up to a 1 +/- epsilon factor. Here the vector x is an element of R-n is defined to be x = x ( 1)+ center dot center dot center dot+x(s), where x(j) >= 0 denotes the non-negative vector held by the 9 -th server. A special case of the problem is when f(x) = x(k) which corresponds to the well-studied problem of F-k moment estimation in the distributed communication model. We introduce a new parameter c(f)[s] which captures the communication complexity of approximating Sigma(i is an element of[n]) f(x(i)) and for a broad class of functions f which includes f(x) = x(k) for k >= 2 and other robust functions such as the Huber loss function, we give a two round protocol that uses total communication c(f)[s]/epsilon(2) bits, up to polylogarithmic factors. For this broad class of functions, our result improves upon the communication bounds achieved by Kannan, Vempala, andWoodruff (COLT 2014) andWoodruff and Zhang (STOC 2012), obtaining the optimal communication up to polylogarithmic factors in the minimum number of rounds. We show that our protocol can also be used for approximating higher-order correlations. Our results are part of a broad framework for optimally sampling from a joint distribution in terms of the marginal distributions held on individual servers. Apart from the coordinator model, algorithms for other graph topologies in which each node is a server have been extensively studied. We argue that directly lifting protocols from the coordinator model to other graph topologies will require some nodes in the graph to send a lot of communication. Hence, a natural question is the type of problems that can be efficiently solved in general graph topologies. We address this question by giving communication efficient protocols in the so-called personalized CONGEST model for solving linear regression and lo

关键词： distributed algorithms coordinator model moment estimation personalized CONGEST model

来源：评论

学校读者我要写书评

暂无评论

Fast distributed Beamforming without Receiver Feedback 56

Fast Distributed Beamforming without Receiver Feedback

引用

56th Asilomar Conference on Signals, Systems, and Computers

作者： Chakrabarti, Kushal Bedi, Amrit S. Dagefu, Fikadu T. Twigg, Jeffrey N. Chopra, Nikhil Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Inst Syst Res College Pk MD 20742 USA DEVCOM Army Res Lab Adelphi MD USA Univ Maryland Dept Mech Engn College Pk MD 20742 USA

ISBN: (纸本)9781665459068

distributed multi-agent beampattern matching inherently enables covert communication by constructively combining the transmitted signals at target receivers and forming nulls towards the adversaries. Most existing beamforming methodologies achieve this by relying on partial or full-state real-time feedback from the receivers. This paper proposes a novel distributed beamforming technique that does not assume any feedback from the receivers or channel parameters, such as multipath fading. The proposed algorithm works in a server-agent architecture of the beamforming agents, eliminating the need for receivers' feedback. Our algorithm is built on the classical gradient-descent (GD) method. However, when the problem is ill-conditioned, GD requires many iterations to converge and is unstable against system noise. We propose an iterative preconditioning technique to mitigate the deleterious effects of the data points' conditioning on the convergence rate, facilitating a rapid establishment of communication links with far-field targets. The empirical results demonstrate the proposed beamforming algorithm's favorable convergence rate and robustness against unknown multipath fading in realistic environments.

关键词： Antenna arrays Cooperative communication distributed algorithms MIMO communication

来源：评论

学校读者我要写书评

暂无评论

Similarity Joins of Sparse Features

引用

ACM International Conference on Management of Data (SIGMOD)

作者： Metwally, Ahmed Shum, Michael Uber Technol Inc Sunnyvale CA 94158 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9798400704222

Identifying all pairs of records from two datasets whose similarity exceeds a given threshold is crucial for data cleaning and clustering. Our work on similarity-joins is motivated by detecting fraud and abuse. We focus on similarity-joins of sparse features, where records represent sparse sets, multisets, or vectors. Most state-of-the-art techniques are distributed versions of sequential algorithms. This is the reason they fail to scale when the alphabet is large, the records are large, or some elements are shared by numerous records. In this paper, we propose FastScalableSparseJoiner (FSSJ) that introduces quasi-prefix filtering, a novel flavor of prefix filtering [7] that exploits the skew in element popularity to avoid processing the most-popular elements without broadcasting the sorted elements to all executors. FastScalableSparseJoiner effectively prunes candidate pairs, and efficiently distributes the computation of partial results for load-balancing across executors. FSSJ can be adopted in any shared-nothing architecture. Based on our evaluation on synthetic and real datasets using a Spark-based implementation, FSSJ is very competitive on small datasets, and is the only algorithm that can join industry-scale datasets even with limited resources.

关键词： Similarity Joins distributed algorithms Load balancing

来源：评论

学校读者我要写书评

暂无评论

Black Hole Search in Dynamic Cactus Graph 18th

Black Hole Search in Dynamic Cactus Graph

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Bhattacharya, Adri Italiano, Giuseppe F. Mandal, Partha Sarathi Indian Inst Technol Guwahati Gauhati India

ISBN: (纸本)9789819705658;9789819705665

We study the problem of black hole search by a set of mobile agents, where the underlying graph is a dynamic cactus. A black hole is a dangerous vertex in the graph that eliminates any visiting agent without leaving any trace behind. Key parameters that dictate the complexity of finding the black hole include: the number of agents required (termed as size), the number of moves performed by the agents in order to determine the black hole location (termed as move) and the time (or round) taken to terminate. This problem has already been studied where the underlying graph is a dynamic ring [6]. In this paper, we extend the same problem to a dynamic cactus. We introduce two categories of dynamicity, but still, the underlying graph needs to be connected: first, we examine the scenario where, at most, one dynamic edge can disappear or reappear at any round. Secondly, we consider the problem for at most k dynamic edges. In both scenarios, we establish lower and upper bounds for the necessary number of agents, moves and rounds.

关键词： Black hole search Dynamic cactus graph Dynamic networks Time-varying graphs Mobile Agents distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：