Arnaud Hamon
email: arnaud.hamon@irccyn.ec-nantes.fr

Yannick Aoustin
email: yannick.aoustin@irccyn.ec-nantes.fr

Cross four-bar structure for the knee of a bipedal robot

Introduction

The objective of this work is to purpose a more efficient joint for the knee of a bipedal robot. Indeed, the biomechanical studies proved the human knee joint is a complex structure which allows a rolling and a sliding movement of the femur on the tibia in the sagittal plain [START_REF] Wilson | Ligaments and articular contact guide passive knee flexion[END_REF]. These movements are guided by the cruciate ligaments and the articular contacts [START_REF] Fuss | Anatomy of the cruciate ligaments and their function in extension and flexion of the human knee joint[END_REF]. These motions cannot be reproduced by one or two revolute joints. In [START_REF] Menschik | Mechanics of the knee-joint. part i[END_REF], authors introduced polycentric knee joint with a four-bar structure to approach the human knee movements. A cross four-bar knee with respect to a revolute knee joint can reduce the energy consumption of a biped, see [START_REF] Hamon | Cross four-bar linkage for the knees of a planar bipedal robot[END_REF]. Moreover, several papers paid interest to the effect of spring equipping the bipedal robot joints [START_REF] Yang | Design and control of a planar bipedal robot ERNIE with parallel knee compliance[END_REF].

We compare the performance of a bipedal robot which uses cross four-bar linkages on the knee joints and we compare the energy consumption of this biped during a walking gait with and without springs on the knee joints. We develop an optimization problem to design optimal walking trajectories with and without springs on the knees. These sets of optimal trajectories show the benefit of springs on the energy consumption for the bipedal robot with cross four-bar knees.

The considered biped is presented on Fig. 1. The cross four-bar is depicted on Fig. 2. The actuated joint is equipped of a spring. The stiffness coefficient k of the spring can be chosen for a desired walking velocity. The objective of this work is to design a set of cyclic reference trajectories on a speed range to compare the energy expenditure of the bipedal robot, with and without springs on the knee joints, during a walking gait. Each step is composed of a single support phase, where the stance foot is in flat contact with the ground, and an impulsive impact.

q 5 q 3 q 2 q 1 q 4 q p1 q p2 Γ p1 Γ p2 Γ 2 Γ 3 Γ 1 Γ 4
To design a walking trajectory, we prescribe the trajectories of each joint of the biped by a cubic spline function with only one knot. This choice allows us to fix initial and final positions and speeds and an intermediate position for each joint. 30 unknown variables are necessary to compute a walking trajectory.

The properties of the impulsive impact give the initial velocities of each joint in function of their final positions and velocities that reduces of 6 the number of unknowns to design a gait. The cyclicity of the trajectories gives the initial positions in function of the final positions that reduces of 6 the number of unknowns. We can compute the final positions of each joint from the final position of the trunk and the length of the step by solving of the inverse geometric model. Finally, we can compute a walking trajectory with 4 variables of configurations, with 6 final velocities and with 6 intermediate positions.

To obtain these 16 variables, we solve, with a SQP method, a parametric optimization problem under constraints to respect the conditions of validity of the gait, such as the unilateral constraint of the biped with the ground, to ensure that the movement is realistic. The criterion of the optimization problem is :

C Γ (x) = 1 d t f 0 Γ T Γdt. (1)
The walking trajectories optimization for a bipedal robot with springs on the knee joints is quite similar than a biped without springs. The difference is on the computation of the articular torques. Indeed, we need to take into account additional torque provided by the spring which depends on the stiffness coefficient of the spring and the position of the knee joint. Moreover, in the definition of the parametric optimization problem we use an additional variable which is the stiffness coefficient of the spring.

Results

With the sets of reference trajectories obtained for the bipedal robot with and without springs on each knee joints, we can compare the energy consumption of the biped in function of the walking velocity. Fig. 4 shows that the springs on the knee joints reduce the energy consumption of the biped during a walking gate.

Figure 1 :

 1 Figure 1: Diagram of the planar bipedal robot. Absolute angular variables and torques.

Figure 2 :

 2 Figure 2: Details of the four-bar linkage with spring on the actuated joint α 1 .

Figure 3 :

 3 Figure 3: Energy consumption of the biped in function of the velocity with and without springs.

2 Figure 4 :

 24 Figure 4: Energy consumption of the biped in function of the velocity with and without springs.


Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@univ-nantes.fr

Sébastien Gambs
email: sebastien.gambs@irisa.fr

Characterizing the Adversarial Power in Uniform and Ergodic Peer Sampling

Keywords: Uniform and ergodic sampling, unstructured P2P, Byzantine adversary

We consider the problem of achieving uniform and ergodic peer sampling in large scale open systems under adversarial behavior. The main challenge is to guarantee that any honest peer is able to construct a uniform and non-definitive (ergodic) sample of the peers identifiers in the system, and this even in the presence of Byzantine peers controlled by the adversary. This sample is built out of a stream of peer identifiers received at each node. We consider and study two types of adversary; an omniscient adversary that has the capacity to eavesdrop on all the messages that are exchanged within the system, and a blind adversary that can only observe messages that have been sent or received by peers he controls. In both models, the adversary can disrupt the input stream by injecting new messages or dropping messages sent by honest peers. Given any sampling strategy, we quantify the minimum effort an adversary has to exert on any input stream to prevent the sampling strategy from outputting a uniform and ergodic sample. We derive lower bounds for both adversary models.

