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

Synchronous Byzantine Agreement With O(n) Messages and O(1) Expected Time

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2025年 20卷 338-349页

作者： Wang, Haochen You, Qidi Duan, Sisi Tsinghua Univ Inst Adv Study Beijing 100190 Peoples R China pace Star Technol Co Ltd Beijing 100086 Peoples R China State Key Lab Space Ground Integrated Informat Tec Beijing 100095 Peoples R China Zhongguancun Lab Beijing 100089 Peoples R China Shandong Inst Blockchain Jinan 250101 Peoples R China

Byzantine agreement is the most fundamental primitive in distributed computing. All known Byzantine agreement protocols achieve quadratic or sub-quadratic messages and communication. We show that surprisingly, by directly assuming a random leader election oracle (that can be built from the verifiable random function), threshold signatures, and the $1/3$ corruption bound, we can build Linear-BA, a binary agreement (BA) that has linear message complexity, constant expected time complexity, and a normal case that has linear communication. We extend Linear-BA to construct Linear-MBA, a multi-valued Byzantine agreement (MBA) protocol also with $O(n)$ messages and $O(1)$ expected time. Finally, we present Linear-MBA-SV, an MBA protocol with the strong validity property via a no-cost transformation from Linear-MBA. All the protocols above are secure under a static adversary, where a static adversary corrupts a set of replicas at the beginning of the protocol. We go on and show an impossibility result that in the adaptive adversary model (in which the adversary can selectively corrupt the replicas while the protocol is running), one cannot build a Byzantine agreement protocol with $O(n)$ messages and $O(1)$ expected time. Accordingly, we revise our protocol to obtain Byzantine agreement protocols with $O(n)$ messages per round and $O(n)$ time. Our results offer a fresh view of what is needed for linear Byzantine agreement: by examining the "needed" assumptions, one can identify the performance bottlenecks for Byzantine agreement. Meanwhile, all our protocols are efficient, as all the building blocks have efficient instantiations.

关键词： Protocols Complexity theory Voting Transforms Adaptation models Linearity Fault tolerant systems Fault tolerance Time complexity distributed computing Byzantine agreement constant expected time linear message complexity

来源：评论

学校读者我要写书评

暂无评论

Scaling Synthetic Brain Data Generation

引用

IEEE JOURNAL OF BIOMEDICAL AND HEALTH INFORMATICS 2025年第2期29卷 840-847页

作者： Doan, Mike Plis, Sergey Georgia State Univ TReNDS Ctr Atlanta GA 30302 USA

The limited availability of diverse, high-quality datasets is a significant challenge in applying deep learning to neuroimaging research. Although synthetic data generation can potentially address this issue, on-the-fly generation is computationally demanding, while training on pre-generated data is inflexible and may incur high storage costs. We introduce Wirehead, a scalable in-memory data pipeline that significantly improves the performance of on-the-fly synthetic data generation for deep learning in neuroimaging. Wirehead's architecture decouples data generation from training by running multiple generators in independent parallel processes, facilitating near-linear performance gains proportional to the number of generators used. It efficiently handles terabytes of data using MongoDB, greatly minimizing prohibitive storage costs. The robust, modular design enables flexible pipeline configurations and fault-tolerant operation. We evaluated Wirehead with SynthSeg, a synthetic brain segmentation data generation tool that requires 7 days to train a model. When deployed in parallel, Wirehead achieved a near-linear 15.7x increase in throughput with 16 generators. With 20 generators, we can train a model in 9 hours instead of 7 days. This demonstrates Wirehead's ability to greatly accelerate experimentation cycles. While Wirehead represents a substantial step forward, it also reveals opportunities for future research in optimizing generation-training balance and resource allocation. Its ability to facilitate distributed deep learning has significant implications for enabling more ambitious neuroimaging research.

关键词： Training Generators Data collection Graphics processing units Throughput Computer architecture Synthetic data Neuroimaging Data models Brain modeling Deep learning distributed computing magnetic resonance imaging neuroimaging synthetic data generation

