Modeling and Practical Evaluation of a Service Location Problem in Large Scale Networks

Olivier Beaumont, Nicolas Bonichon, Hubert Larchevêque Université de Bordeaux, Laboratoire Bordelais de Recherche en Informatique INRIA Bordeaux Sud-Ouest

Abstract-We consider a generalization of a classical optimization problem related to server and replica location problems in networks. More precisely, we suppose that a set of users distributed over a network wish to have access to a particular service proposed by a set of providers. The aim is then to distinguish a set of service providers able to offer a sufficient amount of resources in order to satisfy the requests of the clients. Moreover, a quality of service following some requirements in terms of latencies is desirable. A smart repartition of the servers in the network may also ensure good fault tolerance properties. We model this problem as a variant of Bin Packing, namely Bin Packing under Distance Constraint (BPDC) where the goal is to build a minimal number of bins (i.e. to choose a minimal number of servers) so that (i) each client is associated to exactly one server, (ii) the capacity of the server is large enough to satisfy the requests of its clients and (iii) the distance between two clients associated to the same server is minimized. We prove that this problem is hard to approximate even when using resource augmentation techniques : we compare the number of obtained bins when using polynomial time algorithms allowed to build bins of diameter at most βdmax, for β > 1, to the optimal number of bins of diameter at most dmax. On the one hand, we prove that (i) if β = (2-ǫ), BPDC is hard to approximate within any constant approximation ratio, for any ǫ > 0; and that (ii) BPDC is hard to approximate at a ratio lower than 3 2 even if resource augmentation is used. On the other hand, if β = 2, we propose a polynomial time approximation algorithm for BPDC with approximation ratio 7 3 in the general case. We show how to turn an approximation algorithm for BPDC into an approximation algorithm for the non-uniform capacitated K-center problem and vice-versa. Then, we present a comparison of the quality of results for BPDC in the context of several Internet latency embedding tools such as Sequoia and Vivaldi, using datasets based on PlanetLab latency measurements.

I. INTRODUCTION

A. Problem definition and motivations

Bin Packing is a classical problem that has been studied under many variants (see [START_REF] Jr | Approximation algorithms for bin packing: a survey[END_REF] for a survey). In this paper, we study the generalization where elements belong to a metric space and the maximal distance between two elements belonging to the same bin has to be smaller than a given threshold d max . A given weight threshold W must not be overtaken for each bin and all the elements must belong to exactly one bin. Then, the goal is to minimize the number of bins of diameter at most d max and weighting no more than W .

The motivation for studying BPDC is inspired by our previous works on Bin Covering under Distance Constraint [START_REF] Beaumont | Distributed approximation algorithm for resource clustering[END_REF], [START_REF] Beaumont | Distributed approximation algorithm for resource clustering[END_REF], the distance constrained version of the Bin Covering problem [START_REF] Assmann | On a dual version of the one-dimensional bin packing problem[END_REF].

BPDC is closely related to some classical problems in the area of replica and server location problems in large scale networks such as the Internet. Many variants of server location problems can be found in [START_REF] Pál | Facility location with nonuniform hard capacities[END_REF], [START_REF] Shmoys | Approximation algorithms for facility location problems[END_REF], [START_REF] Chudak | Improved approximation algorithms for capacitated facility location problems[END_REF], [START_REF] Korupolu | Analysis of a Local Search Heuristic for Facility Location Problems[END_REF], [START_REF] Kao | Capacitated domination problem[END_REF], [START_REF] Chuzhoy | Covering problems with hard capacities[END_REF], [START_REF] Kuhn | Distributed approximation of capacitated dominating sets[END_REF], [START_REF] Raz | A sub-constant error-probability lowdegree test, and a sub-constant error-probability PCP characterization of NP[END_REF]. Most of these problems consider that a set of users in a network want to have access to a given service. The aim is then to distinguish a set of service providers able to offer a sufficient amount of resources in order to satisfy the requests of the clients. Moreover, a quality of service following some requirements in terms of latencies is desirable. A smart repartition of the servers in the network may enable to minimize the latencies between any client and its associated server, and also to ensure good fault tolerance properties. Moreover, we assume that the frequency of requests issued by the clients is heterogeneous (i.e. depends on the client), and that the servers come with a maximal capacity.

The study of BPDC is also motivated by other practical problems such as the one presented in [START_REF] Lupton | Data Collection for the Sloan Digital Sky Survey-A Network-Flow Heuristic[END_REF], where Lupton et al. aim at creating a two-dimensional map of the sky composed of quasars and galaxies. In order to gather data on those galaxies, they make multiple snapshots with a telescope, each capturing data for galaxies in the circular portion of the sky visible through the telescope. In this context, they introduce the Euclidean Capacitated Covering by Disks (ECCD) problem, where the aim is to cover points in a Euclidean plane with a minimum number of disks having a fixed diameter, without violating the maximum capacity of any disk (where the capacity corresponds to the maximum number of galaxies for which spectral data can be gathered in a single snapshot). Heuristics for ECCD have been proposed in [START_REF] Lupton | Data Collection for the Sloan Digital Sky Survey-A Network-Flow Heuristic[END_REF] and are validated through simulations only. It is worth noting that ECCD is simpler than BPDC, in the sense that the approximation algorithm we propose does not require the underlying metric space to be Euclidean.

B. Related Works

Bin Packing and K-center problems: An AP T AS (Asymptotic P T AS) has been proposed for Bin Pack-ing [START_REF] De | Bin packing can be solved within 1 + ǫ in linear time[END_REF]. Simple algorithms have also been proposed with approximation ratios slightly larger than 1.15 (see [START_REF] Jr | Approximation algorithms for bin packing: a survey[END_REF] for a survey). The First-Fit-Decreasing algorithm used in this paper is one of the simplest : it consists in sorting the items to be packed in decreasing order of their weights. Then, elements are inserted in this order into the first bin with enough remaining capacity. If no such bin is available, a new one is created. This algorithm has been proved to achieve a 11 9 -approximation ratio in [START_REF] Ullman | The performance of a memory allocation algorithm[END_REF].

BPDC is equivalent to Bin Packing with Conflicts [START_REF] Epstein | On Bin Packing with Conflicts[END_REF]. An instance of BPDC can be transformed into an instance of Bin Packing with Conflicts where 2 items are in conflict iff their distance is larger than d max in the instance of BPDC. Similarly, an instance of Bin Packing with Conflicts can be transformed into an instance of BPDC by setting the distance between two elements to 1 if they are not in conflict and 2 otherwise. However, the notion of resource augmentation, although being natural in the context of distances, has no clear counterpart in the case of Bin Packing with Conflicts.

The (uniform) capacitated K-center problem [START_REF] Bar-Ilan | How to allocate network centers[END_REF] has been introduced by Bar-Ilan et al.. This problem involves a set of elements in a metric space and a fixed number K, corresponding to the number of centers to be placed in the metric space. Each element has to be assigned to one of the K centers, with the additional constraint that each center can only handle a maximal number L of elements. Then, the goal is to minimize the maximal distance between a node and its associated center, for a fixed number K of centers and a fixed capacity L for each center.

In both problems (K-center and BPDC), the goal is to build a small number of groups with bounded weight. In BPDC, the maximum diameter of a bin is fixed and the number of groups has to be minimized whereas in the K-center problem, the number of bins is fixed and the maximal distance between a client and its associated server (which is different from the diameter) has to be minimized. In [START_REF] Khuller | The Capacitated K-Center Problem[END_REF], approximation algorithms for the uniform (weights) capacitated K-center problem are provided. BPDC is also closely related to variants of the original Kcenter problem [START_REF] Hochbaum | A Best Possible Heuristic for the k-Center Problem[END_REF] where intra-cluster distances are to be minimized [START_REF] Gonzalez | Clustering to minimize the intercluster distance[END_REF] instead of the distance to the center of the cluster.

Internet Latency Embedding tools: In order to assess the practical performance of our algorithm, we consider two embedding tools for Internet latencies. Internet embedding tools are used to map distributed resources connected through the Internet into a simple (usually metric) space. Among the most widely encountered embedding tools in the literature are Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF]. These tools assign to each resource a position in a simple space, such that the distance between any two nodes (the latency between them) can be approximated by their distance in the simple space. Of course, another possibility would consist in computing and using the whole latency matrix L, where L i,j denotes the measured latency between resources i and j. Nevertheless, this approach has two main drawbacks. First, in the context of large scale distributed networks, it is unrealistic to assume that all L i,j values can be determined accurately due to the cost of performing all measurements. Then, when using the latency matrix as input, we work in the most general space without any specific topological property. Designing efficient (i.e. with good approximation ratios) algorithms in this context turns out to be extremely difficult. On the other hand, embedding tools induce a (small) distortion of latencies, but they enable to work in simpler spaces and therefore to design more efficient approximation algorithms. In the context of a given application, such as resource clustering, only the performance of the pair embedding/clustering algorithm is meaningful. In this paper, we consider 3 embeddings: no embedding (direct use of the latency matrix), Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF].

Since the Internet latencies space contains a lot of triangular inequality violations [START_REF] Lumezanu | Triangle inequality variations in the internet[END_REF], it can be described as a semi-metric space (a space where the distance function does not satisfy the triangular inequality). Thus, it cannot be embedded in a metric space without encountering a loss of accuracy. In fact, the Internet latencies space seems to be close to an infra-metric [START_REF] Lebhar | The inframetric model for the internet[END_REF], i.e. a space in which the triangular inequality is relaxed in the following way : d(u, v) ≤ ρ max(d(u, w), d(v, w)) for any triple of nodes (u, v, w). Results presented in [START_REF] Lebhar | The inframetric model for the internet[END_REF] show that most triples satisfy above inequality with ρ = 2, and almost every triples satisfy it with ρ = 10. In this paper, we will consider semimetric spaces in which most of triples satisfy this inequality for a small value of ρ and approximation results will be given as a function of ρ.

C. Contributions