Caractérisation de la puissance d'un adversaire: application à un service d'échantillonnage uniforme et ergodique Résumé : Nous considérons le problème de la mise en oeuvre d'un service d'échantillonnage de noeuds uniforme et ergodic dans des systèmes distribués à très grande èchelle soumis à l'influence d'un adversaire malveillant. Nous étudions deux types d'adversaire : un adversaire omniscient qui est capable d'espionner tous les messages échangés à travers les liens de communication du système, et un adversaire aveugle, qui ne peut observer que les messages transitants par les noeuds sous son contrôle. Dans chacun de ces modèles, l'adversaire peut perturber le flux entrant de chaque noeud par l'injection ou l'effacement de messages. Nous quantifions l'effort minimum qu'un adversaire doit exercer pour empêcher la stratégie d'échantillonnage de générer un échantillon uniforme et ergodique. Enfin, nous dérivons des bornes inférieures pour chacun des modèles d'adversaire considérés.

Mots clés : Echantillonnage uniforme et ergodic, P2P non structurés, adversaire byzantin

Introduction

We investigate the problem of achieving uniform and ergodic peer sampling in large scale open systems in presence of adversarial nodes. Uniform sampling is a fundamental primitive ensuring that any individual in a population has the same probability to be selected as sample. Uniform sampling finds its root in many practical problems such as data collection, dissemination, load balancing and data-caching [START_REF] Bertier | On Gossip and Populations[END_REF][START_REF] Jelasity | Gossipbased Peer Sampling[END_REF][START_REF] Karger | Simple Efficient Load Balancing Algorithms for Peer-to-Peer[END_REF][START_REF] Lv | Search and Replication in Unstructured Peer-to-Peer Networks[END_REF] but achieving uniform sampling in large scale open systems has been shown to be difficult. One of the reasons for this is that the population of these systems is typically very large (e.g., thousand or millions of peers) and displays a very high churn (recent studies on the eDonkey file-sharing network have shown that in average 500, 000 peers connect and disconnect per day [START_REF] Blond | Finding Good Partners in Availability-Aware P2P Networks[END_REF]). Moreover, openness makes unavoidable the presence of adversaries controlling a high number of peers. These adversaries strategize to isolate honest peers within the system by violating randomness assumptions that are at the core of these systems 1 .

By relying on the topological properties of structured peer-to-peer systems, it has been shown that it is possible to guarantee that with high probability any peer is equally likely to appear in the local view of each other honest peer in a number of communication rounds polynomial in the size of the system. One way to achieve this is by imposing peers to frequently depart from their position and move to another random position in the system [START_REF] Anceaume | Dependability Evaluation of Cluster-based Distributed Systems[END_REF][START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF]. In unstructured peer-to-peer systems, peers cannot rely on the topological nature of structured graphs to detect undesirable behaviors. To circumvent this issue, Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] have relied on the properties of min-wise independent permutations, which are fed by the streams of gossiped peer ids and eventually converge towards uniform sampling on the peer ids. However, the resulting sample is definitive in the sense that no other peer id received in the input stream can ever appear in the random sample, which makes this sampling strategy uniform but not ergodic. Informally, the ergodicity property guarantees that each peer id has a nonzero probability to appear infinitely often in a sample. A preliminary step in determining conditions under which uniform and ergodic sampling is achievable in unstructured peerto-peer systems potentially populated with a large proportion of Byzantine peers has been presented in a previous paper [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF]. Briefly, it has been shown that imposing strict restrictions on the number of messages sent by malicious peers during a given period of time and providing each honest peer with a very large memory (proportional to the size of the system) are necessary and sufficient conditions to obtain uniform and ergodic sampling.

In this paper, we propose a characterization of the adversarial power towards biasing uniform and ergodic sampling. By adopting a statistical view of the input stream and by comparing distributions using metrics such as information divergence, we derive lower bounds on the work that the adversary has to exert to bias this input stream such that uniform and ergodic sampling does not hold. We consider and study two models of adversary; the omniscient adversary, that has the capacity to eavesdrop on all the messages that are exchanged within the system, and the blind one that can only observe messages that have been sent or received by peers he controls (i.e.,the malicious ones). To the best of our knowledge, we are not aware of any previous work that has specified and characterized the conditions for which uniform and ergodic sampling is achievable in the presence of adversarial behavior.

The outline of this paper is the following. In Section 2, we give an overview of the existing related work, whereas Section 3 describes the model of the system and the particular assumptions that we make. In Section 4, we describe the functionalities of a sampling component and the properties that it should guarantee while in Section 5, we present some background on information divergence of data-streams. The omniscient and blind adversary models, as well as the characterization of the minimum effort the adversary has to exert to bias the sampling properties, are respectively studied in Sections 6 and 7. Finally, Section 8 presents some concluding remarks.

Related Work

Different approaches have been proposed to deal with malicious behaviors in the peer sampling problem in unstructured overlays. Jesi et al. [START_REF] Jesi | Secure Peer Sampling[END_REF] propose a random sampling algorithm taking explicitly into account malicious peers. Their solution assumes that the ultimate goal of the malicious peers is to mutate the random graph into a hub-based graph, hub for which malicious peers gain the lead. This approach, also adopted in several structured based overlays [START_REF] Singh | Eclipse Attacks on Overlay Networks: Threats and Defenses[END_REF] through auditing mechanisms, or in sensor networks [START_REF] Liu | Detecting Malicious Beacon Nodes for Secure Location Discovery in Wireless Sensor Networks[END_REF], is effective only if the number of malicious peers is very small with respect to the size of the system (i.e., typically of O(log n)). Recently, Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] have proposed a uniform but not ergodic peer sampling algorithm that tolerates up to a linear number of malicious peers. Their sampling mechanism exploits the properties offered by min-wise permutations. Specifically, the sampling component is fed with the stream of peer ids periodically gossiped by peers, and outputs the peer id whose image value under the randomly chosen permutation is the smallest value ever encountered. Thus eventually, by the property of min-wise permutation, the sampler converges towards a random but permanent sample. In a previous work [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF], we show that imposing strict restrictions on the number of messages sent by malicious peers during a given period of time and providing each honest peer with a very large memory (proportional to the size of the system) are necessary and sufficient conditions to obtain uniform and ergodic (non permanent) sampling. It is worth noting that our results complement two previous results [START_REF] Busnel | A Formal Characterization of Uniform Peer Sampling Based on View Shuffling[END_REF][START_REF] Gurevich | Correctness of Gossip-Based Membership under Message Loss[END_REF], in which an analysis of the class of uniform and ergodic sampling protocols is presented. Both previous work provide a complete analytical proof of a gossip-based protocol that reaches both uniformity and ergodicity, but in contrast to the present work, adversarial behaviors were not considered. Finally, taking a completely different approach from the previously mentioned papers, which are based on gossip algorithms or on distance function properties, the techniques presented in [START_REF] Yu | SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks[END_REF][START_REF] Yu | SybilGuard: Defending against Sybil Attacks via Social Networks[END_REF] rely on social network topologies to guard against Sybil attacks. Both protocols take advantage of the fact that Sybil attacks try to alter the fast mixing property of social networks to defend against these attacks. However, in presence of malicious peers with a high degree, the performance of both protocols degrade drastically.

