共查询到20条相似文献,搜索用时 46 毫秒
2.
Taisuke Izumi Akinori Saitoh Toshimitsu Masuzawa 《Journal of Parallel and Distributed Computing》2007
The Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ (Δ-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ-timed uniform consensus problem in presence of fc crash processes and ft timing-faulty processes, and propose a Δ-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ-timed uniform consensus when at least ft+1 correct processes exist in the system. If the system has less than ft+1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as ft+1 processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes requires that the system has at least ft+1 correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to ft timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than ft+1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness. 相似文献
3.
Motivated by the famous 3n+1 conjecture, we call a mapping from Z to Zresidue-class-wise affine if there is a positive integer m such that it is affine on residue classes (mod m). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings. 相似文献
4.
The local b-function bf,p(s) of an n-variate polynomial f∈C[x] (x=(x1,…,xn)) at a point p∈Cn is constant on each stratum of a stratification of Cn. We propose a new method for computing such a stratification and bf,p(s) on each stratum. In the existing method proposed in Oaku (1997b), a primary ideal decomposition of an ideal in C[x,s] is needed and our experiment shows that the primary decomposition can be a bottleneck for computing the stratification. In our new method, the computation can be done by just computing ideal quotients and examining inclusions of algebraic sets. The precise form of a stratum can be obtained by computing the decomposition of the radicals of the ideals in C[x] defining the stratum. We also introduce various techniques for improving the practical efficiency of the implementation and we show results of computations for some examples. 相似文献
5.
Given a graph G, an integer k, and a demand set D={(s1,t1),…,(sl,tl)}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA’06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA’06, with performance ratio O(n2/3logl). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n2/3logk) via greedy approach, improving the previously best known ratio in the literature. 相似文献
6.
7.
This paper aims at investigating properties of homomorphisms which preserve the bordered words. The bordered words are classified into d1-words and d2-words, where the length of the proper border of d2-word is greater than half of it. Some characterizations of d1-word-preserving homomorphism are studied. Some relationships among d-primitivity-preserving homomorphisms, d1-word-preserving homomorphisms, and d2-word-preserving homomorphisms are investigated. We show that every d-primitivity-preserving homomorphism is d1-word-preserving and every d1-word-preserving homomorphism is d2-word-preserving. 相似文献
8.
9.
10.
11.
A real x is called h-bounded computable , for some function h:N→N, if there is a computable sequence (xs) of rational numbers which converges to x such that, for any n∈N, at most h(n) non-overlapping pairs of its members are separated by a distance larger than 2-n. In this paper we discuss properties of h-bounded computable reals for various functions h. We will show a simple sufficient condition for a class of functions h such that the corresponding h-bounded computable reals form an algebraic field. A hierarchy theorem for h-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h-bounded computability for special functions h. 相似文献
12.
13.
The present paper investigates two-parameter families of spheres in R3 and their corresponding two-dimensional surfaces Φ in R4. Considering a rational surface Φ in R4, the envelope surface Ψ of the corresponding family of spheres in R3 is typically non-rational. Using a classical sphere-geometric approach, we prove that the envelope surface Ψ and its offset surfaces admit rational parameterizations if and only if Φ is a rational sub-variety of a rational isotropic hyper-surface in R4. The close relation between the envelope surfaces Ψ and rational offset surfaces in R3 is elaborated in detail. This connection leads to explicit rational parameterizations for all rational surfaces Φ in R4 whose corresponding two-parameter families of spheres possess envelope surfaces admitting rational parameterizations. Finally we discuss several classes of surfaces sharing this property. 相似文献
14.
15.
16.
17.
18.
19.
A collection of T1,T2,…,Tk of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible if there exists a tree T such that each tree Ti can be obtained from T by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(nk) time, n being the number of leaves. Here, we present an O(nf(k)) algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable (FPT) with respect to the number k of trees. 相似文献
20.
Recently, Universum data that does not belong to any class of the training data, has been applied for training better classifiers. In this paper, we address a novel boosting algorithm called UAdaBoost that can improve the classification performance of AdaBoost with Universum data. UAdaBoost chooses a function by minimizing the loss for labeled data and Universum data. The cost function is minimized by a greedy, stagewise, functional gradient procedure. Each training stage of UAdaBoost is fast and efficient. The standard AdaBoost weights labeled samples during training iterations while UAdaBoost gives an explicit weighting scheme for Universum samples as well. In addition, this paper describes the practical conditions for the effectiveness of Universum learning. These conditions are based on the analysis of the distribution of ensemble predictions over training samples. Experiments on handwritten digits classification and gender classification problems are presented. As exhibited by our experimental results, the proposed method can obtain superior performances over the standard AdaBoost by selecting proper Universum data. 相似文献