In this paper, we present an approximation algorithm for BPDC based on resource augmentation. More specifically, we compare the number of obtained bins when using a polynomial time algorithm allowed to build bins of diameter at most βd max , for β > 1, to the optimal number of bins of diameter at most d max . More precisely, we will say that A is an (α, β)-approximation algorithm based on resource augmentation [START_REF] Csirik | Resource augmentation for online bounded space bin packing[END_REF], [START_REF] Epstein | Online bin packing with resource augmentation[END_REF] for BPDC if (i) it runs in polynomial time, (ii) the bins returned by A have diameter at most βd max and (iii) the number of bins is at most αOPT BPDC , where OPT BPDC denotes the optimal number of bins with distance constraint set to d max .

In the context of large scale distributed platforms, resource augmentation is both efficient and realistic. Indeed, the aggregate amount of requests a server can handle really needs to be lower than the capacity of the server, in order for the server to be able to process the requests, whereas the threshold on the maximal latency between a server and one of its client is somehow weaker, since the server would still be able to handle its requests if it is violated (it would then simply do it slowly).

In this context, we prove that if β = (2-ǫ), this problem is hard to approximate in the general case, within any constant approximation ratio (even in any function in the number of elements), and that it is also hard to approximate within any ratio lower than 3 2 , whatever the resource augmentation. On the other hand, we propose in this paper a ( 73 , ρ)approximation algorithm for Bin Packing under Distance Constraint in a ρ-inframetric.

We also prove that an approximation algorithm for BPDC can be turned into an approximation algorithm for capacitated K-center problem and vice-versa. As far as we know, this provides the first approximation algorithm for non-uniform (weights) capacitated K-center problem. In the simpler context of the uniform capacitated K-center problem, the performance of the adaptation of the algorithm we propose for BPDC equals the performance of the best known approximation algorithm [START_REF] Khuller | The Capacitated K-Center Problem[END_REF].

Then we present a comparison of the performance of the proposed algorithm for BPDC in the context of several embedding tools for the latencies over Internet. Using different embedding tools, together with the same algorithm and actual latency measures, we can decide which embedding tool offers in practice for realistic datasets the best embedding for the specific optimization problem we consider.

The rest of this paper is organized as follows. In Section II, we present the definitions and the notations used throughout this paper. In Section III we prove that BPDC cannot be approximated even by using a (2 -ǫ) resource augmentation on the diameter, and that it is also hard to approximate at any ratio lower than 3 2 whatever the resource augmentation. In Section IV, we propose a ( 73 , ρ)approximation algorithm in ρ-inframetric, therefore achieving the best possible resource augmentation ratio in classical metric spaces. We also present a (2, ρ)-approximation algorithm for the uniform version of BPDC. Section V is devoted to the relationships between BPDC and K-center problems and how to turn an approximation algorithm of one problem into an approximation algorithm for the other. Eventually, in Section VI, we present the comparison, on actual datasets, of the performance of the ( 73 , ρ)-approximation algorithm for BPDC using different embedding tools for the latencies over Internet.

II. NOTATIONS AND DEFINITIONS

In this section, we present the definitions and notations that will be used throughout this paper.

An instance I of BPDC can be described as a 5-tuple I = (S, d, w, W, d max ), where S is a set S = {e 1 , . . . e n } of elements, (S, d) is a semi-metric space, w is a weight function, W is a weight threshold and d max is the distance threshold.