System Model

Model of the Network. We consider a system populated by a large collection of peers in which each peer is assigned a unique and permanent random identifier from an m-bit identifier space. Peer identifiers (simply denoted ids in the following) are derived by applying some standard strong cryptographic hash function on peers intrinsic characteristics. The value of m (128 for the standard MD5 hash function) is chosen to be large enough to make the probability of identifiers collision negligible. The system is subject to churn, which is classically defined as the rate of turnover of peers in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF]. Each peer knows only a small set of peers existing within the system and this knowledge generally varies according to the activity of the system. The particular algorithm used by peers to choose their neighbors and to route messages induces the resulting overlay topology. In this work, we consider only an unstructured overlay. Unstructured overlays are assumed to conform with random graphs, in the sense that relationships among peers are mostly set according to a random process. Note that in the following we indifferently use both terms node and peer.

Adversary. We assume the presence of malicious (i.e., Byzantine) peers that try to manipulate the system by exhibiting undesirable behaviors. In our context, this amounts to dropping chosen messages and injecting new ones to bias the sample list maintained by non malicious peers. We model malicious behaviors through an adversary that fully controls these malicious peers. The adversary cannot control more than a fraction k (0 < k < 1) of malicious peers in the whole system. A node that is not malicious is said honest. We distinguish between two models of adversary. The omniscient adversary model that represents an adversary that is able to eavesdrop all messages exchanged within the system, and the blind adversary model that represents an adversary that can only observe messages sent or received by malicious nodes. In both models, we assume that the adversary cannot tamper with the content a message exchanged between two honest nodes without being detected. This is achieved by the means of a signature scheme that ensures the authenticity and integrity of messages.

Sampling Assumptions. Similarly to Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF], we assume that there exists a time T 0 such that after that time, the churn of the system ceases. This assumption is necessary to make the notion of uniform sample meaningful. Thus from T 0 onwards, the population of the system S is composed of n 2 m nodes, such that at least (1 -k)n of them are honest and no more than kn of them are controlled by the adversary. The subset of honest nodes in the overlay is denoted by N and we assume that all the nodes in N are weakly connected from time T 0 onwards.

Sampling Component

Following the lines of [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF], each node u ∈ N has locally access to a sampling component2 as presented in Figure 1. The sampling component implements a strategy s and has uniquely access to a data structure Γ u , referred to as the sampling memory. The size of the sampling memory Γ u is bounded and is denoted by |Γ u |. The sampling component S s u is fed with a stream < v i , v j , . . . > of (possibly non unique) node ids that correspond to the node ids periodically received by node u ∈ N (e.g., through gossip algorithms, or random walks for instance). The fingerprint of an input stream is a collection of weighted points in which each node id is weighted by the number of times this node id appears in the stream. Specifically, a stream of node ids can be summarized by < (v 1 , m 1 ), . . . , (v n , m n ) >, where v i denotes the identifier of a node in S and m i ∈ N represents the number of times v i appears in the stream.

At each time t, the following three steps are atomically executed: the first element of the stream, say node id v, is given as input to the sampler component. The sampling component S s u reads v, and removes it from the stream. According to its strategy s, S s u may store or not v in Γ u and outputs at most one node id. For example, the strategy s may consist in storing v if Γ u is not full, or in substituting v for a randomly chosen node id that belongs to Γ u , or in simply dropping v. The output at time t, denoted S s u (t), is chosen among the node ids in Γ u according to strategy s. For instance, strategy s may consist in choosing the smallest node id in Γ u , or the smallest node id under a given min-wise permutation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]. The maximum finite hitting time needed for the sampling component S s u to reach a uniform sample is denoted by T s . Clearly, T s depends on the strategy s implemented by the sampling component and also on the stream of node ids the sampling component is fed with. We assume that the sampling strategy is known by the adversary in the sense that the algorithm used is public knowledge. However, if the algorithm is a randomized one, the adversary has not access to the local random coins used by the honest peers.

Finally, δ represents the number of node ids injected by the adversary in the input stream of node u during the time interval T s . Note that it does not matter whether the injected node ids correspond to the ids of malicious nodes or not as the unique goal of the adversary is to bias the input stream in such a way that whatever the strategy s of the sampler component, its output S s u (t) cannot guarantee both the uniform and ergodic properties [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF]. More precisely, these properties are defined as follows Property 4.1 (Uniformity) Let N be a weakly connected graph from time T 0 onwards, then for any time t ≥ T s , for any node v ∈ S, and for any node u ∈ N ,

P[v ∈ S s u (t)] = 1 |S| .
Property 4.2 (Ergodicity) Let N be a weakly connected graph from time T 0 onwards, then for any time t ≥ T s , for any node v ∈ S, and for any node u ∈ N ,

P {t |t > t ∧ v ∈ S s u (t )} = ∅ = 0,
where ∅ represents the empty set.