来源：评论

学校读者我要写书评

暂无评论

Recovering Reed-Solomon Codes Privately

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2025年 20卷 2807-2821页

作者： Kruglik, Stanislav Kiah, Han Mao Dau, Son Hoang Yaakobi, Eitan Nanyang Technol Univ Sch Phys & Math Sci Singapore 637371 Singapore RMIT Univ Sch Comp Technol STEM Coll Melbourne Vic 3000 Australia Israel Inst Technol Technion Comp Sci Dept IL-3200003 Haifa Israel

We investigate the problems of privately repairing erasures and evaluating their linear combinations for Reed-Solomon codes with low communication bandwidths. We propose two approaches: one based on hiding subspaces used to form parity-check equations, and another based on multiplying parity-check equations with random polynomials. We also derive a lower bound on the repair bandwidth for the single erasure case under reasonable assumptions about the schemes being used and demonstrate the optimality of the proposed schemes for codes of specific lengths.

关键词： Maintenance engineering Reed-Solomon codes Polynomials Bandwidth Codes Symbols Privacy Costs Vectors Finite element analysis distributed storage distributed computing low-bandwidth schemes privacy

来源：评论

学校读者我要写书评

暂无评论

Real-Time Routing in Traffic Simulations: A distributed Event Processing Approach 23

Real-Time Routing in Traffic Simulations: A Distributed Even...

引用

23rd International Symposium on Parallel and distributed computing (ISPDC)

作者： Heinrich, Paul Laudan, Janek Nagel, Kai Tech Univ Berlin Transport Syst Planning & Transport Telemat Berlin Germany

ISBN: (纸本)9798350369205;9798350369199

This paper explores the integration of distributed event processing in the context of real-time routing within a parallel transportation simulation framework for the Multi-Agent Transport Simulation (MATSim). A novel simulation prototype, utilizing Rust and MPI, demonstrates significant reductions in computation time by applying domain decomposition of the network and assigning each part to a separate process. However, sharing and processing events within this setup remains challenging. We present a proof of concept for integrating distributed event processing. Our evaluation has shown that realtime routing significantly increases simulation runtime because uneven distribution of routing requests increases load imbalances and makes speedups less efficient. Sharing event data between processes benefits from smaller subdomains. However, global synchronization for sharing data leads to waiting times introduced by load imbalances.

关键词： Mulit-Agent Transport Simulation distributed computing MPI Real-Time Routing

来源：评论

学校读者我要写书评

暂无评论

Self-propelling, soft, and slender structures in fluids: Cosserat rods immersed in the velocity-vorticity formulation of the incompressible Navier-Stokes equations

引用

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING 2025年 440卷

作者： Tekinalp, Arman Bhosale, Yashraj Cui, Songyuan Chan, Fan Kiat Gazzola, Mattia Univ Illinois Mech Sci & Engn Urbana IL 61801 USA Univ Illinois Carl R Woese Inst Genom Biol Urbana IL 61801 USA Univ Illinois Natl Ctr Supercomp Applicat Urbana IL 61801 USA

We present a hybrid Eulerian-Lagrangian method for the direct simulation of three-dimensional, heterogeneous, active, and self-propelling structures made of soft fibers and operating in incompressible viscous flows. Fiber-based organization of matter is pervasive in nature and engineering, from biological architectures made of cilia, hair, muscles or bones to polymers, composite materials or soft robots. In nature, many such structures are adapted to manipulate flows for feeding, swimming or energy harvesting, through mechanisms that are often not fully understood. While simulations can support the analysis (and subsequent translational engineering) of these systems, extreme fibers' aspect-ratios, large elastic deformations, two-way coupling with three-dimensional flows, and self-propulsion all render the problem numerically challenging. To address this, we couple Cosserat rod theory, where fibers' dynamics is accurately captured in one-dimensional fashion, with the velocity-vorticity formulation of the Navier-Stokes equations, through a virtual boundary technique. The favorable properties of the resultant hydroelastic solver are demonstrated against a battery of benchmarks, and further showcased in a range of multi-physics scenarios, involving magnetic actuation, viscous streaming, biomechanics, multi-body interaction, and untethered swimming.