Throughout this paper, for the sake of simplicity, we set W = 1 and we normalize the weights of the elements accordingly (i.e. divide them by W ). Moreover, we do not deal with elements whose weight is larger than 1, since such elements cannot be packed in any bin. Thus, an instance of BPDC can be described by a 4-tuple I = (S, d, w, d max ), where w : S → [0; 1[, hence the following definition.

Definition 2.1 (BPDC: Distance Constrained Bin Packing): Given an instance I = (S, d, w, d max ), find a collection of pairwise disjoint subsets S 1 , . . . S K of S of minimal cardinality

K such that ∀i ≤ K, e∈Si w(e) ≤ 1, ∀(e u , e v ) ∈ S i , d(e u , e v ) ≤ d max .
We denote by OPT BPDC (I) (or simply OPT BPDC ) the minimum value of K for a given instance I.

In order to work on graphs, we will rely on the following tool that builds a graph from a set of points in a metric space.

Definition 2.2 (Compatibility Graph):

The compatibility graph Comp(I, d) associated to an instance I is the graph

G = (S; E) such that ∀(u, v) ∈ S 2 , (u, v) ∈ E ⇔ d(u, v) ≤ d.
Observe that (e i , e j ) ∈ E and (e j , e k ) ∈ E ⇒ d(e i , e k ) ≤ ρd in a ρ-inframetric space (ρ ≤ 2 in a metric space). Note that if S are points in a Euclidean space, and L 2 norm is used to define distances, Comp(I, 1) is the unit-disk graph [START_REF] Clark | Unit disk graphs[END_REF].

III. INAPPROXIMABILITY WITH SMALL RESOURCE AUGMENTATION

As stated in the introduction, BPDC is equivalent to Bin Packing with Conflicts [START_REF] Epstein | On Bin Packing with Conflicts[END_REF]. Hence BPDC is NP-Complete and hard to approximate. In what follows, we present Theorem 3.1 and Theorem 3.2 that both provide insights on the difficulty of approximating BPDC, even when using resource augmentation.

Theorem 3.1: ∀ǫ > 0, and ∀ 0 < α ≤ |S| 1/7-δ , there is no polynomial time (α, (2 -ǫ))-approximation algorithm for BPDC unless P = N P .

Proof: Since Bin Packing with Conflicts is itself a generalization of the graph coloring problem, and that it has been shown to be hard to approximate within |V | 1/7-δ for any δ > 0 [START_REF] Bellare | Free bits, pcps and non-approximability-towards tight results[END_REF], so is BPDC. Moreover, consider a reduction from Bin Packing with Conflicts to BPDC. In a conflict graph, distances between elements have integer values, so that the diameter of any set of elements in a corresponding instance of BPDC is an integer. Thus, for every bin B built on such an instance of BPDC, if the diameter of B is less or equal than (2 -ǫ) then it is at most 1. Thus, the use of a resource augmentation ratio smaller than (2 -ǫ) does not help to approximate BPDC.

Theorem 3.2: ∀ β ≥ 1 and ∀ 1 ≤ α < 3/2, there is no polynomial time (α, β)-approximation algorithm for BPDC unless P = N P , whatever the metric space used to define distances.

Proof: Ignoring the distance constraint brings us back to classical Bin Packing. Thus a (α, β)-approximation algorithm for BPDC, with α ≤ 3/2, could be used as an approximation algorithm for Bin Packing, ensuring an approximation ratio of α, which is impossible since it is well known that Bin Packing is hard to approximate within such a ratio (otherwise the 2-partition problem could be solved).

IV. A GREEDY ( 73 , ρ)-APPROXIMATION ALGORITHM FOR BPDC

In this section, we present Algorithm 1, which is an adaptation of the algorithm proposed by Epstein and Levin in [START_REF] Epstein | On Bin Packing with Conflicts[END_REF] for Bin Packing with Conflicts, using First-Fit-Decreasing algorithm to build bins (see Section I-B for a brief description of First-Fit-Decreasing algorithm).

As for the number of built bins, Algorithm 1 ensures an approximation ratio of 7 3 in any semi-metric space. When this semi-metric space is a ρ-inframetric, Algorithm 1 is a ( 7 3 , ρ)-approximation algorithm for BPDC. When the space is metric, it is a ( 7 3 , 2)-approximation algorithm for BPDC. In order to adapt the algorithm presented in [START_REF] Epstein | On Bin Packing with Conflicts[END_REF] to BPDC, we rely on the definition of the extended weight e(x) of an element x. If w(x) > 1 2 , then e(x) = 1, and if w(x) ∈ I j = ( 1 j+1 , 1 j ] for some integer j > 1, then e(x) = w(x) + 1 j(j+1) . Moreover, let us denote by OPT BPC the cardinality of an optimal solution for the Bin Packing with Conflicts problem, and by OPT GRAPHCOL the cardinality of an optimal solution for the precoloring extension problem used in [START_REF] Epstein | On Bin Packing with Conflicts[END_REF] to approximate Bin Packing with Conflicts. This precoloring extension problem is a simple extension of the classical coloring problem with the additional constraint that some nodes are already assigned colors in the input. [START_REF] Epstein | On Bin Packing with Conflicts[END_REF]): In Algorithm 1, if |M | ≤ OPT BPDC and each set of M is of diameter at most ρd max , then the number of bins returned by Algorithm 1 is ( 73 , ρ)-approximation algorithm for BPDC is at most 7 3 OPT BPDC and each bin is of diameter at most ρd max .

In [START_REF] Epstein | On Bin Packing with Conflicts[END_REF] the authors work on a particular class of graphs where computing a coloring (more precisely, solve the precoloring extension problem) of the nodes can be done optimally in polynomial time. Thus, they can build a partition M such that |M | ≤ OPT GRAPHCOL on line 7 of Algorithm 1 and each set of M is of diameter at most d max . Since, from [START_REF] Epstein | On Bin Packing with Conflicts[END_REF], Bin Packing with Conflicts is a generalization of the graph coloring problem, OPT GRAPHCOL ≤ OPT BPC . Eventually, since Bin Packing with Conflicts and BPDC are equivalent, then |M | ≤ OPT BPC = OPT BPDC and Theorem 4.1 can be used.

Indeed, each of the |M | built sets corresponds to a color class, and bins can be built "locally", without taking into account any conflicts within each color class, using a classical Bin Packing algorithm.

Taking advantage of resource augmentation, we can obtain a general result for any compatibility graph on a ρinframetric. Indeed, Algorithm 2 describes how to build a partition M of U into sets of diameter ρd max , such that |M | ≤ OPT BPDC . Then, in each set, bins can be built without taking into account any distance constraint, using the same classical Bin Packing algorithm. On the other hand, some bins may have diameter ρd max instead of d max , thus the resource augmentation ratio.

Algorithm 2 Building a partition M of U into sets of diameter at most ρd max 1: build Comp'(I, d max ), the graph Comp(I, d max ) where the edges between two elements of weight larger than Proof: Two elements of M cannot belong to the same bin in an optimal packing. Indeed, since they belong to the MIS of Comp'(I, d max ), either their distance in Comp(I, d max ) is at least 2 (and thus they are too far away to belong to the same bin) or both elements have weight larger than 1 2 and in this case, the bin would be too heavy. Hence, |M | ≤ OPT BPDC .

Theorem 4.3: Algorithm 1 together with Algorithm 2 is a ( 7 3 , ρ)-approximation algorithm for BPDC when d is a ρinframetric. Theorem 4.3 is directly obtained using Theorem 4.1 and Lemma 4.2. Thus, Algorithm 1 is optimal with respect to resource augmentation, in the sense that no constant approximation ratio can be achieved using a resource augmentation strictly smaller than 2 in the metric case (cf Section III).

Remark concerning a uniform weights version: Let us consider the following "uniform weights" version of BPDC, where all items have the same weight x. Since the weight of each bin is at most 1, the goal is to build bins containing at most ⌊ 1

x ⌋ elements from S (still valid for the distance constraint). In this case, lines 2-6 of Algorithm 1 are useless and we obtain Corollary 4.4.

Corollary 4.4: Algorithm 1 together with Algorithm 2 is a is a (2, ρ)-approximation algorithm for the uniform version of BPDC.

Proof: Note that in the uniform case, First-Fit-Decreasing algorithm (or any greedy algorithm) will create bins of ⌊ 1

x ⌋ elements (thus, only optimal ones) except for at most one bin in each of the |M | packs built by Algorithm 2. Thus, the number of non optimal bins is smaller than |M | and, by Lemma 4.2, |M | ≤ OPT BPDC . Combined with the other optimal bins, this provides the claimed approximation ratio.

V. COMPARISON WITH THE CAPACITATED K-CENTER

PROBLEM

In this section, we present how to build an approximation algorithm for the capacitated (uniform or non-uniform) Kcenter problem (CapKcenter for short) from an approximation algorithm for BPDC.

Definition (Non-uniform Capacitated K-center): Given an instance K = (S, d, w, K), i.e. a set S = {e 1 , . . . e n } of elements, a metric space (S, d), a weight function w : S → [0; 1) and an integer K, find the smallest value r max and a subset X ⊆ S of centers whose size is at most K and an assignment of the elements to the centers in X such that the overall weight of elements assigned to any center is smaller than 1, and every element is assigned to a center at distance less than r max from itself.

We denote by OPT CAPKCENTER (K) (or simply OPT CAPKCENTER ) the optimal value of r max for a given instance K. The usual formulation of the capacitated K-center (see [START_REF] Khuller | The Capacitated K-Center Problem[END_REF]) deals with uniform weights : ∀x ∈ S, w(x) = w. Thus, the weight condition corresponds to assign no more than 1/w elements to any center. Usually, for the K-center problem, K is given and r max is to be minimized.

To use resource augmentation for this problem, let us say that A is an (α, γ, β)-approximation algorithm for (nonuniform) capacitated K-center if it runs in polynomial time and builds a solution using at most αK centers (instead of K), with an assignment of nodes to centers such that the overall weight of nodes assigned to any center is smaller than γ (instead of 1), and such that every node is assigned to a center at distance at most βOPT CAPKCENTER (instead of OPT CAPKCENTER ).

Theorem 5.1: An (α, β)-approximation algorithm for BPDC can be turned into an (α, 1, 2β)-algorithm for Cap-Kcenter. Conversely, an (α, 1, β)-approximation algorithm for CapKcenter can be turned into an (α, 2β)-approximation algorithm for BPDC.

Proof: Given (S, d, w), a set of weighted elements in a metric space, we consider two natural transformations, T and T ′ , between packings and assignments:

Transformation T :

• takes as input a set of bins, solution of instance I = (S, d, w, d max ) of BPDC, for a fixed value of d max , • in each bin, an element is arbitrary chosen to become the center of the bin, • all other elements are assigned to it; the radius of the obtained assignment is at most the maximal diameter among the input bins. Transformation T ′ :

• takes an assignment as input, solution of instance K = (S, d, w, K) of CapKcenter, for a fixed value of K, • for each center, T ′ builds a bin composed of the center and all elements assigned it; the diameter of the obtained bin is at most twice the radius of the corresponding assignment.

Let us now describe how a (α, β)-approximation algorithm A for BPDC can be turned into a (α, 1, 2β)approximation algorithm for the non-uniform capacitated Kcenter problem. Let K = (S, d, w, K) be an instance of the non-uniform capacitated K-center problem. Let I(D) = (S, d, w, D) be an instance of BPDC, based on the same set of weighted elements, for any positive value D.

Let d α denote the smallest value such that algorithm A computes a solution of BPDC with at most αK bins on the instance I(d α ). Let d 1 , d 2 , . . . , d n(n+1)/2 denote the distances between each pair of elements of S in non decreasing order (d 1 is the distance between the two closest elements and d n(n+1)/2 is the diameter of S). Since for any

d i ≤ D < d i+1 , Comp(I(D), D) = Comp(I(d i ), d i )
, there is only a polynomial number of values to be considered to compute d α .

Since A is a (α, β)-approximation algorithm for BPDC, the number of bins created by A on I(D) is at most αOPT BPDC (I(D)). Hence, for any D < d α , OPT BPDC (I(D)) > αK α = K. Applying T ′ to the optimal solution of K provides a valid solution for I(2OPT CAPKCENTER (K)) with at most K bins. From the last observation, we obtain that 2OPT CAPKCENTER (K) ≥ d α .

Applying T to the result of A on I(d α ), we obtain an assignment of size αK, of maximum radius at most βd α ≤ 2βOPT CAPKCENTER (K) and of maximum weight at most 1 for instance K. Hence, this adaptation of A provides a (α, 1, 2β)-approximation algorithm for the non-uniform capacitated K-center problem.

Let us now prove how to turn an approximation algorithm for the non-uniform K-center problem into an approximation algorithm for BPDC. Let us consider a (α, 1, β)approximation algorithm A ′ for the non-uniform capacitated K-center problem. Let I = (S, d, w, d max ) be an instance of BPDC. Let K(K) = (S, d, w, K) be an instance of nonuniform capacitated K-center, based on the same set of weighted elements, for any positive value Let K β denote the smallest value such that algorithm A ′ computes a solution for the non-uniform K-center problem with radius at most βd max on the instance K(K β ). Since A ′ is a (α, 1, β)-approximation algorithm for non-uniform capacitated K-center, the radius of the assignment built by

A ′ on K(K) is at most βOPT CAPKCENTER (K(K)). Hence, for any K < K β , OPT CAPKCENTER (K(K)) > βdmax β = d max .
Applying T to the optimal solution of I provides a solution for K(OPT BPDC (I)) with radius at most d max . From the last observation, we obtain that OPT BPDC (I) ≥ K β .

Applying T ′ to the result of A ′ on K(K β ) provides a packing with at most αK β ≤ αOPT BPDC (I) bins with diameter at most 2βd max and with weight at most 1 on the instance I. Hence this adaptation of A ′ provides a (α, 2β)approximation algorithm for BPDC.

Note that this result can also be applied on uniform versions of BPDC and capacitated K-center. In such a setting, combining Theorem 5.1 with Corollary 4.4, Algorithm 1 provides a (2, 1, 4)-approximation algorithm for the capacitated K-center problem in the general case. This result has to be compared to the one presented in [START_REF] Khuller | The Capacitated K-Center Problem[END_REF], where a polynomial time algorithm is proposed, providing a ( 2 c , c, 4)approximation ratio, where c = m+1 m for any m ≥ 1. For example, if m tends becomes arbitrarily large, this algorithm provides a (2, 1, 4)-approximation algorithm, which is exactly the same as the one provided by the adaptation of Algorithm 1. Note that in the other way, this particular case providing a (2, 1, 4)-approximation algorithm for the capacitated K-center problem becomes a (2, 8)-approximation algorithm for uniform BPDC, by Theorem 5.1, whereas Algorithm 1 is already a (2, 2)-approximation algorithm for the same problem.

Moreover, combining Theorem 5.1 with Theorem 4.3, Algorithm 1 provides a ( 7 3 , 1, 4)-approximation algorithm for CapKcenter. To the best of our knowledge, it is the first approximation result for a non uniform version of CapKcenter, since the family of algorithms presented in [START_REF] Khuller | The Capacitated K-Center Problem[END_REF] cannot easily be adapted to such a non-uniform weights version. Eventually, one could see the difference between those approximation ratios (between 7 3 and 2) as the cost of the non-uniformity of the weights.

VI. EXPERIMENTAL EVALUATION

In this section, we propose a comparison of the most widely encountered embedding tools for latency extimation, namely Vivaldi [START_REF] Cox | Practical, distributed network coordinates[END_REF], [START_REF] Dabek | Vivaldi: a decentralized network coordinate system[END_REF] and Sequoia [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], [START_REF] Abraham | Reconstructing approximate tree metrics[END_REF], in the context of the location problems considered in this paper. For all the embeddings, Algorithm 1 will be used to compute the solution of BPDC.

Vivaldi associates with each node of a network two coordinates in the Euclidean plane plus a height. In such a space, the distance between two nodes having coordinates

(a x , a y , a h ) ∈ R 2 × R + and (b x , b y , b h ) ∈ R 2 × R + is given by d(a, b) = (a x -b x ) 2 + (a y -b y ) 2 + a h + b h .
Sequoia embeds Internet nodes into one or several weighted trees in which each node is either a leaf or the root, and in which internal nodes are virtual nodes. The distance between two nodes in the original network is approximated by the distance in the embedding tree (or as the median of these distances in the case of multiple trees). In [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], it is claimed that the accuracy of the prediction is higher using Sequoia as soon as a few trees rooted at different nodes are used (10 or 15 trees).

The main originality of the approach we propose is that it is done in the context of a specific application, i.e. the placement of servers for heterogeneous amounts of requests. Indeed, the accuracy of embedding tools have already been compared in [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF], but the goal was only to estimate the closeness between latency predictions returned by the embeddings and the actual measurements.

In practice, when considering an specific application, the chain is more complicated and the performance of the chain embedding+algorithm has to be evaluated as a whole. Indeed, our experiments will show that the performance obtained when running the same algorithm in different embedding strongly depends on the embedding for server location problems and that the ranking of the embeddings is not the same as the one obtained in [START_REF] Ramasubramanian | On the treeness of internet latency and bandwidth[END_REF].

To compare the respective performance of the different embedding tools, we will compare the results obtained using Algorithm 1 with the following embeddings:

• no embedding (direct use of the latency matrix)

• Vivaldi embedding • 1-tree Sequoia embedding • 5-trees Sequoia embedding • 10-trees Sequoia embedding • 15-trees Sequoia embedding.

A. Experimental Protocol

In order to perform realistic simulations, we need to estimate the distance (the latencies) between any pair of resources and we need to estimate the heterogeneous capacity of the resources.

In order to estimate latencies, we ran simulations on a real dataset taken from the Meridian project1 containing all-pairs latency measurements between 2500 nodes arbitrarily chosen from PlanetLab2 . In this matrix, latency measurements are symmetric.

This matrix contains a lot of triangular inequality violations. The study in [START_REF] Lumezanu | Triangle inequality variations in the internet[END_REF] makes a difference between triangular inequality violations due to the structure of the Internet itself or due to the traffic on the Internet, and violations due to measurements inaccuracy. Considering the study by Lebhar et al. in [23], for each triple, we consider that if the value ρ associated with this triple is larger 10, then it might be due to the inaccuracy of the measurement.

Thus, in a first step, we compute for each latency measurement between two nodes, the number of times it appears in a triple for which the ρ value is larger than 10. Figure 1 depicts the repartition function of this number: a point (x, y) means that y% of the latency values appear in less than x triples having a ρ value larger than 10. Using Figure 1, we consider that a latency value is notvalid if it appears in more than 300 triangles in which the value of ρ is larger than 10. Each not-valid latency is replaced by the 2-hop shortest path made of valid latencies. The resulting latency matrix is call the fixed matrix.

To obtain this "fixed matrix", only 0.13% of the latency values in the original latency matrix have to be modified. In what follows, we run simulations using both the original latency matrix, and the "fixed matrix".

In order to estimate the heterogeneous amount of requests of the clients, we choose to rely on two distributions of the weights of the elements, namely, the uniform distribution in [0, 1) and the log-normal distribution with parameters 0 and 1, since both seem to arise naturally in many practical situations (the log-normal distribution can be seen as a bounded power-law distribution, which seems more realistic than a classical power-law). We choose, according to those distributions, two sets of 2500 values.

For each simulation, we rely on the following protocol

• We embed the latency matrix, using either Vivaldi or Sequoia (using one or multiple trees in the case of Sequoia). • We assign to each element a weight according either to the uniform distribution (in [0, 1)) or to the log-normal distribution (with parameters 0 and 1). • We apply Algorithm 1 for BPDC to the resulting embedding, with the same set of weighted elements but for different values of d max , from the minimal distance previously identified to 200ms (since beyond this value, no evolution is observed). As mentioned in the introduction, it is unrealistic in practice to assume that the whole latency matrix is known. Indeed, in the context of large scale dynamic platforms, the time taken to estimate all latencies is much too high with respect to the dynamics of the system. It is worth noting that the implementation of Vivaldi does not require a centralized knowledge of the matrix, what is not the case for Sequoia to the best of our knowledge.

For each simulation, we plot the total number of bins built. For each built bin, we also estimate its diameter as the maximal distance between any two nodes in the bin, where distances are actual ones, i.e. the one of the latency matrix, whatever the intermediate distance estimated by the embedding tool is. For each simulation and for each value of d max , we plot the average diameter of built bins, and the percentage of "valid" bins, i.e. of bins whose diameter in the latency matrix used is lower than 2d max , the maximum diameter allowed by the corresponding algorithm.

We ran simulations for different values of W (the size of bins), and choose a different value for each distribution of the weights. Indeed, we wanted to work with the more meaningful and representative value. For small values of W , solutions tend to put fewer and fewer elements in each bin, since element weights get closer to the threshold. Thus, the average number of elements per bin tends towards one for any value of d max . For large values of W , the distance constraint becomes the most important and the problem is close to MINIMUM CLIQUE PARTITION. Thus we chose, for each distribution, a weight threshold such that bins contain on average approximately 8 elements.

• In the case of the uniform distribution, we chose W = 4, since the average weight of an element is 0.5,

• In the case of the log-normal distribution, we chose W = 5.2.

Eventually, since simulation results were highly similar when using one or the other distribution law to generate elements' weights, we only present results obtained using the log-normal distribution, with W = 5.2.

B. Simulation results

Figures 2 and 3 and 4 respectively depict, for each considered embedding, the number of built bins, the average value of the diameter of built bins and the percentage of valid bins built in each case, for several values of d max and using the fixed latency matrix. Figures 5 and6 and 7 also depict, for each considered embedding, the number of built bins, the mean diameter of the built bins and the percentage of valid built bins in each case, for several values of d max and using the original latency matrix.

Figures 2 and5 show that there are three intervals for the value of d max in each of which the difficulty of BPDC appears for different reasons.

• d max ≤ 10ms. In this case, the weight constraint is weaker than the distance constraint. The difficulty comes from the topology and the problem close to the MINIMUM CLIQUE PARTITION PROBLEM in the compatibility graph. • 10ms < d max ≤ 60ms. In this case, both constraints (weight and distance) have to be taken into account. • 60ms < d max . The distance constraint is the weakest one and the topology is not crucial anymore. The weighted constraint is the most important and BPDC is close to classical Bin Packing.

Figures 4 and7 show that Algorithm 1 builds a higher percentage of valid bins when using Vivaldi embedding, using either the original or the fixed matrix as input. By contrast, when using Sequoia embedding with 1-tree only (either with the original or the fixed matrix as input) the percentage of valid bins is much lower. The direct use of the latency matrix (whatever the latency matrix used) provides performances between those obtained using Vivaldi embedding and those obtained using Sequoia 1-tree embedding.

The information provided by the comparison between the use of the original latency matrix and of the fixed matrix as input of the embedding tools is related to the robustness of the behavior of Algorithm 1 with each embedding. In fact, only a few amount of latency values have been modified between the original and the fixed matrix (0.13% of the values). Thus if, for a given embedding, the performance differences are important when using each of the two matrix as input, this means that only a few changes in the instance can deeply modify the result of the execution of the algorithm, meaning that the joint use of the algorithm and the given embedding is not robust for our application.

Thus, when comparing the figures depicting results obtained using each of the two latency matrices, we observe almost no difference between both datasets when using Vivaldi embedding. It is also the case when no embedding is used (direct use of the latency matrix). By contrast, when comparing the results obtained using the two different latency matrix as input for the different Sequoia embeddings, we observe major differences.

Algorithm 1

 1 Greedy ( 7 3 , ρ)-approximation algorithm for BPDC 1: U ← S // elements not grouped yet 2: C = Comp(I, d max ) 3: while there is a set of three connected items {a, b, c} that can fit into one bin, i.e. w(a)+w(b)+w(c) ≤ 1, such that e(a)+e(b)+e(c) > 1 and w(c) ≤ w(b) ≤ w(a) ≤ 1 2 , or a pair of connected items (a, b) that can fit into one bin, i.e. w(a) + w(b) ≤ 1, such that e(a) + e(b) > 1 do 4: choose such a set of maximum overall extended weight, and put all the elements of this set into a new bin 5:remove from U this set of elements 6: end while 7: build a partition M of U 8: apply First-Fit-Decreasing on each set of the M parts induced by the previous partition.

Theorem 4 . 1 (

 41 Reformulation of Theorem 12 of

Figure 1 .

 1 Figure 1. Repartition function of the number of triples having a ρ value larger than 10.

Figure 2 .Figure 3 .Figure 4 .

 234 Figure 2. Number of built bins for BPDC, for different values of dmax, using different embeddings, using the fixed latency matrix.

  The partition M of U built by Algorithm 2 satisfies |M | ≤ OPT BPDC .

	1 2 have been removed 2: build a Maximal Independent Set (MIS) M such that
	elements of weight larger than 1 2 belong to M . 3: arbitrarily associate each node ∈ M to one of its
	neighbors in M so that |M | packs of elements are
	returned.
	Lemma 4.2:

http://www.cs.cornell.edu/People/egs/meridian/data.php

http://www.planet-lab.org/

• All four Sequoia embeddings (using 1, 5, 10 or 15 trees) provide bad performances (in terms of percentage of valid bins and mean diameter of the bins) when using the original matrix as input, • As evoked before, the performance of Sequoia-1-tree embedding is still poor when using the fixed matrix, • The Sequoia-5-trees embedding, when working with the fixed matrix, ensures performance that are comparable to those obtained without using any embedding on the same matrix, • both Sequoia-10-trees and Sequoia-15-trees embeddings perform better than when no embedding is used, when using the fixed matrix. To explain the lack of robustness of Sequoia, it is necessary to go into the details of Sequoia algorithm. In fact, in some cases, even just one triangular inequality violation can, in the subtree rooted at the least common ancestor to the three nodes concerned by this violation, induce important distance distortions. Distances between nodes in this subtree can therefore be highly underestimated. This ends in building bins having a diameter in the original matrix violating the imposed distance constraint (thus, those bins are not valid). Therefore, reducing the number of such Triangular Inequality Violations in the original matrix to obtain the fixed matrix can highly improve the performance of Sequoia.

We can conclude from these observations that the joint use of Algorithm 1 and Sequoia, with any number of trees used to embed the network, is not robust in the context of our application. By contrast, the use of Vivaldi embedding, while offering good performances, is a robust solution for BPDC.

VII. CONCLUSION

In this paper, we have considered an extension the classical Bin Packing problem, where the distance between two elements belonging to the same bin has to be lower than a given threshold. This problem is closely related to several servers and replicas location problems that have been widely studied in the literature. We have provided both inapproximability results and approximation algorithms based on resource augmentation for this problem. Another important contribution of this paper is the comparison, in the specific context of server location problems, of several embedding tools for Internet latencies, on an actual dataset corresponding to PlanetLab nodes. We prove that comparing Vivaldi and Sequoia embeddings on a specific application and using an actual dataset enables to discuss their robustness.


Vaughan Bell

David A Oakley

Peter W Halligan

Dr Quinton Deeley

Dissociation in Hysteria and Hypnosis: Evidence from Cognitive

Keywords: Hypnosis, hysteria, conversion disorder, dissociative disorders, neuropsychology, brain

HAL is

Introduction

At the close of the nineteenth century, the French neurologist Jean-Martin Charcot proposed the radical hypothesis that similar brain processes were responsible for the unexplained neurological symptoms of hysteria and the pseudo-neurological behaviours commonly produced by hypnosis. This hypothesis stemmed from his many years of work using hypnosis where the symptoms of hysteria could be produced, or resolved, and in posttraumatic cases, identical symptoms to the post traumatic symptoms could be reproduced. [START_REF] Ellenberger | The Discovery of the Unconscious: The History and Evolution of Dynamic Psychiatry[END_REF] Even in a modern context, Kirsch [START_REF] Kirsch | Changing Expectations: A Key to Effective Psychotherapy[END_REF] notes that "Hypnotized subjects are asked to experience paralysis, amnesia, anaesthesia, involuntary movements and hallucinations. In fact, hypnotisability is measured as the number of conversion and dissociation symptoms that the person is able to display". Central to Charcot's explanation was the concept that symptoms could derive from unconscious 'fixed' ideas based on suggestions or autosuggestions "remaining isolated from the rest of the mind and expressing themselves outwardly through corresponding motor phenomena" (quoted in Ellenberger, [START_REF] Ellenberger | The Discovery of the Unconscious: The History and Evolution of Dynamic Psychiatry[END_REF]). Recent advances in cognitive neuroscience provide an opportunity to evaluate Charcot's hypothesis. This review focuses on 'hysteria' which classically describes the presentation of medical symptoms without evidence of tissue pathology that can adequately explain the impairment, and its relationship to the effects of hypnosis. While the concept of hysteria has historically varied, [START_REF] Brown | Psychological mechanisms of medically unexplained symptoms: an integrative conceptual model[END_REF] this review focuses on aspects of the condition which have been modelled using hypnosis; to date, these typically include conditions that would be diagnosed as conversion disorder and affect voluntary motor or sensory function, or would be diagnosed as psychogenic, functional, or dissociative amnesia.

These remain controversial and curious diagnoses characterised by putative psychological mechanisms rather than any specific symptom or pathognomonic finding. The review begins by considering the historical links between the two proposed psychological constructs implicated in hysteria -namely 'dissociation' and 'conversion' -before examining the parallels between hysteria and hypnosis.

Dissociation and Conversion

Although not the first to use the term, the philosopher and psychiatrist Pierre Janet wrote extensively about dissociation, and it is Janet's conception of dissociation as a "narrowing of the field of consciousness" resulting in the compartmentalisation of normally integrated mental functions that continues to define the condition today. [START_REF] Ellenberger | The Discovery of the Unconscious: The History and Evolution of Dynamic Psychiatry[END_REF] Janet cited unresolved traumatic memories as the cause of fixed ideas and of dissociation in hysteria, and felt a tendency to dissociate was an innately pathological process whichever form it took. Freud, who had studied with Charcot, extended Janet's ideas in Studies in Hysteria (co-authored with Joseph Breuer) by proposing that the dissociative process resulted from the repression of traumatic material into the unconscious, much of which related to sexual memories or desires. Thus following Freud, hysteria became "conversion hysteria" [START_REF] Ellenberger | The Discovery of the Unconscious: The History and Evolution of Dynamic Psychiatry[END_REF], typically understood as a psychological defence mechanism that converts emotional distress associated with repressed memories of trauma into physical symptoms, so producing dissociation. Nevertheless, it is not clear whether the concept of conversion is testable given the circular definition whereby patients with conversion symptoms are unable to describe precipitating traumata owing to the events being repressed into the unconscious, while the absence of remembered trauma is used as evidence for this process at work. [START_REF] Brown | Psychological mechanisms of medically unexplained symptoms: an integrative conceptual model[END_REF] The Freudian notion of 'conversion' as a defence against pathological emotional states is also suspect in light of the fact that in patients with diagnoses of hysteria-like conditions, psychiatric co-morbidity is the norm rather than the exception. [START_REF] Crimlisk | Slater revisited: 6 year follow up study of patients with medically unexplained motor symptoms[END_REF] Moreover, almost all of the available evidence that can be reviewed concerns the clinically presented 'end states' (i.e. symptoms) of hysteria, and does not address the processes that led up to them or indeed to the possibility that there is a 'state' of hysteria that can be identified over and above the presence of specific symptoms. Indeed, relatively little research has looked specifically at causal neuropsychology, with a single case study by Kanaan et al. [START_REF] Kanaan | Imaging repressed memories in motor conversion disorder[END_REF] and a group study by Voon et al. [START_REF] Voon | Emotional stimuli and motor conversion disorder[END_REF] being the only prominent examples. In light of this, the view adopted here is that the symptoms of hysteria (paralyses, amnesias, sensory losses and so on) are examples of a form of dissociation (compartmentalisation) in which relatively circumscribed aspects of cognition become separated from normal subjective awareness or voluntary control. [START_REF] Holmes | Are there two qualitatively distinct forms of dissociation? A review and some clinical implications[END_REF] Further, these dissociative 'end states' can be viewed as distinct from 'conversion' as a hypothetical process that causes them.

The neuropsychology of hysteria i) hysterical paralysis:

The first neuroimaging study was completed using SPECT to assess cerebral perfusion in an individual diagnosed with hysterical anaesthesia and paralysis. [START_REF] Tiihonen | Altered cerebral blood flow during hysterical paresthesia[END_REF] The researchers found decreases in right parietal activity and increases in right frontal activity when the median nerve on the paralysed left side was electrically stimulated with the asymmetry in these two areas largely resolving on recovery. A more detailed study by Vuilleumier et al. [START_REF] Vuilleumier | Functional neuroanatomical correlates of hysterical sensorimotor loss[END_REF], also using SPECT, investigated seven patients with single-sided hysterical paralysis and sensorimotor loss. The design involved passive vibratory stimulation of both hands when the deficit was present, and 2-4 months later after recovery. This study found regional cerebral blood flow decreases in the basal ganglia and thalamus contralateral to the paralysis when symptoms were present but not when the condition had resolved. The authors suggested that the hysterical sensorimotor loss symptoms may result from dysfunction in striatothalamocortical circuits controlling sensorimotor and voluntary motor behaviour, and that motor processes may be modulated by inputs from regions such as anterior cingulate cortex (ACC) or the orbitofrontal cortex (OFC) into the basal ganglia and thalamus. In each of these studies, brain activation was compared when the deficit was present, and then later, when it had resolved, so regional cerebral blood flow (rCBF) changes could be directly correlated with the presence of hysterical symptoms. Nevertheless, in both cases, although sensory stimulation was provided, patients were entirely passive and the studies did not explore the task-related neural basis of alterations in voluntary motor control by requiring subjects to attempt to move the affected limb during paralysis and sensory loss, and after their resolution.

In terms of resting state studies, Yazici and Kostakoglu [START_REF] Yazici | Cerebral blood flow changes in patients with conversion disorder[END_REF] imaged five patients with conversion paralysis and found that four out of the five patients had left temporal and one patient had left parietal perfusion decreases. A similar study by Tanaka et al. [START_REF] Tanaka | Pseudohysterical hemiparesis[END_REF] found a resting state reduction in the activity of frontal motor areas in four cases of conversion paralysis, but as both studies imaged a rest condition and no stimulus or task was introduced, it is again difficult to draw any conclusions about dynamic (i.e. task-related) differences in function.

Marshall et al. [START_REF] Marshall | The functional anatomy of a hysterical paralysis[END_REF] reported the first task-based functional imaging study of a patient with a leftsided hysterical paralysis using PET. When asked to move the paralysed leg, there was no activation in the contralateral motor cortex and this was accompanied by an activation increase in the right ACC and right OFC. This was not seen when the good leg was moved, which was accompanied by normal contralateral motor cortex activation. This activation task based type of study was later extended by Spence et al. [START_REF] Spence | Discrete neurophysiological correlates in prefrontal cortex during hysterical and feigned disorder of movement[END_REF] in a small case series that compared patients with hysterical weakness to four participants instructed to feign motor weakness and two normally moving controls. Patients were distinguished by a reduction in left dorsolateral prefrontal cortex (DLPFC) activity regardless of their side of weakness while feigners were distinguished by a reduction in right DLPFC activation.

As outlined in Table 1, fMRI studies on hysterical paralysis typically show functional decreases in brain areas related to the area of impairment typically linked to increases in prefrontal cortex activity, supporting the explanation that the impairment is due to inhibition of the primary motor areas by higher level systems at some point during sensory or motor processing. However, a refinement of the executive control explanation presented by Cojan et al. [START_REF] Cojan | Motor inhibition in hysterical conversion paralysis[END_REF] used a GO-NOGO task to examine brain activation during movement preparation, execution and inhibition in a patient with left handed hysterical conversion paralysis in comparison to a group of healthy controls. These authors reported that right motor cortex activity was present during preparation to move (also previously reported in the case study by Marshall et al. [START_REF] Cojan | Motor inhibition in hysterical conversion paralysis[END_REF]) which argues against the idea that hysterical paralysis functions through an inhibition during motor intention. Notably, conscious inhibition of movement in the NOGO trials in the Cojan et al study [START_REF] Cojan | Motor inhibition in hysterical conversion paralysis[END_REF] was associated with inferior frontal gyrus activation which was not present in paralysis-related movement failure to GO stimuli.

Rather, paralysis-related response failure was associated with increased activation in the right ventrolateral prefrontal cortex, left superior frontal gyrus and bilateral precuneus. The authors note that ventrolateral prefrontal cortex receives inputs from executive regions involved in emotion processing such as OFC and ventromedial prefrontal cortex, and may thus act as a point at which affective information can influence task-related representations held in prefrontal regions. Further, functional connectivity was increased between the motor cortex and midline cortical regions involved in self-referent processing, including the ventromedial PFC and precuneus. These authors therefore proposed that hysterical paralysis may occur through the influence of internal representations and memories related to the self affecting the motor execution stage.

Studies using transcranial magnetic stimulation (TMS) to stimulate the primary motor cortex of patients with hysterical paralysis have found normal motor evoked potentials, in keeping with the proposal that changes in higher level control systems underpin the disorders (e.g. [START_REF] Cantello | Diagnosis of psychogenic paralysis: the role of motor evoked potentials[END_REF]). It should be noted, though, that three studies of patients with diagnosed psychogenic dystonia (abnormal muscle tone) reported unusual motor evoked potentials (review in Quartarone et al. [START_REF] Quartarone | Abnormal sensorimotor plasticity in organic but not in psychogenic dystonia[END_REF]). This may result from an adaptation to the maintenance of chronic abnormal muscle tone which is nonetheless proximally caused by changes in higher level control systems. Alternatively, there may be an as yet unknown impairment in the primary motor pathway associated with this disorder; or, possibly, the diagnosis (at least in the patients studied) may be inaccurate. measured with both EEG (electroencephalography) and MEG (magnetoencephalography) are normal during sensory stimulation [START_REF] Black | Conversion hysteria: lessons from functional imaging[END_REF] to the point where they are considered diagnostic in hysterical blindness, deafness, and anaesthesia. Furthermore, while the signal linked to primary sensory processing is intact, the signals in higher level brain areas associated with cognitive processing have been found to be abnormal when compared to normal subjects or those asked to simulate the impairment. [START_REF] Black | Conversion hysteria: lessons from functional imaging[END_REF] Hence, these studies have shown hysterical sensory loss in different modalities (vision, hearing, touch) to be associated with normal early sensory cortical processing.

Nevertheless, an fMRI study by Ghaffar et al. [START_REF] Ghaffar | Unexplained neurologic symptoms: an fMRI study of sensory conversion disorder[END_REF] showed that hysterical sensory symptoms can be associated with task-related changes in activity in primary sensory cortices as well as higher level control regions. The study involved three patients, two with hysterical anaesthesia and one with both anaesthesia and paresthesia (tingling). Vibrotactile stimulation to the affected area was compared with an equivalent unaffected area on the contralateral side, and with bilateral stimulation. Each patient was analysed separately and in all cases, stimulation of the affected region did not result in the expected activation in the contralateral primary somatosensory cortex that occurred when the unaffected region was stimulated. Furthermore, the lack of expected activation was variously accompanied by activation increases in the OFC, ACC, secondary somatosensory cortex and basal ganglia. The results from the Ghaffar et al. suggest an apparent contradiction to the electrophysiological studies that typically show no differences in the responses of primary sensory areas between patients and controls. However, it is not yet clear how closely the measurements reflect similar processing owing to differing methodologies and temporal resolution of the measurements which have been shown previously to produce different results in sensory paradigms.

iii) functional amnesia:

Dissociative, functional or psychogenic amnesias involve autobiographical memory loss, often for traumatic or stressful events, in the absence of neuropathology that could explain the cognitive impairment. [START_REF] Kopelman | Disorders of memory[END_REF] The disorder is typically characterised by a profound loss of past memories, often associated with 'fugue' states involving loss of identity and wandering (usually in the context of severe precipitating psychosocial stress); depression; and a history of transient organic amnesia.

Two main theories have attempted to explain the aetiology and maintenance of the condition: Kopelman [START_REF] Kopelman | Disorders of memory[END_REF] proposes that functional amnesia results from arousal driven prefrontal inhibition of the medial temporal and diencephalon memory retrieval mechanisms, in line with similar theories of dissociative symptoms where top-down executive inhibition is postulated. [START_REF] Oakley | Hypnosis and conversion hysteria: a unifying model[END_REF] In contrast, Markowitsch [START_REF] Markowitsch | Psychogenic amnesia[END_REF] argues that precipitating events cause a release of stress-related hormones resulting in a 'mnestic block syndrome' characterised by functional dissociation of fronto-temporal regions, particularly of the right hemisphere where dissociative amnesia is caused by failure to engage the medial temporal / diencephalic system, rather than its active inhibition.

As can be seen from Table 2, resting state studies using [18F] fluorodeoxyglucose positron emission tomography (FDG-PET) or SPECT in patients with functional amnesia syndromes have typically found reduced metabolic activity in the right inferolateral PFC, [START_REF] Brand | Functional brain imaging in 14 patients with dissociative amnesia reveals right inferolateral prefrontal hypometabolism[END_REF] with fewer studies reporting reduced temporal metabolism [START_REF] Markowitsch | Neuroimaging and behavioral correlates of recovery from mnestic block syndrome and other cognitive deteriorations[END_REF][START_REF] Hennig-Fast | A case of persistent retrograde amnesia following a dissociative fugue: neuropsychological and neurofunctional underpinnings of loss of autobiographical memory and self-awareness[END_REF] or perfusion [START_REF] Markowitsch | Impaired episodic memory retrieval in a case of probable psychogenic amnesia[END_REF] with varying laterality. By contrast, activation studies in patients with dissociative amnesia more commonly report increased prefrontal and decreased medial temporal / diencephalic activity associated with inability to remember, often alongside other changes in brain activity. Of the six patients included in relevant activation studies reviewed in Table 2, three showed greater DLPFC activity and one greater lateral PFC (BA 8) activation in tasks contrasting stimuli from amnesic relative to non-amnesic periods, whilst four showed reduced medial temporal lobe/ diencephalic activations, although with varying laterality, differential activation of sub-regions and complex patterns of changes where repeated measures were taken. In terms of theoretical models, resting state studies are generally consistent with Markowitsch's [START_REF] Markowitsch | Psychogenic amnesia[END_REF] view that functional amnesia results from failure to cue autobiographical memory retrieval while activation studies are consistent with Kopelman's [START_REF] Kopelman | Disorders of memory[END_REF] executive inhibition model. This apparent contradiction may reflect the operation of both processes in individuals with dissociative amnesia as indicated by two single case studies, one using SPECT and PET [START_REF] Brown | Psychological mechanisms of medically unexplained symptoms: an integrative conceptual model[END_REF] and one using FDG-PET and fMRI. [START_REF] Brown | Psychological mechanisms of medically unexplained symptoms: an integrative conceptual model[END_REF] These studies demonstrated right frontal and temporal hypoperfusion and temporal hypometabolism respectively during resting state but increased prefrontal / executive activation during attempted retrieval of information from the amnesic relative to remembered periods.