Uniformity states that any node in the overlay should have the same probability to appear in the sample of honest nodes in the overlay, while ergodicity says that any node should have a non-zero probability to appear infinitely often in the sample of each honest node in the overlay. Note that uniformity by itself does not imply ergodicity, and vice versa. Indeed, the former does not impose any restriction on the freshness of output node ids, while the latter one does not provide any guarantee regarding the equiprobability of node ids to be chosen as samples. Moreover, as each node v in S has a non-zero probability to be returned by S s u (t) at time t, u must appear at least once in the input stream. Thus, ∀v ∈ S, starting from time T s , m v > 0.

Note that the analysis presented in this paper is independent from the way the stream of node ids at each node u has been generated. That is, it may result from the propagation of node ids through gossip-based algorithms (namely through push, or pull or push-pull mechanisms initiated by u and its neighbors), from the node ids received during random walks initiated at u, or even from induced churn.

Information Divergence of Data Streams

A natural approach to detect changes on data streams is to model it as a distribution and to compute the distance between the observed stream and the ideal one. The distance we use in our context is the Kullback-Liebler (KL) divergence (sometimes called the relative entropy [START_REF] Cover | Elements of information theory[END_REF]).

Definition 5.1 (Kullback-Liebler divergence) Given two probability distributions on events p = {p 1 , . . . , p n } and q = {q 1 , . . . , q n }, the Kullback-Liebler divergence between p i relative to q i is defined as the expected value of the likelihood ratio with respect to q i :

D(p||q) = n i=1 p i log 2 p i q i (1) = H(p, q) -H(p), (2)
where H(p) = -p i log 2 p i is the (Shannon) entropy of p and H(p, q) = -p i log 2 q i is the cross entropy of p and q (by convention, 0 log 2 0 = 0).

The KL-divergence is a member of a larger class of distances known as the Ali-Silvey distances [START_REF] Ali | General Class of Coefficients of Divergence of One Distribution from Another[END_REF]. For the sake of clarity, we will use the notation log to denote the logarithm in base 2 for the rest of this paper. Definition 5.2 (τ -closeness) A stream of node ids σ is τ -close if the KL-divergence between the uniform probability distribution p (U ) and the probability distribution q corresponding to σ is below or equal to a robustness threshold τ .

Given two probability distributions, the Earth Mover's Distance (EMD) [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] measures the minimal amount of work needed to transform one distribution to another by moving the probability mass between events. We rely on this metric to quantify the effort that an adversary exerts to bias the input stream. In our context, a unit of work corresponds to dropping one id and to pushing another id instead in the input stream.

Omniscient Adversary Model

In this section, we study the behavior of an omniscient adversary, which has the capacity to eavesdrop on all the messages sent and received by all the nodes in S. In the following, we demonstrate that the strategy that pushes all the probability mass over a single id is the one that maximizes the bias of the input stream so that it becomes far from the uniform distribution. We also describe an optimal strategy on how to achieve it.

In the following, we consider input streams of length T s observed from time T 0 . Let σ be a stream such that the id of each node in S appears exactly once in the stream, except for a unique id that appears in all the remaining slots. Therefore, we have ∃v i ∈ S, m v i = T s -(n-1) and ∀v j = v i ∈ S, m v j = 1. The following theorem states that the probability distribution associated to this particular stream is the one that has the maximal divergence from the uniform distribution. In the following, notation [1. . n] denotes the set {1, 2, . . . , n}. Theorem 6.1 (Maximal divergence from the uniform distribution) Let p (U ) be the uniform distribution corresponding to a uniform stream, i.e., ∀i ∈ [1.

. n], p

(U ) i = 1
n , and q be the probability distribution corresponding to σ, i.e., ∃v i ∈ S, q v i = Ts-(n-1) Ts and ∀v j ∈ S, v j = v i , q v j = 1

Ts . Then, for any possible probability distribution q,

D(p (U ) ||q) ≤ D(p (U ) ||q).
Proof. Let q be the probability distribution representing any valid input stream on (T 0 , T s ].

We have ∀v i ∈ S,

q v i = mv i
Ts , where m v i is the number of times v i is present in the input stream. Therefore,

D(p (U ) ||q) = H(p (U ) , q) -H(p (U ) ) = n i=1 p (U ) i log p (U ) i - n i=1 p (U ) i log m v i T s = log T s n - 1 n log n i=1 m v i .
Therefore, maximizing D(p (U ) ||q) amounts to minimizing log ( n i=1 m v i ). We characterize the stream that minimizes n i=1 m v i under the following constraints:

     1 ≤ m v i ≤ T s with 1 ≤ i ≤ n, n i=1 m v i = T s . (3)
From this set of constraints, we immediately have 1 ≤ m v i ≤ T s -(n -1). To relax the second constraint, we pose

m vn = T s - n-1 i=1 m v i . Let function f be such that f (m v 1 , . . . , m v n-1 ) = T s - n-1 i=1 m v i n-1 i=1 m v i = m v j   T s -m v j - n-1 i=1,i =j m v i   n-1 i=1,i =j m v i .
Function f is differentiable on its domain

I s = [1. . T s -n + 1] n-1 , thus we get df dm v j (m v 1 , . . . , m v n-1 ) =   T s -2m v j - n-1 i=1,i =j m v i   n-1 i=1,i =j m v i . We have df dm v j ≥ 0 ⇔ m v j ≤ T s -n-1 i=1,i =j m v i 2 < T s -(n -1).
Function f is then a paraboloid, which first increases then decreases, and then reaches its minimum on the domain's boundary. As f is symmetric and all m v j variables are independent, the minimum for each m v j can be determined separately. The minimum for a particular m v j is reached when m v j = 1 or m v j = (T s -n + 1). That is,

   f (m v1 , . . . , 1, . . . , m vn-1 ) = n-1 i=1,i =j m vi T s -1 - n-1 i=1,i =j m vi f (m v1 , . . . , T s -n + 1, . . . , m vn-1 ) = (T s -n + 1) n-1 i=1,i =j m vi n -1 - n-1 i=1,i =j m vi f (m v1 , . . . , T s -n + 1, . . . , m vn-1 ) = n-1 i=1,i =j m vi   (T s -n + 1)   n -2 - n-1 i=1,i =j m vi   + T s -n + 1   = n-1 i=1,i =j m vi   (T s -n)   n -2 - n-1 i=1,i =j m vi   + T s -1 - n-1 i=1,i =j m vi   . As ∀i, m v i ≥ 1, we have n -2 -n-1 i=1,i =j m v i ≤ 0. Moreover, as T s ≥ n, we have f (m v 1 , . . . , T s -n + 1, . . . , m v n-1 ) ≤ f (m v 1 , . . . , 1, . . . , m v n-1 ) and therefore the minimum is reached for m v j = T s -n + 1. From the set of constraints (cf. Relation (3)), if the maximum of D(p (U ) ||q) is reached for m v j = T s -n + 1 then n i=1,j =j m v i = n -1 implies that ∀i ∈ [1..n], i = j, m v i = 1, which concludes the proof.