关键词： Velocity-vorticity formulation Immersed boundary method Cosserat rods Soft body Magnetism Self-propulsion Soft robotics Multiphysics Flow-structure interaction distributed computing

来源：评论

学校读者我要写书评

暂无评论

An efficient data-driven method to construct dynamic service areas from large-scale taxi location data

引用

JOURNAL OF INTELLIGENT TRANSPORTATION SYSTEMS 2025年第1期29卷 1-17页

作者： Nguyen, Minh Hieu Kim, Soohyun Yun, Sung Bum Park, Sangyoon Heo, Joon Yonsei Univ Dept Civil & Environm Engn Seoul South Korea Seoul Inst Technol Dept Urban Strategy Res Seoul South Korea

Service area analysis is crucial for determining the accessibility of public facilities in smart cities. However, the acquisition of service areas using conventional approaches has been limited. First, investigating traffic flow is difficult, as this factor varies significantly over time and space. Second, obtaining service areas of mobile facilities/targets has remained a challenge owing to a lack of data and methods. To address these problems, this study proposes an efficient big-data-driven approach that utilizes large-scale taxi GPS location data collected over two years within Seoul City and distributed computation to obtain the average travel time values on fine-grained grid cells of 100 m x 100 m resolution. On-the-fly visualization methods were then established with an ability to construct isochrone maps of service areas in near-real-time. This enabled performing accurate service area analysis of mobile facilities/targets dynamically. The proposed solution can be effectively used in various applications, such as optimizing the ride-sharing services or the routes of autonomous electric vehicles in future smart cities, as demonstrated in this study.

关键词： big-data-driven method distributed computing dynamic service area isochrone map on-the-fly visualization

来源：评论

学校读者我要写书评

暂无评论

Luby's MIS algorithms made self-stabilizing

引用

INFORMATION PROCESSING LETTERS 2025年 188卷

作者： Giakkoupis, George Turau, Volker Ziccardi, Isabella Univ Rennes Inria CNRS IRISA Rennes France Hamburg Univ Technol Inst Telemat Hamburg Germany Bocconi Univ BIDSA Milan Italy

We reconsider two well-known distributed randomized algorithms computing a maximal independent set, proposed in the seminal work of Luby (1986). We enhance these algorithms such that they become self-stabilizing without sacrificing their run-time, i.e., both stabilize in O (log n ) synchronous rounds with high probability on any n-node graph. The first algorithm gets along with three states, but needs to know an upper bound on the maximum degree. The second does not need any information about the graph, but uses a number of states that is linear in the node degree. Both algorithms use messages of logarithmic size.

关键词： Self-stabilization Fault tolerance distributed computing Maximal independent set (MIS)

来源：评论

学校读者我要写书评

暂无评论

Coded computing for distributed Graph Analytics

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第10期66卷 6534-6554页

作者： Prakash, Saurav Reisizadeh, Amirhossein Pedarsani, Ramtin Avestimehr, Amir Salman Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90089 USA Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