One possibility is that reduced resting state metabolism or perfusion in right ventral frontal and/or temporal regions reflects basal under-activity in memory systems secondary to chronic executive inhibition. Equally, executive processes could be recruited to inhibit retrieval when the 'mnestic block syndrome' fails to prevent the cueing of memory retrieval. This raises the possibility that executive inhibition may be sufficient to cause functional memory suppression in the absence of high arousal and stress hormone release, for example, in motivated forgetting, suggested amnesia, and in culturally influenced forms of circumscribed autobiographical memory loss such as spirit possession.

iv) summary: Evidence from EEG, TMS and behavioural studies indicate that early processing in primary sensory and motor cortices remain functionally intact in people diagnosed with hysterical sensorimotor syndromes, suggesting that the impairment stems from task-related inhibition involving high-level processes (for example, suppression of primary motor cortex during paralysis;

primary sensory cortex during sensory loss; and by analogy the medial temporal lobe memory system during amnesia). Neuroimaging research has generally supported this model, indicating that the process of dissociation implicated in symptom formation and expression may be mediated by top-down inhibition involving areas in the prefrontal cortex. This suggests the likely involvement of executive regions modulating attention, response selection, and inhibition -possibly interacting with emotion executive and self-related processing regions -although it is still not clear at what point in the process inhibition occurs and how much variation there might be in the mechanisms that produce similar symptoms. For example, voluntary and involuntary (hysterical) movement inhibition have overlapping but distinct patterns of increased activity in executive systems. [START_REF] Cojan | Motor inhibition in hysterical conversion paralysis[END_REF] Also, evidence of reduced resting metabolism in executive systems (e.g right inferolateral PFC in patients with dissociative amnesia [START_REF] Brand | Functional brain imaging in 14 patients with dissociative amnesia reveals right inferolateral prefrontal hypometabolism[END_REF]) may indicate that in some cases functional (hysterical) symptoms may partly result from a lack of executive engagement of brain systems supporting a basic function (such as retrieval of memories by the medial temporal lobe memory system), rather than task related inhibition.