This allows us to formulate an upper-bound D max on the KL-divergence between the uniform stream and any other stream:

D max = D(p (U ) ||q) = log T s n - 1 n log (T s -n + 1) . ( 4
)
Thus any input stream σ is D max -close (cf. Definition 5.2).

To determine the minimal effort that the adversary has to exert to bias the input stream so that both uniformity and ergodicity properties do not hold, we use the Earth Mover's Distance (EMD) between the uniform distribution and the target one. In the following when we say that the adversary replaces the node id v i by v j , we mean that he drops v i from the input stream and inject v j instead. Lemma 6.2 (Optimal strategy to maximize the divergence) Given an input stream σ, replacing the less frequent id in σ with the most frequent one maximizes the gain in KLdivergence with respect to the uniform distribution for the same amount of work as measured by the EMD distance.

Proof. Given an input stream σ represented by the probability distribution q, we construct the input stream σ from σ by substituting one occurrence of node id v i with node id v j so that D(p (U ) ||q ) is maximized after this replacement (where q denote the probability distribution representing σ ). This amounts to maximizing D(p (U ) ||q ) -D(p (U ) ||q) . Recall that all node ids in S must be present in σ . Therefore, we search for the node id pair (v i , v j ) such that

             m v j = m v j + 1 m v i = m v i -1 v j = arg max v j ∈S log 1 q v j -log 1 qv j v i = arg max v i ∈S log 1 q v i -log 1 qv i Collection des Publications Internes de l'Irisa c IRISA leading to    v j = arg max v j ∈S 1 -1 mv j +1 = arg min v j ∈S 1 mv j +1 = arg max v j ∈S m v j v i = arg max v i ∈S 1 + 1 mv i -1 = arg max v i ∈S 1 mv i -1 = arg min v i ∈S m v i
Thus the optimal node id replacement that maximizes the KL-divergence gain is obtained by replacing the less frequent node id v i with the most frequent one v j .

Algorithm 1 shows an optimal implementation of Lemma 6.2 with respect to the number of performed replacements. This algorithm is run by the adversary. Specifically, the inputs of the algorithm are τ s and an input stream σ that will feed the sampler component S s u of node u. Recall that τ s is the robustness threshold of the sampling strategy s implemented by S s u , i.e., for any τ s -close input stream σ, the sampling strategy s is capable of outputting a uniform and ergodic sample. The goal of the greedy Algorithm 1 is to tamper with the input stream σ in order to increase its KL-divergence above τ s with a minimum effort.

Algorithm 1: Adversary biasing strategy

Data: an input stream σ, the robustness threshold τ s Result: the number of replacements if it exists if τ s ≥ D max then 1 return "fail"

2 else 3 ← 0; 4 v j ← arg max v j ∈S m v j ; 5 while D(p (U ) ||q σ ) ≤ τ s do 6 v i ← arg min {v∈S:mv i =1} m v i ; 7 let k be the index of an id such that σ[k] = v i ; 8 σ[k] ← v j //one occurence of v i is dropped and v j is injected instead ; 9 ← + 1; 10 return 11
By assumption, the adversary is omniscient and therefore has the capacity to observe the entire input stream σ. From Section 4, the adversary knows the strategy s of the sampler, and thus can compute the value of τ s . The value of the maximum divergence D max is computed as Relation (4). If D max is greater than or equal to the robustness threshold, the algorithm returns "fail". Otherwise at each iteration, the adversary performs the optimal id replacement until the KL-divergence exceeds the robustness threshold. Note that at lines (8) and ( 9) both m v i and m v j are updated. The counter returned by Algorithm 1 represents the number of replacements done by the adversary.

Consider s a sampling strategy, τ s its robustness threshold, and σ an input stream. Let be the number of replacements executed in Algorithm 1. We denote q σ( ) the probability distribution derived from σ after these optimal replacements. Corollary 6.3 (Lower bound on the effort exerted by an omniscient adversary) The minimum number of replacements an omniscient adversary has to apply to exceed τ s is

δ = inf ∈ N : D(p (U ) ||q σ( ) ) > τ s . (5)

Blind Adversary Model

In this section, we study the behavior of a blind adversary, that is an adversary that only has the capacity to observe messages sent or received by the nodes he controls. A strategy that the adversary might apply to bias the input stream is to choose a node id (possibly one that belongs to a malicious node but not necessarily) and to push it in the input stream as much as possible. We show that this strategy is optimal and we give the lower bound on the expected minimum amount of work a blind adversary has to exert to bias the input stream.

Theorem 7.1 (Lower bound on the expected effort exerted by a blind adversary) Let s be a sampling strategy, τ s its robustness threshold and T s the maximum convergence time of s. The minimum number of replacements a blind adversary has to apply to exceed τ s in expectation is given when the input stream is the uniform one. We have

δ = inf ∈ I s : 1 n -1 Ts n -1 log T s n + 2 log (T s ) -log (T s + n ) -log T s -n 1 + ( -1) mod T s n -1 > τ s (6)
where