Many distributed computing systems have been developed recently for implementing graph based algorithms such as PageRank over large-scale graph-structured datasets such as social networks. Performance of these systems significantly suffers from communication bottleneck as a large number of messages are exchanged among servers at each step of the computation. Motivated by graph based MapReduce, we propose a coded computing framework that leverages computation redundancy to alleviate the communication bottleneck in distributed graph processing. As a key contribution of this work, we develop a novel coding scheme that systematically injects structured redundancy in the computation phase to enable coded multicasting opportunities during message exchange between servers, reducing the communication load substantially in large-scale graph processing. For theoretical analysis, we consider random graph models, and focus on schemes in which subgraph allocation and Reduce allocation are only dependent on vertex ID while the Shuffle design varies with graph connectivity. Specifically, we prove that our proposed scheme enables an (asymptotically) inverse-linear trade-off between computation load and average communication load for two popular random graph models - Erdos-Renyi model, and power law model. Particularly, for a given computation load r, (i.e. when each graph vertex is carefully stored at r servers), the proposed scheme slashes the average communication load by (nearly) a multiplicative factor of r. Furthermore, for the Erdos-Renyi model, we prove that our proposed scheme is optimal asymptotically as the graph size increases by providing an information-theoretic converse. To illustrate the benefits of our scheme in practice, we implement PageRank over Amazon EC2, using artificial as well as real-world datasets, demonstrating gains of up to 50.8% in comparison to the conventional PageRank implementation. Additionally, we specialize our coded scheme and extend our theore

关键词： Servers Load modeling Computational modeling Resource management Adaptation models Redundancy Encoding Coded computation distributed computing graph algorithms MapReduce PageRank

来源：评论

学校读者我要写书评

暂无评论

Parking problem by oblivious mobile robots in infinite grids

引用

THEORETICAL COMPUTER SCIENCE 2025年 1023卷

作者： Chakraborty, Abhinav Mukhopadhyaya, Krishnendu Birla Inst Technol Mesra Dept Math Ranchi 835215 Jharkhand India Indian Stat Inst Adv Comp & Microelect Unit 203 BT Rd Kolkata 700108 West Bengal India

In this paper, the parking problem of a swarm of mobile robots has been studied. The robots are deployed at the nodes of an infinite grid, which has a subset of prefixed nodes marked as parking nodes. A parking node p(i) has a capacity of k(i), which is given as an input and represents the number of robots it is capable of accommodating. As a solution to the parking problem, in the final configuration, robots need to partition themselves into groups so that each parking node contains a number of robots that are equal to the capacity of the node. It is assumed that the number of robots in the initial configuration equals the sum of the capacities of the parking nodes. The robots are assumed to be autonomous, anonymous, homogeneous, identical and oblivious. They operate under an asynchronous scheduler. They do not have any agreement on the coordinate axes, nor do they agree on a common chirality. All the initial configurations for which the problem is unsolvable have been identified. A deterministic distributed algorithm has been proposed for the remaining configurations, ensuring the solvability of the problem.

关键词： distributed computing Mobile robots Look-compute-move cycle Asynchronous Infinite grids Parking nodes

来源：评论

学校读者我要写书评

暂无评论

distributed Evolutionary computing Migration Strategy by Incident Node Participation 10th

Distributed Evolutionary Computing Migration Strategy by Inc...

引用

10th International Conference on Large-Scale Scientific Computations (LSSC)

作者： Balabanov, Todor Zankinski, Iliyan Barova, Maria Bulgarian Acad Sci Inst Informat & Commun Technol Acad G Bonchev StrBlock 2 BU-1113 Sofia Bulgaria

ISBN: (纸本)9783319265209;9783319265193

distributed evolutionary algorithms are implemented on heterogeneous computing nodes. In a distributed environment it is usual these nodes to differ in operating system and hardware. Such an environment has major problems related to network latency. Some of the evolutionary optimization algorithms are very suitable for distributed computing implementation, because of their high level of parallel scalability. In most cases only fitness function calculation is distributed synchronously (or asynchronously). In this case the population is presented only in the master node. In the next case each separate node has part of the distributed population (it is called island model). The last common model is based on shared memory and each computing node has access to the whole population (it is called fine-grained model). All other models are some hybridization. In the island model there is a common parameter related to migration strategy. The most often used node topology is the ring topology. On a regular basis each node sends its best individual to the next node in the ring. In this paper, a hybrid model, based on incident node participation in star topology, is proposed.

关键词： distributed computing Evolutionary algorithms Migration strategies

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：