The neuropsychology of hypnosis

In contrast to hysteria, we can be more confident about the sequence of events, at least in the procedural sense, leading up to the 'end-states' associated with hypnosis. The content of the suggestion is key to determining the nature of the 'hypnotic' phenomenon (e.g. leg paralysis), which can be described as a form of dissociation (or 'compartmentalisation'). [START_REF] Brown | Psychological mechanisms of medically unexplained symptoms: an integrative conceptual model[END_REF] Though the brain mechanisms underlying this process are still far from clear, it is known from neuroimaging studies that altered patterns of brain activity accompany the focused and absorbed 'hypnotic' state and there is particularly strong evidence that distinct brain changes are associated with each of the hypnotic phenomena so far studied. For general reviews on the neuropsychology of hypnosis and suggestion see Oakley and Halligan. [START_REF] Oakley | Hypnotic suggestion and cognitive neuroscience[END_REF] Neuropsychological evidence for dissociation in hypnosis 'State' theories of hypnosis (such as Hilgard's 'neodissociation' theory, and Bowers' 'dissociated control' theory) imply that hypnosis per se involves an altered state of consciousness. An alternative approach, enshrined in 'non-state' theories, suggests that hypnosis does not involve a special altered state of consciousness as part of its causal mechanism. [START_REF] Oakley | Hypnosis and conversion hysteria: a unifying model[END_REF] While this remains a key debate in hypnosis, it does not directly bear on the issue of dissociation, which in principle could operate with or without an 'altered state'.