I s = 0..T s -n + 1 -Ts n .
Proof. Let us consider the uniform node ids stream on a window of length T s . For any v i ∈ S, v i is present in the stream T s /n in average. Thus the probability distribution p (U ) is such that ∀v i ∈ S, p

v i = 1/n. From the previous section, we have seen that the optimal strategy for the adversary to bias an input stream is to replace the less frequent node id in this stream with the most frequent one. By assumption, the adversary is blind and cannot observe all the node ids of the input stream. Thus the strategy the adversary applies consists choosing a specific node id v j and repeatedly pushes v j in the input stream. Let σ be an input stream and σ be the stream obtained from σ after one step of this adversarial strategy (i.e., replacing v i by v j for some v i ∈ S). We have

D(p (U ) ||q σ ) -D(p (U ) ||q σ ) = 1 n log m vj m vj + 1 + log m vi m vi -1 (7)
where q σ and q σ represent respectively the probability distributions of σ and σ . In the following, q σ( ) denotes the probability distribution derived from σ after replacements. Given a sampling strategy s, we prove by induction on the number of optimal replacements that, starting from a uniform stream, the maximum KL-divergence after replacements is given by

D(p (U ) ||q σ( ) ) = 1 n -1 Ts n -1 log T s n + 2 log (T s ) -log (T s + n ) -log T s -n 1 + ( -1) mod T s n -1 . (8)
Note that cannot be greater than T s -n + 1 -Ts n . Indeed, all node ids in the initial uniform stream are present at least Ts n times and the maximum number of times a unique id can appear in the stream is (T s -n + 1). For = 1, the claim immediately holds from Equation 7. Now, assume that the claim also holds for all 1 ≤ k ≤ . We show that the claim holds for k = + 1. The KL-divergence with respect to the uniform stream after + 1 steps is

D(p (U ) ||q σ( +1) ) = D(p (U ) ||q σ( ) ) + D(p (U ) ||q σ( +1) ) -D(p (U ) ||q σ( ) ). (9)
D(p (U ) ||q σ( ) ) is given by Equation 8, and D(p (U ) ||q σ( +1) ) -D(p (U ) ||q σ( ) ) represents the gain of step ( + 1). Two sub-cases need to be considered: (i) mod Ts n -1 = 0 and (ii) mod Ts n -1 = 0. Case (i ): the less frequent node id v i in the stream at step + 1 is the same as the one removed at step . After steps, m v j = Ts n + and m v i = Ts n -1 + ( -1) mod

-1 + ( -1) mod Ts n -1 -1 = 1 n log (T s + n ) -log (T s + n( + 1)) + log T s -n 1 + ( -1) mod T s n -1 -log T s -n 2 + ( -1) mod T s n -1 .
By assumption (i), and 1 + ( -1) mod Ts n -1 = mod Ts n -1 . From Equation 9, we get

D(p (U ) ||q σ( +1) ) = 1 n Ts n -1 log T s n + 2 log (T s ) -log (T s + n( + 1)) -log T s -n 1 + mod T s n -1 ,
which ends Case (i ).

Case (ii ). The argumentation is the same as above. However, as mod Ts n -1 = 0, the node id that has been previously replaced is now present exactly once in the stream. Thus the adversary needs to randomly choose another node id in the stream before processing the next step of his strategy. Thus applying Equation 7 at step + 1 gives

D(p (U ) ||q σ( +1) ) -D(p (U ) ||q σ( ) ) = 1 n log Ts n + Ts n + + 1 + log Ts n Ts n -1 . ( 10
)
By assumption ( -1) mod Ts n -1 = Ts n -1 -1 , and by combining the induction hypothesis 8 with the gain obtained at step + 1 (Equation 10) we get

D(p (U ) ||q σ( +1) ) = 1 n      -1 Ts n -1 log T s n + 3 log (T s ) -log (T s + n( + 1)) -log (T s -n) -log (n)     
.

By assumption of the case we have + 1, which proves the induction:

D(p (U ) ||q σ( +1) ) = 1 n Ts n -1 log T s n + 2 log (T s ) -log (T s + n( + 1)) -log T s -n 1 + mod T s n -1 .
As a conclusion, any value of that allows the adversary to exceed the robustness threshold τ s defeats the sampling strategy. Thus, the minimum number of replacement operations δ is the lower bound of this set of values.

We now evaluate the minimum amount of work a blind adversary has to exert, in the worst case, to bias the input stream. In the worst case, the node id v i the adversary has chosen to blindly flood might be initially present only once in the input stream. In order to bias the input stream, the adversary needs to push id v i sufficiently often so that the probability of appearance of id v i reaches the uniform value, with respect to all the other node ids, and then to continue to push this id δ times so that the divergence between the resulting stream and the uniform one is maximum. Theorem 7.2 (Lower bound on the effort exerted by a blind adversary) Let s be a sampling strategy, τ s its robustness threshold and T s the maximum convergence time of s. The minimum number of replacements the adversary has to apply on a stream, in the worst case, to exceed τ s is δ +

T s n - 1
Proof. The proof is immediate. First, the adversary has to raise the chosen id at least up to the uniform value. As in the worst case, this id is present only once in the initial stream, this costs Ts n -1 replacements to reach a number of occurrences equals to Ts n . Moreover, once this id is present in the modified stream Ts n times, the adversarial follows the same strategy as before, which requires δ more steps to guarantee that the robustness threshold τ s is exceeded. Note that this value is a worst-case bound and not the exact minimum value with respect to τ s because after the first ( Ts n -1) steps, the modified stream could be different from the uniform one. In this situation, the KL-divergence to the uniform stream is strictly greater than 0, reducing accordingly the amount of work of the adversary to exceed τ s .

Concluding Remarks

