Algorithm Sample Clauses

Algorithm. We now describe the basic step of the reconciliation mechanism, i.e., the reconcili- ation between two sites on a given object. Section 8 describes when to invoke the reconciliation mechanism, and the options that exist in its use. The basic step is as follows.

Algorithm. We now describe an algorithm that solves Byzantine agree- ment in the basic partially synchronous model when ℓ > n+3t . Our algorithm is based on the algorithm given by Xxxxx, Xxxxx and Xxxxxxxxxx [9] for the classical case where n = ℓ, with several novel features. Generalizing the algo- rithm is not straightforward. Some of the difficulty stems from the following scenario. Suppose two correct processes share an identifier and follow the traditional algorithm of [9]. They could send very different messages (for example, if they have different input values), but recipients of those messages would have no way of telling apart the messages of the two correct senders, so it could appear to the recipients as if a single Byzantine process was sending out contradictory information. Thus, the algorithm has to guard against in- consistent information coming from correct homonym pro- cesses as well as malicious messages sent by the Byzantine processes.

Algorithm. Next, we present an algorithm that solves Byzantine agree- ment assuming ℓ > 3t. Our agreement algorithm is generic: given any synchronous Byzantine agreement algorithm for ℓ processes with unique identifiers (such algorithms exist when ℓ = n > 3t, e.g., [13]), we transform it into an algorithm for n processes and ℓ identifiers, where n ≥ ℓ. Without loss of generality, we assume that the algorithm to be transformed uses broadcasts: a process sends the same message to all other processes. (If a process wishes to send a message only to specific recipients, it could include the recipient’s identi- fier in the broadcasted message.) In our transformation, we divide processes into groups ac- cording to their identifiers. Each group simulates a single process. If all processes within a group are correct, then they can reach agreement and cooperatively simulate a sin- gle process. If any process in the group is Byzantine, we allow the simulated process of that group to behave in a Byzantine manner. The correctness of our simulation re- lies on the fact that more than two-thirds of the simulated processes will be correct (since ℓ > 3t), which is enough to achieve agreement.

Algorithm. Prior to GEMS commencing --------- discussions with the Institutional Review Board ("IRB"), R2 shall confirm in writing to GEMS that the R2 Product algorithm can process the PMA (pre-market approval) cases which are done in feasibility format and that R2 can use them for the PMA submission. In the event that the FDA does not accept these cases for R2's FDA submission, then GEMS and R2 shall negotiate in good faith to determine how to acquire additional cases as outlined in Section 2.8.3.

Algorithm. The shared memory Under x-obstruction-freedom, up to x processes may concurrently progress without preventing termination. As a consequence, in comparison to obstruction-freedom, solving k-set agreement in this setting requires to deal with more contention scenarios. To cope with these additional interleavings of processes, we increase the number of entries in REG . More precisely, REG now contains m = (n − k + x) entries. Ordering the quadruplets In the base algorithm, the four fields of some quadruplet X are the round number X.rd, the level X.ℓvℓ, the conflict flag X.xxℓ, and the value X.val. Coping with x-concurrency requires to replace the last field, which was initially a singleton, with a set of values. Hereafter, this new field is denoted X.valset. In line with the definitions of Section 4.1, let “>” denote the lexicographical order over the set of quadruplets, where the relation ⊐ is generalized as follows to take into account the fact that the last field of a quadruplet is now a non-empty set of values: X ⊐ Y d=ef (X > Y ) ∧ [(X.rd > Y.rd) ∨ (X.xx ℓ) ∨ (X.valset ⊇ Y.valset)]. In comparison to the definition appearing in Section 4, the sole new case where the ordering X ⊐ Y holds is (X > Y ) ∧ (X.valset ⊇ Y.valset). This case captures the fact that, as long as at most x input values are competing at some round, there is no conflict. If such a situation arises, we simply construct a quadruplet that aggregates the different input values. function sup(T ) is % T is a set of quadruplets whose last field is now a set of values % (S1) (S2) (S3) (S4) (S5) (S6) let (r, ℓeveℓ, conf ℓict, valset ) be max(T ); let tuples(T ) be {X | X ∈ T ∧ X.rnd = r}; let values(T ) be {v | X ∈ T ∧ v ∈ X.valset }; let conf ℓict (T ) be conflict ∨ |tuples(T )| > x ∨ |values(T )| > x; % lexicographical order % l et valset be the (at most) x greatest values in values(T ); return (r, ℓeveℓ, conf ℓict (T ), valset ) . Figure 4: Function sup() suited to x-obstruction-freedom Modifications to the sup() function Figure 4 describes the new definition of function sup(). Compared with the original algorithm in Figure 1, it introduces a few modifications (underlined and in blue). Those are detailed below. • Line S1. As pointed out previously, the last field of a quadruplet is now a set of values. The lexicographical ordering over such sets is as follows: sets are ordered first according to their size, and second using some arbitrary order over their elements. By abuse of notation, this ...