Indeed, one approach that is not specifically a 'state theory' but does include a dissociative component has been put forward by Oakley. [START_REF] Oakley | Hypnosis and conversion hysteria: a unifying model[END_REF] This model uses 'state' in a purely descriptive, rather than causal sense, to simply describe subjective changes associated with hypnosis (such as mental absorption and focusing of attention), and draws inspiration from Norman and Shallice's contention scheduling / supervisory attentional model of executive function. In Norman and Shallice's model the supervisory attentional system can intervene in non-routine situations specifically to control or modulate actions by deploying top-down attentional resources. Wellpractised action sequences, however, become automatic and can be triggered by environmental circumstances acting directly on lower level executive structures with little conscious involvement ('contention scheduling'). Against this background, Oakley posits a 'Level 1' system of which we have full awareness and involves limited capacity analytical processing and conscious selfreflection. The 'Level 2' system is equivalent to both the supervisory attentional system and contention scheduling system of the Norman and Shallice model, but has the additional role of selecting a subset of currently active representations for processing in the 'Level 1' self-awareness system, which may be reflected in conscious thoughts. In this model, 'suggestions' serve to influence processing in the 'Level 2' system and include environmental prompts, verbal information from others, or our own beliefs, motives and expectancies. This process is facilitated by the focusing of attention, by absorption in internal mental events, and disattention to external stimuli that are typical products of hypnosis induction procedures. Anything which results from influences acting directly on the 'Level 2' system is likely to appear to the 'Level 1' system as automatic or unintentional. Hence, in this model both hypnotic and hysterical symptoms can be explained as produced by suggestion-driven alterations in activity of the Level 2 system, which in turn influences the conscious content of the Level 1 system.

As it is known that individuals differ in their extent of hypnotisability, and that this may reflect intrinsic variations in executive functions, evidence relevant to trait and state differences will be reviewed below.

Hypnotic models of hysteria

At a purely phenomenological level, hypnosis has long been associated with hysteria [START_REF] Ellenberger | The Discovery of the Unconscious: The History and Evolution of Dynamic Psychiatry[END_REF] and more recent empirical work has attempted to examine this link in more detail, first by looking at the association between susceptibility to hypnosis and prevalence of hysteria, and secondly by directly comparing the neuropsychological effects of a hypnotically suggested impairment as a model of an equivalent hysterical symptom.

Trait associations between hysteria and hypnotisability

Only relatively recently have investigators begun to examine whether trait hypnotisability is related to the clinical presentation of hysteria and related symptoms. Bliss [START_REF] Bliss | Hysteria and hypnosis[END_REF] initially reported high rates of hypnotisability in a group of patients with hysteria compared to controls, and this was subsequently replicated in a larger study by Roelofs et al. [START_REF] Roelofs | Hypnotic susceptibility in patients with conversion disorder[END_REF][START_REF] Roelofs | Childhood abuse in patients with conversion disorder[END_REF]. One study, by Moene et al. [START_REF] Moene | Hypnotizability, dissociation and trauma in patients with a conversion disorder: An exploratory study[END_REF] did not find higher levels of hypnotisability in patients, although reported a difference on trait measures of dissociation and found that conversion disorder inpatients were significantly more hypnotisable than similarly diagnosed outpatients.

The association between non-epileptic seizures and hypnotisability is rather more equivocal, however. While Kuyk et al. [START_REF] Kuyk | Hypnotic recall: a positive criterion in the differential diagnosis between epileptic and pseudoepileptic seizures[END_REF] reported on a group of patients with non-epileptic seizures, finding them significantly more hypnotisable than patients with epilepsy, this has not been replicated by Goldstein et al. [START_REF] Goldstein | Dissociation, hypnotizability, coping styles and health locus of control: characteristics of pseudoseizure patients[END_REF] and Litwin and Cardeña. [START_REF] Litwin | Demographic and Seizure Variables, But Not Hypnotizability or Dissociation, Differentiated Psychogenic from Organic Seizures[END_REF] Modelling symptoms with suggestions in highly hypnotisable subjects i) hypnotic paralysis:

Building on their earlier task-based neuroimaging study of hysterical paralysis, [START_REF] Marshall | The functional anatomy of a hysterical paralysis[END_REF] Halligan et al. [START_REF] Halligan | Imaging hypnotic paralysis: implications for conversion hysteria[END_REF] replicated the study methodology, but used a left leg paralysis suggestion in a single hypnotised participant to produce a functionally identical impairment to the patient in their previous study. The areas of brain activation during attempted movement (increased right ACC cortex and right OFC without motor cortex activation) were close to those of their earlier clinical study. It was concluded that in neurocognitive terms, the mechanisms of hypnotically suggested and hysterical paralysis might be similar and that modelling of hysterical symptoms with suggestions remains an important investigative tool. Aiming to address criticisms that the hypnotised participant might have been faking his paralysis, Ward et al. [START_REF] Ward | Differential brain activations during intentionally simulated and subjectively experienced paralysis[END_REF] repeated the study with 12 highly hypnotisable participants who were tested in one part of the study with hypnotically suggested paralysis and in another part were asked, again while hypnotised, to feign the same left leg paralysis in return for a financial reward if they could do so convincingly. While independent clinically trained observers were not able to distinguish hypnotically suggested from feigned paralysis, the hypnotic paralysis condition resulted in brain activation patterns in line with their previous single case study [START_REF] Marshall | The functional anatomy of a hysterical paralysis[END_REF] but markedly different from the feigned condition: specifically, right-sided increases were found in the OFC and cerebellum, and left-sided increases in the thalamus and putamen in hypnotic paralysis compared to increases in left ventrolateral prefrontal cortex and a number of right posterior cortical structures when faking, although the previously reported activation of the right ACC during hypnotic paralysis was not found.

fMRI studies of hypnotically induced paralysis have also been conducted (noting that the fMRI environment does not interfere with hypnotic modelling of hysterical symptoms [START_REF] Oakley | Hypnotic depth and response to suggestion under standardized conditions and during FMRI scanning[END_REF]. As a parallel to their neuroimaging study on hysterical conversion paralysis, [START_REF] Spence | Discrete neurophysiological correlates in prefrontal cortex during hysterical and feigned disorder of movement[END_REF] Cojan et al [START_REF] Cojan | The brain under selfcontrol: modulation of inhibitory and monitoring cortical networks during hypnotic paralysis[END_REF] completed an fMRI analogue study again using the GO-NOGO task with hypnotically induced paralysis. They similarly found normal motor cortex activation during the preparation phase, which was again taken to suggest that movement inhibition was not working through suppression of motor intention. They also reported that anterior prefrontal and ACC activity was increased in all hypnosis conditions, not solely simulated paralysis, suggesting that activity in these areas may be indicative of state-related hypnosis changes and do not reflect a specific inhibitory mechanism. As with their study on hysterical paralysis, they found a greater degree of functional connectivity between the motor cortex and precuneus, and similarly argued that motor inhibition may be mediated through imagery-based and self-reflective processing rather than direct manipulation of top-down executive control.

ii) hypnotic sensory syndrome analogues: While imaging studies of hysterical sensory syndromes have largely focused on conditions like hysterical blindness, deafness and anaesthesia, hypnotic studies have largely focused on analogues of functional pain syndromes (reviewed in Oakley [START_REF] Oakley | Hypnosis, trance and suggestion: evidence from neuroimaging[END_REF]), with the result that there are few direct comparisons of dissociative symptoms and their hypnotic analogues.

iii) hypnotic amnesia: Aiming to simulate psychogenic amnesia, Mendelsohn et al. [START_REF] Mendelsohn | Mesmerizing memories: brain substrates of episodic memory suppression in posthypnotic amnesia[END_REF] used hypnosis to impair selectively memory for specific aspects of a film when a post-hypnotic cue was

given. The study compared high and low hypnotisable individuals, as well as individuals asked to feign high hypnotisability, and reported that only the high hypnotisable group showed impaired recall and this was associated with reduced activity in the left extrastriate occipital lobe and the left temporal pole, as well as increased activity in the left rostrolateral prefrontal cortex. These effects were reversed when the post-hypnotic amnesia suggestion was reversed. These findings are consistent with studies that demonstrate increased activity in inhibitory regions of prefrontal cortex, and decreased activity in medial temporal lobe regions during attempted recollection of stimuli from amnesic relative to non-amnesic periods in psychogenic amnesia (see Table 2).

Summary and Conclusion

In this review we have assessed Charcot's hypothesis that similar brain processes underlie the symptoms of hysteria and suggested effects in hypnosis in relation to contemporary research in cognitive neuroscience and neuropsychiatry. The studies above indicate that hypnotisability traits are associated with a tendency to develop dissociative symptoms, at least in the sensorimotor domain; that dissociative symptoms can be modelled with suggestions in highly hypnotisable subjects; and that hypnotic phenomena engage similar brain processes to those underlying hysteria symptoms. One clear theme to emerge from the findings is that 'symptom' activation, whether clinically diagnosed or simulated with hypnosis, is typically associated with increases in prefrontal cortex activity. This suggests that intervention by the executive system in both automatic and voluntary cognitive processing is key in both hysteria and hypnosis but several issues remain. One of the most pertinent is deciding by what cognitive and neural mechanisms involuntary inhibition of willed movements take place. Numerous studies have implicated ACC and OFC in the inhibition of movement execution (Table 1), whereas the more recent studies of Cojan et al. [START_REF] Cojan | Motor inhibition in hysterical conversion paralysis[END_REF][START_REF] Cojan | The brain under selfcontrol: modulation of inhibitory and monitoring cortical networks during hypnotic paralysis[END_REF] point to the involvement of brain regions involved in affective modulation of motor function (OFC, vmPFC, via VLPFC), and processing external and internal stimuli relevant to the self (vmPFC and precuneus).

This also highlights the issue of the extent to which diverse hysteria-like syndromes share a common neurocognitive basis. For example, while Cojan et al.'s work [START_REF] Cojan | Motor inhibition in hysterical conversion paralysis[END_REF][START_REF] Cojan | The brain under selfcontrol: modulation of inhibitory and monitoring cortical networks during hypnotic paralysis[END_REF] focuses on psychogenic paralyses where motor intention is a clearly defined concept, it is less clear that the findings can be as easily applied to hysterical sensory losses, such as psychogenic blindness, where an intention stage is more difficult to conceptualise. One approach to this problem is to employ experimental designs which parcellate phenomena (movement, sensation, memory) into their respective component phases to help identify at what point, and how, hysterical or suggested effects manifest themselves within and between symptom domains (cf. Cojan et al).

It is also not clear what the limits are with respect to the use of hypnosis as a neurocognitive model for learning about the different forms of hysteria. For example, if we assume there is a close correspondence between the genesis of hypnotic and hysterical symptoms, this would imply that in hysteria there is: a) a focused and absorbed state which in clinical cases may facilitate specific symptomatology; b) that is followed by acceptance of a some form of (internal or external)

