Article
Computer Science, Theory & Methods
Xiaoqing Liu, Shuming Zhou, Sun-Yuan Hsieh, Hong Zhang
Summary: This study focuses on measuring the subsystem reliability in multiprocessor systems and compares two different network topologies with the same order, demonstrating a negative correlation between subsystem reliability and dimension n. The research provides a theoretical methodology for choosing the more dependable topology within k-ary n-cube networks with the same order.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2022)
Article
Computer Science, Hardware & Architecture
Xiaoqing Liu, Shuming Zhou, Jiafei Liu, Hong Zhang
Summary: In the big data era, multiprocessor systems are crucial. The effect of processor failure is significant as the probability of such failures increases with system scale. This research establishes an approximation and upper bound for the subsystem reliability of cactus-based networks using a probabilistic fault model and the Principle of Inclusion-Exclusion. Numerical simulations show that the derived upper bound is close to the accurate approximation of subsystem reliability.
Article
Computer Science, Hardware & Architecture
Yanze Huang, Limei Lin, Li Xu, Sun-Yuan Hsieh
Summary: The rapid growth of processors in a multiprocessor system leads to an increase in the probability of faulty processors. The reliability of a multiprocessor system can be measured by the probability of a fault-free subgraph, which effectively characterizes its functionality. This article focuses on the subgraph reliability of (n, k)-arrangement graph An, k under a probabilistic fault model and investigates intersecting modes of subgraphs. The probability of a fault-free (n - 1, k - 1)-subarrangement graph in An, k is analyzed, and the result is close to the asymptotic value under both uniform and nonuniform fault models.
IEEE TRANSACTIONS ON RELIABILITY
(2023)
Article
Computer Science, Hardware & Architecture
Yanze Huang, Limei Lin, Li Xu
Summary: In this research, we establish the probability of subgraph reliability for a multiprocessor system using the probabilistic fault model. We analyze the probability of at least one fault-free subgraph under different fault probabilities and obtain an upper bound. The results show that our upper bound is very close to the lower bound and better than the upper bound obtained from the arrangement graph.
Article
Mathematics, Applied
Baohua Niu, Shuming Zhou, Hong Zhang, Qifan Zhang
Summary: This paper investigates the importance of subsystem reliability assessment and proposes two strategies for measuring the subsystem reliability of complete-transposition networks. By establishing upper and lower bounds as well as an approximation, the robustness of subsystem reliability is investigated and a critical time point for valid bounds is determined. Numerical simulations validate the analytical inferences.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2023)
Article
Computer Science, Hardware & Architecture
Mengjie Lv, Jianxi Fan, Weibei Fan, Xiaohua Jia
Summary: This article explores the subsystem-based reliability in data center networks (DCNs) and how to conduct fault diagnosis. By calculating upper and lower bounds and determining an approximation, it becomes easier to evaluate the network's reliability. The findings serve as a reference for fault diagnosis in other DCNs.
IEEE TRANSACTIONS ON RELIABILITY
(2022)
Article
Computer Science, Information Systems
Yuetai Li, Yixuan Fan, Lei Zhang, Jon Crowcroft
Summary: The centralized system becomes less efficient, secure, and resilient as the network size and heterogeneity increase. Distributed consensus mechanisms characterized by decentralization, autonomy, parallelism, and fault-tolerance can meet the increasing demands of safety and security. This article establishes a Node and Link probabilistic failure model for the RAFT protocol and proposes reliability performance indicators for quick deployment. The impact of failures in a distributed consensus network is evaluated.
IEEE INTERNET OF THINGS JOURNAL
(2023)
Article
Environmental Sciences
Rui Sun, Ming Qiu, Fei Liu, Zhi Wang, Washington Yotto Ochieng
Summary: This paper proposes a dual w-test-based quality control algorithm for integrated IMU/GNSS navigation in urban areas, which effectively improves the navigation performance.
Article
Multidisciplinary Sciences
Viacheslav Kovtun, Ivan Izonin, Michel Gregus
Summary: The article describes the process of the security subsystem countering cyber-physical attacks and proposes a concept for calculating the time to failure as an indicator of the system's reliability. The models and concepts presented in the article are validated through comparison of empirical and simulated data.
SCIENTIFIC REPORTS
(2022)
Article
Computer Science, Hardware & Architecture
Xiao-Yan Li, Yufang Zhang, Ximeng Liu, Xiangke Wang, Hongju Cheng
Summary: Fault diagnosis plays an important role in analyzing the reliability of multiprocessing systems. This paper extends the threshold for regular networks based on probabilistic diagnosis algorithm and determines the status of a cluster of nodes by analyzing local performance. The global performance evaluation based on the Poisson distribution and the Binomial distribution shows good correctness performance. Additionally, the probabilistic diagnosis scheme is applied to explore well-known networks.
Article
Physics, Multidisciplinary
Siyao Yang, Zhenning Cai, Jianfeng Lu
Summary: Two fast algorithms applying the inclusion-exclusion principle to sum bosonic diagrams in bare diagrammatic quantum Monte Carlo and inchworm Monte Carlo method are proposed. These algorithms extend previous work from fermionic to bosonic systems and reduce computational complexity from double factorial to exponential. Numerical experiments validate the theoretical results and efficiency of the methods.
NEW JOURNAL OF PHYSICS
(2021)
Article
Engineering, Mechanical
Pouyan Asem, Paolo Gardoni
Summary: This paper presents a probabilistic empirical model for predicting the permeability of mudstone. The model considers multiple parameters and provides a database that includes various rock parameters affecting permeability.
PROBABILISTIC ENGINEERING MECHANICS
(2022)
Article
Multidisciplinary Sciences
Lantao You, Yuejuan Han, Jianfeng Jiang
Summary: The hypercube Q(n) is a highly symmetrical interconnection network. Variants of Q(n), such as the n-dimensional locally twisted cube LTQ(n), have been proposed to reduce its diameter. To further optimize the diameter, the n-dimensional folded locally twisted cube FLTQ(n) is introduced. Connectivity and super-connectivity are important indicators for fault tolerance and reliability of a network. In this paper, it is shown that the super-connectivity of FLTQ(n) is twice the connectivity.
Article
Engineering, Civil
Sergio Belluco, Flora Faleschini, Lorenzo Hofer, Carlo Pellegrino
Summary: This study investigates the code design formulations for transmission length in Eurocode 2:2020 and fib Model Code 2020, and proposes new coefficients to consider model uncertainties. The results show that the prestress force release methodology has a significant impact on the prediction.
ENGINEERING STRUCTURES
(2023)
Article
Automation & Control Systems
Tat-Thang Le, Minh-Khai Nguyen, Truong-Duy Duong, Caisheng Wang, Sewan Choi
Summary: A new fault-tolerant method for current-fed dual active bridge (CF-DAB) converters with blocking capacitors is proposed in this article to improve the reliability of multiphase bidirectional dc-dc converters. The proposed method is shown to be a practical, simple, low loss, and effective solution.
IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS
(2023)
Article
Computer Science, Theory & Methods
Hoa T. Vu
Summary: This paper addresses the maximum satisfiability problem in the data stream model. It presents algorithms that achieve approximations to the optimum value and corresponding Boolean assignments in sublinear space complexity. The paper also discusses related problems and provides approximation algorithms and space complexity for them.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Sameep Dahal, Jukka Suomela
Summary: This research demonstrates that finding a maximal fractional matching in distributed graph algorithms requires the use of fine-grained fractional values, and gives a specific characterization of the small value requirements, with a denominator of at least 2d. It also provides a new algorithm to meet these requirements.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Peng Yang, Yuan Huang, Zhiguo Fu
Summary: This paper investigates the computational complexity classification of Holant problems on 3-regular graphs and provides corresponding conclusions.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Yi-Jun Chang
Summary: This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks. Recent studies have shown that some problems can be solved with energy-efficient algorithms, while others require significant energy consumption. To improve energy efficiency, this paper focuses on bounded-genus graphs and proposes corresponding algorithms.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Dekel Tsur
Summary: This paper proposes algorithms for 2-CLUB CLUSTER VERTEX DELETION and 2-CLUB CLUSTER EDGE DELETION problems. The algorithms have running times of O*(3.104k) and O*(2.562k) respectively, and were obtained using automated generation of branching rules. These results improve upon previous algorithms for the same problems.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Xianrun Chen, Sai Ji, Chenchen Wu, Yicheng Xu, Yang Yang
Summary: This paper introduces the diversity-aware fair k-supplier problem and presents an efficient 5-approximation algorithm to address the fairness and over-representation issues in facility selection.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara
Summary: Sliding block puzzles play a crucial role in computational complexity, with their complexity varying depending on the rules and set of pieces. In this study, we explore the computational complexities of jumping block puzzles, a newer concept in the puzzle community. We analyze different variants of these puzzles based on real puzzles and a natural model, and determine their complexities. Our findings show that these puzzles are generally PSPACE-complete, with additional cases being NP-complete or solvable in polynomial-time.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar
Summary: This paper studies the many-to-many bipartite matching problem with two-sided preferences and two-sided lower quotas. By defining the concept of critical matching, the goal is to find a popular matching in the set of critical matchings, and an efficient algorithm is proposed to compute a popular matching of the largest size.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Rahul Jain, Raghunath Tewari
Summary: To solve the reachability problem is to determine if there is a path between two vertices in a graph. This paper studies space-efficient algorithms that run in polynomial time to decide reachability. An algorithm is presented that solves reachability in directed graphs using O(n log n) space.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Daniel Berend, Liat Cohen, Omrit Filtser
Summary: The Tower of Hanoi puzzle has been a fascination for mathematicians and theoretical computer scientists for over a century. By using graph theory, we can study connectivity, shortest paths, and other properties of the Hanoi puzzle. Additionally, the Hanoi graphs are related to interesting structures such as the Sierpinski gasket and Gray codes.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Ling Gai, Weiwei Zhang, Zhao Zhang
Summary: This paper studies the problem of selfish bin packing with punishment. Different types of punishments are considered, and it is shown that punishment based on the result can achieve better performance with an upper bound of approximately 1.48 compared to the optimal solution.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Di Wang, Jinhui Xu
Summary: This paper studies the problem of Differentially Private Empirical Risk Minimization (DP-ERM) with both convex and non-convex loss functions. Several new methods are proposed for DP-ERM with smooth convex loss functions, achieving near-optimal expected excess risks while reducing gradient complexity. For DP-ERM with non-convex loss functions, both low and high dimensional spaces are explored, and utility measurements are introduced using different norms and error bounds. The paper reveals that certain non-convex loss functions can be reduced to a level similar to convex loss functions.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Florian Bruse, Maurice Herwig, Martin Lange
Summary: This paper presents a weight measure for formal languages based on the summands of a geometric series discounted by the fraction of words of certain length in the language. It shows that this weight measure is computable for regular languages. As an application, a distance metric between languages is derived as the weight of their symmetric difference, which can be used in automatic grading of standard exercises in formal language theory classes.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Oliver Bachtler, Tim Bergner, Sven O. Krumke
Summary: By studying the almost disjoint paths problem and the separating by forbidden pairs problem, this paper reveals that they have an unbounded duality gap and analyzes their complexity. In addition, for a fixed value of k, an efficient algorithm is proposed to solve the ADP problem.
THEORETICAL COMPUTER SCIENCE
(2024)
Article
Computer Science, Theory & Methods
Elisabeth Remy, Paul Ruet
Summary: This paper studies the extension of the nested canalization property to multivalued functions and investigates the effect of the Van Ham mapping on this property. The study finds that the Van Ham mapping transforms softly nested canalizing multivalued functions into nested canalization Boolean functions, a property that is also relevant in the modeling of gene regulatory networks.
THEORETICAL COMPUTER SCIENCE
(2024)