Algorithm. We present an oblivious algorithm for solving the point convergence problem. (As we show later, the algorithm solves the point formation problem if the robots are synchronous.) Intuitively, the algorithm solves the problem by achieving the fol- lowing two subgoals at every time instant t: (1) the robots in the same connected component of Gt \get closer" in some sense at t+1, and (2) robots that are mutually visible at t remain mutually visible at t + 1. First of all, at every time instant t, if ri does not see any robot other than itself then ri does not move at t. Otherwise to achieve the rst subgoal, we move ri toward the center ci(t) of the smallest enclosing circle Ci(t) of the positions of all the robots that ri can see, over some distance M OV E to be speci ed below. See Figure 7. If ri moves at t as mentioned above, then we achieve the second subgoal as x x(t) x x Figure 8: Robots ri and rj remain mutually visible. follows. Let rj, i 6= j, be one of the robots that are visible from ri at t. Let mj be the midpoint of ri(t) and rj(t). As is shown in Figure 8, if the next positions of ri and rj are both inside the disc Dj with center mj and radius V =2, then ri and rj can still see each other at t + 1. Formally, given the direction of the move (towards ci(t), as explained above), ri computes the maximum distance `j that it can move in that direction with- out leaving Dj, as follows. If dist(ri(t); rj(t)) = 0, then clearly `j = V =2. Oth- erwise, let dj = dist(ri(t); rj(t)) be the distance between ri and rj at t, and j = 6 ci(t)ri(t)rj(t) the direction of the move of ri with respect to the ray from ri to rj, where 0 j . Then `j = (dj=2) cos j + q(V =2)2 ((dj=2) sin j)2: Robot ri computes this `j for each rj 2 Si(t), and then nds rj 2Si(t) frig f`jg GOAL = dist(ri(t); ci(t)); which is the distance from ri to ci(t) at t. Finally, ri moves over distance M OV E = minfGOAL; XXX IT g towards ci(t). By the de nition of LIM IT , ri remains inside the disc Dj for every rj 2 S after the move. Since all robots compute their next positions using the same algorithm, any pair of robots that are mutually visible at t remain mutually visible at t + 1. That is: Lemma 5 For any two robots ri, rj and any time instant t 0, (ri; rj) 2 Et ! (ri; rj) 2 Et+1. 2

Algorithm. The algorithm consists of two phases. During the first phase, the checkpoint initiator identifies all processes with which it has communicated since the last checkpoint and sends them a request. • Upon receiving the request, each process in turn identifies all processes it has communicated with since the last checkpoint and sends them a request, and so on, until no more processes can be identified. • During the second phase, all processes identified in the first phase take a checkpoint. The result is a consistent checkpoint that involves only the participating processes. • In this protocol, after a process takes a checkpoint, it cannot send any message until the second phase terminates successfully, although receiving a message after the checkpoint has been taken is allowable.

Algorithm. A recursive mathematical formulation or model applied to transform input data streams from a form not suitable to users to output data streams in a form suitable to users by combining, reformatting, calculating, mathematically transforming, adjusting and/or some combination of these manipulations.

Algorithm. The K-medians algorithm is simply the K-means algorithm, using cityblock distance and me- xxxx in place of squared Euclidean distance and mean. Thus, any of the K-means algorithm variations pre- sented (individual-reassignment, batch, or combined) can be used with K-medians. Median definition. If the number of observations (N) is odd, the sample median is the observation in the middle of an ordered list of observations. If the number of observations is even, the sample median is the mean of the two middle observations (Xxxxx, 2002). A cluster median is the vector of the cluster-wise medians for each variable (attribute). For a group of observations with more than one variable, the cluster median is a vector of the group-wise medians for each variable (attribute).

Algorithm. ‌ The CCD algorithm uses the CD decomposition to classify time series. Algorithm 2 im- plements the CCD technique. First, given a matrix X of m time series and a truncation value k, we compute the truncated CD of X (Line 1). As a result of this decomposition, we obtain two matrices, i.e., L which is an n k matrix and R which is an m k matrix. Second, the loading matrix L is mapped to a binary matrix E, where, if li, j > 0, ei, j = 1, otherwise ei, j = 0. Subsequently, each row of Li has a binary representation Ei based on the sign of its elements. The rows with the same sign pattern, and hence the same binary representation, are grouped in the same class (line 3-4). Algorithm 2: CCD(X,k) Input : n m matrix X, k 1 L, R = CD(X, k) ; 2 for i = 1 to n do 3 for j = 1 to k do 4 ei = li, j + 1 ; 2×li, j 2 // ei, j is an element of E 5 for i = 1 to k do 6 classesi = classesi + 2i ×Ei ; 7 return classes;