suggestion which determines the nature of the 'hysterical' symptom(s) and; c) the phenomenological experience of a dissociation is accompanied by distinct brain changes associated with the particular symptom. However, the following points are noted.

This account sees hysteria as predominantly an auto-suggestive disorder, [START_REF] Oakley | Hypnosis and conversion hysteria: a unifying model[END_REF] whereas in hypnosis the relevant suggestion is traditionally given by another person (hetero-suggestion). However, these are normally initiated intentionally, in contrast to patients with hysterical symptoms who are unaware of, or might be strongly motivated not to acknowledge to themselves or others, any selfsuggestions or mental states (such as a focused attentional state, internal imagery, or expectancies) that may precede symptom onset. It is notable that Charcot considered the 'idea' influencing hysterical and hypnotic phenomena to be unconscious. In the case of hypnosis, however, usually there is awareness of the imaginal content of the suggestion (except where suggestions of loss of awareness or amnesia for the suggestion are made, as in post-hypnotic suggestion). Nevertheless, there is evidence of different styles of hypnotic responding characterised by differing degrees of automaticity in response generation. Hypnotic subjects with a 'concentrative' response style (who simply focus their attention on the content of suggestions) may experience suggested effects as 'happening by themselves' while those with a 'constructive' response style (who actively 'think with' the suggestion or engage in goal-directed imagery) have a greater awareness of active contribution to the suggested effects, even if the resulting symptoms are experienced as involuntary and realistic. [START_REF] Oakley | Hypnosis and conversion hysteria: a unifying model[END_REF] It is not known whether, or to what extent, patients with hysteria display analogues of 'concentrative' and 'constructive' response styles to generate symptoms -and researching this would be difficult because of the interest of patients with hysteria to avoid acknowledging psychological processes that cause or maintain their symptoms. Furthermore, most hysteria symptoms, unlike hypnotic phenomena, are chronic and are not easily terminated or modified by external suggestion. One possibility is that the resistance of these symptoms to change may be because the 'suggestion' that created them is implicit and reinforced internally (Charcot's 'idea') based on a psychologically relevant need, belief, or formative experience. While this has been one of the most popular historical explanations for the aetiology of hysteria (and indeed, still forms the basis of the "psychological factor" required in the DSM-IV diagnosis) the theory remains largely unspecified.

While the recent literature has provided some compelling leads into the understanding of these phenomena, it is apparent that the field still lacks the well-controlled systematically designed studies that could give a clear insight into the neurocognitive processes behind dissociation in both hysteria and hypnosis. We hope this review provides a stimulus for this effort and raises some useful questions to focus future research.

  right amygdala happy faces Greater functional connectivity between the right amygdala and the right supplementary motor = increased activation; = decreased activation; = lack of expected activation; ACC = anterior cingulate cortex; PCC = posterior cingulate cortex; SFG = superior frontal gyrus; OFC = orbitofrontal cortex; DLPFC = dorsolateral prefrontal cortex; vmPFC = ventromedial prefrontal cortex; PFC = prefrontal cortex ii) functional sensory syndromes: Numerous studies have shown that evoked potentials (EPs)

Table 1 .

 1 Summary of SPECT, PET, and fMRI studies of motor and sensory hysteria.

	Study, participants	Impairment	Method	Critical comparison	Changes during task
	Tiihonen et al.	L paralysis,	SPECT	Affected vs recovered	right frontal
	1995[8] Single case	paresthesia		during stimulation of L median nerve	right parietal
	Marshall et al.	L paralysis	PET	Motor execution attempt	right ACC and right OFC
	1997[12]			vs motor preparation	motor cortex
	Single case
	Spence et al.	Hysterical	PET	Patients vs feigners	Patients: Left DLPFC
	2000[13]	weakness			Feigners: Right DLPFC
	Three patients, four
	feigners, two controls
	Vuilleumier et al.	Subjective	SPECT	Affected vs recovered and	contralateral basal ganglia and
	2001[9]	paralysis,		resting state vs vibratory	thalamus in affected state
	Seven patients	weakness, some with sensory loss		stimulus.	ipsilateral pre and post central gyrus on recovery
	Mailis-Gagnon et al.	Chronic pain	fMRI	Affected vs unaffected	ACC
	2003[17] Four patients	with hysterical anaesthesia		body parts and mild vs noxious stimulation.	thalamus, insula, inferior frontal, posterior ACC
					contralateral motor cortices,
					bilateral prefrontal
	Werring et al.	Medically	fMRI	8Hz visual stimulation vs	left posterior ACC, left inferior
	2004[18]	unexplained		darkness	frontal cortex, left insula-claustrum,
	Five patients	vision loss			bilateral striatum and thalami, left limbic structures
					visual cortex
	Burgmer et al.	Left or right-	fMRI	Passive observation of	cortical hand areas during
	2006[19]	sided hand		video clip of moving	movement observation
	Four patients	paralysis		hand or hand at rest.
	Ghaffar et al.	Unilateral	fMRI	Vibratory stimulation of	OFC, ACC, secondary
	2006[20]	conversion		affected area vs	somatosensory cortex, basal ganglia /
	Three patients	disorder, sensory subtype		unaffected area vs bilateral stimulation	putamen, thalamus contralateral primary somatosensory cortex
	Stone et al. 2007[21]	Unilateral	fMRI	Movement in feigners vs	putamen and lingual gyri
	Four patients, four feigners	ankle weakness		controls	bilaterally, left inferior frontal gyrus, left insula
					right middle frontal and OFCs
	de Lange et al.	Arm	fMRI	Mental rotation of	medial prefrontal cortex, superior
	2007[22]	paralysis		affected vs unaffected	temporal cortex
	Eight patients			arm	No change in motor activation
	Kanaan et al. 2007[5]	R sided	fMRI	Recalling traumatic vs	amygdala and right inferior frontal
	Single case	paralysis		non-traumatic memories	lobe
					motor cortex

Cojan et al. 2009[14] L arm fMRI GO-NOGO task: affected left vs right hand; Left hand preparation: right motor cortex, left OFC, right vmPFC and

Table 2 .

 2 Summary of SPECT, PET, and fMRI studies of psychogenic amnesia

	Study,	Impairment	Method	Critical comparison	Changes
	participants
	Markowitsch et	Probable	SPECT	SPECT three weeks post	Resting SPECT: right inferior
	al. 1997[32]	psychogenic	(resting	onset.	frontal and anterior temporal
	Single case	amnesia,	perfusion),	PET 6 months post	cortex
		retrograde	PET	onset. Episodic retrieval:	PET: bilateral precuneus and
			(activation)	old sentences	parietal, right lateral PFC (BA 8)
				(information heard one	and PCC.
				day prior to scanning) vs	Left middle temporal gyrus and
				new sentences	superior temporal gyrus, bilateral
					premotor cortex, left thalamus and
					cerebellum
	Markowitsch et	Psychic shock-	FDG-PET	2 vs 12 months after	At two months: left temporal
	al. 2000[30]	induced mnestic	(resting)	syndrome onset each in	mesial cortex and thalamus.
	Single case	block syndrome		comparison to controls,	At twelve months: normalised
				some recovery at 12	metabolism.
				months mark. ROI in
				temporal lobes and
				thalami only.
	Yasuno et al.	Psychogenic	PET	Interaction: famous face	left medial frontal cortex and
	2000[33]	amnesia,	(activation)	versus gender	right hippocampal region at 12
	Single case, 12	retrograde		discrimination, 2 vs 12	relative to 2 months
	healthy controls			months after syndrome	left ACC and parieto-occipital
				onset. No direct	junction, right occipital cortex,
				statistical comparison	middle lateral PFC (BA 9,
				with controls.	DLPFC) and anterior medial
					temporal region including the
					amygdala at 12 relative to 2
					months
	Yang et al.	Selective	fMRI	Recognisable faces of	Recognisable faces: amygdala,
	2005[34]	retrograde		pre-amnesic period	hippocampus, parahippocampal
	Single case	psychogenic		friends. Unrecognisable	gyrus and insula.
		amnesia, after a		faces of post-amnesia	Unrecognisable and unfamiliar
		severe stressful		period friends.	faces: "significantly less
		event.		Unfamiliar faces. No	activation in the limbic area".
				direct statistical
				comparison.
	Botzung et al.	Psychogenic	fMRI	Recall of residual	Left superior temporal gyrus,
	2007[35]	autobiographical		autobiographical	insula, posterior inferior temporal
	Single case	memory loss for		memories from amnesic	gyrus, precuneus, superior parietal
		period to age 16		period vs recall from	gyrus, cerebellum. Right inferior
				preserved period (rather	occipital gyrus, temporo-occipital
				than successful	junction, superior parietal gyrus.
				inhibition of memories	Bilateral retrosplenial and PCC.
				from amnesic period)	Left parahippocampal gyrus,
					ACC, precuneus, DLPC, middle
					frontal gyrus.
	Hennig-Fast et	Persistent	FDG-PET	fMRI: Presentation of	Resting PET:
	al. 2008[31]	retrograde	(resting,	autobiographical vs	Reduced metabolism right
	Single case, 9	amnesia	acute state	various types of non-	temporo-mesial area.
	healthy controls	following a	only), fMRI	autobiographical	fMRI, acute state,
		dissociative		information. Acute state	autobiographical:
		fugue.		vs one year post-onset.	dorsal ACC and PCC,
				No direct statistical	precentral and subcallosal gyrus,
				analysis of interaction.	medial PFC
					temporo-occipital cortex
					Temporo-occipital activation
					normalised one year post-onset.
	Brand et al.	Dissociative	FDG-PET		right inferolateral PFC
	2009[29]	amnesia, with	(resting)		left hippocampus in 2 out of 14

Acknowledgments and Funding

The authors would like to gratefully acknowledge the role of The Psychiatry Research Trust in funding research which has facilitated the writing of this review article.

Competing interests

None.

Copyright License Statement

The Corresponding Author has the right to grant on behalf of all authors and does grant on behalf of all authors, an exclusive licence (or non-exclusive for government employees) on a worldwide basis to the BMJ Publishing Group Ltd and its Licensees to permit this article (if accepted) to be published in JNNP and any other BMJPGL products to exploit all subsidiary rights, as set out in our licence.