In this paper, we have focused on the problem of achieving uniform and ergodic peer sampling in large scale open systems potentially populated with malicious peers. This problem consists in guaranteeing that the knowledge of the system maintained by each honest peer is a uniform and non permanent sample of the whole population of the system. By modeling input streams as probability distributions, we have characterized the minimum effort (measured in terms of node ids' replacements) that an omniscient and a blind adversary have to exert on the input stream of node identifiers to exceed the robustness threshold that quantifies the power of a sampling strategy. Similarly to (pseudo)-random number generators that are considered as the basic mathematical tool to generate complex probability distributions, we believe that uniform peer sampling should be regarded as a necessary building block to derive larger classes of sampling schemes. This building block is of utmost importance in systems in which the population is continuously evolving and thus, where it is impossible to capture the full complexity of the network through global snapshots. In our context, this dynamicity is exploited by the adversary to bias the peer sampling by over-representing targeted peers. We conjecture that there exists a total order relationship on the power of ergodic (resp. non ergodic) uniform sampling strategies with respect to their robustness threshold τ . This can be depicted by using a planar representation as shown by Figure 2. Each τ -radius circle in this picture represents the class of τ -close uniform sampling strategies. For instance, in this representation the strategy proposed by Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] belongs to the largest circle corresponding to τ = ∞ on its non ergodic part (left side). As another illustrative example, the sampling strategy proposed in Busnel et al. [START_REF] Busnel | A Formal Characterization of Uniform Peer Sampling Based on View Shuffling[END_REF] should be ranked as less powerful than the one proposed by Gurevich et al. [START_REF] Gurevich | Correctness of Gossip-Based Membership under Message Loss[END_REF] since the latter one achieves uniform and ergodic sampling despite message loss contrary to the former one. Both strategies would appear in the ergodic part of the representation (right side). Finally, we think that this classification can be used as a tool to precisely compare any two sampling strategies as different as they are (e.g., [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF] and [START_REF] Massoulié | Peer Counting and Sampling in Overlay Networks: Random Walk Methods[END_REF]). As future work, we intend to rank the state-the-art sampling algorithms in the light of this new framework. Moreover, we plan to extend this work by integrating other dimensions, such as space and time resources, and deterministic versus probabilistic strategies.

Figure 1 :

 1 Figure 1: Sampling component of node u ∈ N .

Figure 2 :

 2 Figure 2: Characterization of Sampling Strategies

Collection des Publications Internes de l'Irisa c IRISA

Although malicious nodes have also access to a sampling component, we cannot impose any assumptions on how they feed it or use it as their behavior can be totally arbitrary.


F Servant

J P Brison

A Sulpice

C Opagiste

V Madigou

P Lejay

Crystal growth and characterization of the ruthenate superconducting compound: Sr 2 RuO 4

Keywords: 71.27.+a, 74.25.Ha, 74.70._b, 74.70.Pq Keywords: A2. Floating zone technique, A2. Growth from melt, A2. Single crystal growth, B1. Oxides, B1. Perovskites, B2.Superconducting materials

Sr 2 RuO 4 is a copper-free layered perovskite superconductor with the tetragonal K 2 NiF 4 -type structure. The precise nature of the pairing in the superconducting state of this material is still under debate. In this paper, we report about crystal growth and characterization of this compound. The crystals were grown by a floating zone technique using a light furnace equipped with double elliptical mirrors starting from off-stoichiometric Sr 2 RuO 4 . The crystals have been checked by X-ray diffraction and microanalysis. The superconducting properties were measured by AC-susceptibility, magnetization and specific heat. High crystalline quality centimetre-sized crystals have been grown and best crystals exhibit superconducting transitions at Tc = 1.3K (typical dimensions: 4.5mm diameter and 70mm length with the (0 0 1) axis perpendicular to growth direction). The unconventional superconductors are characterized by a drastic impurity effect on the superconducting properties. We try to establish a correlation between the defect concentration and the physical properties of Sr 2 RuO 4 .

Introduction

Sr 2 RuO 4 still appears to be the only non cuprate layered-perovskite superconductor known to date. Sr 2 RuO 4 shares the same K 2 NiF 4 structure as the La-based cuprates superconductors. This structure can be built up by three perovskite monolayers stacked along the resulting c-axis where the layers 1 and 3 are SrRuO 3 perovskite strontium-centred units, while layer 2 is ruthenium-centred.

Removing two RuO 2 layers lead to the K 2 NiF 4 type structure [1][2][3]. For n =1; this compound is a member of the Ruddlesden-Popper series: Sr n+1 Ru n O 3n+1 which includes Sr 3 Ru 2 O 7 and SrRuO 3 , respectively, for n = 2 and ∞.

Research works performed, since its physical properties study [4,5], have firmly shown unconventional superconducting properties at almost Tc = 1.5K: As the heavy fermions systems, Journal of Crystal Growth 275 (2005) e739-e743 p2/7 Sr 2 RuO 4 is not s-wave type superconductor [6]. The main consequence is the non-magnetic impurity effect at very low concentration, which sharply drops the superconducting temperature to zero [7,8].

In this paper, we report about the crystal growth experiment using the floating zone technique at ambient pressure in an image furnace. The single crystals are characterized by electronic microprobe analysis, X-ray powder and Laue diffraction, their mosaic has been measured by synchrotron diffraction.

The important problem of Sr 2 RuO 4 , in the sample preparation, is to obtain the superconducting state which appears to be extremely brittle due to a drastic impurity effect. The superconducting properties were measured by specific heat, alternative-current susceptibility using a standard mutualinductance technique in a 3He refrigerator and the magnetization measurements were performed on a SQUID magnetometer.

We discuss the relation between the superconducting properties and the presence of various defects in Sr 2 RuO 4 single crystals.

Experimental procedure

Single crystals were grown by the floating zone method. Feed and seed rods were prepared by high temperature solid state reaction. Powders of SrCO 3 (5N) and RuO 2 (3N) were used as starting materials. Due to the high volatility of RuO 2 during the growth process, the molar starting composition was 2:1.15 for SrCO 3 and RuO 2 , respectively. The mixture was twice hydrostatically pressed at 10 kbars and sintered in air at 1300°C for 24 h with an intermediate grinding to improve the sample homogeneity. The cylindered samples were placed on rods of the same chemical composition to prevent contamination from the alumina crucible. The final rods dimensions were 5mm length for 80mm long.

A non commercial double-elliptical light furnace (equipped with two 1500W halogen lamps) has been used for growing the Sr 2 RuO 4 single crystals. The atmosphere was composed of high quality oxygen (40%) and argon (60%) at room pressure. The feeding rod and the seed were inversely rotated at 10 rpm. To limit the RuO 2 evaporation, the growth speed was typically kept between 2 and 4 cm/h.

Results

Several single crystals with typical size of 4-5mm diameter and 10-70mm length were successfully grown. During each process, two large 180° opposite shiny facets were developed parallel to the growth direction (Fig. 1). Each growth has been checked by powder X-ray diffraction on crushed p3/7 small parts of the crystal. To optimize the physical properties of Sr 2 RuO 4 , several parameters have been adjusted. First we studied, with a fixed rods chemical stoichiometry, the influence of the atmosphere composition at room pressure. A wide range of gas mixture has been tested : from 6% to 100% of oxygen in argon. It appeared that this parameter is not relevant to the superconducting properties of Sr 2 RuO 4 . We concluded that the oxygen partial pressure did not affect both the RuO 2 evaporation level during the melt and the final oxygen stoichiometry of Sr 2 RuO 4 . It has to be noted that annealing the crystals at different temperature under various atmospheres never improved the superconducting properties of Sr 2 RuO 4 too. The molar ratio of the starting material was 2:1.15 for, respectively, SrCO 3 and RuO 2 . To compensate precisely the RuO 2 loss during melt, the growth rate has to be carefully adjusted to obtain a final pure phase. For this chemical composition, a fixed rods diameter (i.e. a constant volume of the melt) and a fixed rotation speed, we studied the influence of the pulling speed of the growth on the phase purity. The optimal speed, giving the best critical temperature, was 4 cm/h, Fig. 3 shows the influence of the growth speed on the superconducting temperature measured by ACsusceptibility. This rather rapid growth of the crystal was necessary to optimize the RuO 2 stoichiometry. This could probably produce internal defects in the crystal but the measured mosaic on the crystals being very fairly good and more curiously annealing never improved the superconducting temperature. Due to the increase of the RuO 2 concentration in the starting polycrystalline materials, and in regards to the pseudo-binary diagram (SrO-RuO 2 ), it is possible to form Sr 3 Ru 2 O 7 and SrRuO 3 as impurity phases or epitaxial-like intergrowth.

With Sr 2 RuO 4 , those two last materials are in a crystallographic relation according to the Ruddlesden-Popper series. A very small amount of these phases could be detected by X-ray diffraction if the excess of RuO 2 was not compensated by its evaporation during the growth (pulling speed dependent). However, AC-susceptibility measurements revealed no Tc dependence with a very tiny quantity of Sr 3 Ru 2 O 7 . On the other hand, in some crystals, magnetization measurements revealed traces of a ferromagnetic phase with an ordering Curie temperature of 165 K. This was the signature of the presence of SrRuO 3 in the material; even if it could not be detected by X-ray diffraction and MEB measurements. This ferromagnetic phase affects drastically the superconducting properties of Sr 2 RuO 4 . Fig. 4 represents the magnetization versus temperature for three different Sr 2 RuO 4 single crystals, their superconducting temperatures are given in insert. For the non superconducting sample, grown with a starting composition of 2:1.33, the calculated ferromagnetic mass, assuming that the whole magnetic signal corresponded to SrRuO 3 , was 0.4% of the sample. explained by the presence of SrRuO 3 intergrowth undetectable by classical analysis (Fig. 5). For the crystal with the good Tc of 1.23 K, the amount of SrRuO 3 was negligible (o4 ppm). In the optimal crystal growth conditions, we obtained the superconducting properties which are described in Fig. 6, measured on a centimetre-sized Sr 2 RuO 4 single crystal. The AC-susceptibility and the specific heat experiments showed a bulk transition at Tc = 1.31K with a width less than 0.2 K.

Fig. 1 .

 1 Fig. 1. Photo of Sr 2 RuO 4 single crystal with a shiny facet perpendicular to the [0 0 1] direction.

  Journal of Crystal Growth 275 (2005) e739-e743 p4/7

Fig. 2 .

 2 Fig. 2. (1 1 0) Bragg reflection measured at ESRF. The calculated mosaic is 0.041.

Fig. 3 .

 3 Fig. 3. Influence of the growth speed on the superconductivity.

Fig. 4 .

 4 Fig. 4. Magnetization versus temperature for three different Sr 2 RuO 4 single crystals.

Fig. 5 .Fig. 6 .

 56 Fig. 5. High resolution transmission electronic microscopy of Sr 2 RuO 4 crystal. SrRuO 3 have been detected in epitaxial growth. The Fourier transformed calculated pictures of each region are given in insert.

Journal of Crystal Growth 275 (2005) e739-e743

Acknowledgements

We are grateful to J. Balay, A. Hadj-Azzem and J.M. Martinod, the technical and cryogenic staff of CNRS and CEA, Grenoble, France for expert assistance. We would also like to thank S.

Raymond for neutron measurements.

p7/7

Conclusion

We obtained high purity Sr 2 RuO 4 single crystals by the floating zone technique in a light furnace with a sharp Tc up to 1.31K measured on centimetre sized samples. For the highest Tc, the optimal starting composition of the rods was with 15% RuO 2 in excess and the growth speed of 4 cm/h. We observed that a very small amount of SrRuO 3 is able to destroy the superconductivity of Sr 2 RuO 4 .

Large single crystals with homogeneous superconducting properties for the whole volume have been obtained which allowed inelastic neutron scattering experiments [12][13][14].