Stephane Maag
email: stephane.maag@it-sudparis.eu

Keywords: MANET, Routing Protocols, Conformance Testing, Model-checker, SPIN

This paper deals with the crucial challenging issue of testing the conformance of the MANET routing protocols. Indeed, because of the inherent constraints of such networks such as a dynamic topology, to formally test these protocols becomes a tough problem. Most of the studies taking into account a formal model of the protocol is faced to the combinatorial state space explosion issue when deploying and analyzing that model. In our work we present how to cope with that problem by drawing inspiration of the model-checker research domain and an integration of a component-based testing algorithm dedicated to the automatic generation of OLSR test sequences from a formal model written in Promela.

A Component based Testing Technique for a MANET Routing Protocol

Fatiha Zadi * † and Mounir Lallali * †

I. INTRODUCTION

A wireless mobile ad hoc network (MANET) is a collection of mobile nodes that communicate each other. This kind of network is self-organizing and does not depend on any predefined infrastructure neither centralized administration. By this way, the network may rapidly be deployed. Every node participates to the communication establishment as well reliable operations. Nevertheless, the nodes movement may lead to a volatile topology providing then numerous interconnections. Since the network is infrastructureless, some of the nodes have to behave as routers by interacting using their radio range with open transmission medium in order to establish end-to-end communications. Therefore, due to the inherent constraints of such networks as well the limited resources of the nodes, reliable and efficient routing protocols are needed leading then to the challenging issue of testing the MANET routing protocols.

Many protocols to route the packets through a MANET have now been proposed and several implementations have been provided. Besides, many works proposing testing techniques have been published. However, most of them are related with simulation or emulation testbeds in order to check performance aspects of these protocols. Very few of them take into account their functional properties as well by applying formal approaches. But as established in [1], simulators such as NS-2 may contain erroneous implementations (in their case AODV) on which many studies are based, illustrating by this manner that formal testing techniques are crucial to test such routing protocols.

From that observation, conformance testing techniques that ensure correct protocol implementations have become more and more essential for the development of reliable communicating systems. Due to the complexity to test the systems whose the size becomes huge, the designers use some modularity concepts to model them. Indeed, in many cases and more specifically with the formal model of a MANET whose the topology may be often modified, the analysis of its formal specification may be difficult failing to reach a test objectives and then to generate the test sequences.

That is why component-based testing approach has become a main research area. Its main goal is to generate test sequences for a component embedded in a whole system. The techniques are known for several years now [START_REF] Bourhfir | A guided incremental test case generation procedure for conformance testing for CEFSM specified protocols[END_REF], [START_REF] Cavalli | A servicecomponent testing method and suitable CORBA architecture[END_REF] but the constraints occurring when testing a MANET routing protocol lead most of the times to the combinatorial explosion of the model [START_REF] Maag | Testing methodology for an ad hoc routing protocol[END_REF]. That is why some efforts have been done to combine techniques provided by both the testing and modelchecking communities.

A. Related Works

Although there are many works about testing and verify a MANET [START_REF] Viana | One step forward: Linking wireless self-organising networks validation techniques with formal testing approaches[END_REF], from our knowledge, there is no publication on the generation of test sequences from the model of a MANET routing protocol by using model-checking techniques. Nevertheless, we may cite the following works from which we draw inspiration.

For instance, the authors of [START_REF] Xu | Generating regression tests via model checking[END_REF] propose to use the modelchecker SPIN [START_REF] Holzmann | The SPIN Model Checker -Primer and Reference Manual[END_REF] in order to automatically generate regression tests. The technique is dedicated to the test of software. Nevertheless, the case study as well the model is very simple and since the model-checker is not modified, the approach is not scalable. In [START_REF] Beyer | Generating tests from counterexamples[END_REF], the model-checker Blast is applied [START_REF] Beyer | The software model checker blast: Applications to software engineering[END_REF]. This latter has been modified in order to generate test suites guaranteeing a full coverage of the software. Nevertheless, in this approach no formal specification is performed and it is much more dedicated to the software testing rather than to the routing protocol one. Indeed, it seems difficult with that technique to observe or control (as needed in a testing architecture) interfaces between some protocol layers.

The same issues are met with the work presented in [START_REF] Zheng | A model checking based test case generation framework forweb services[END_REF]. The authors apply the Nu-SMV model-checker [START_REF] Cimatti | Nusmv: a new symbolic model verifier[END_REF] in order to test the conformance of different kinds of interfaces of Web Services. They use unit and integration testing technique through interfaces between the formal specifications and the data flow. However for a MANET routing protocol, the specification represents several different topologies and to access interfaces embedded in a wireless and mobile node may be difficult. Another interesting work is the one published by Heimdahl et al. [START_REF] Rayadurgam | Generating mc/dc adequate test sequences through model checking[END_REF] where several case studies are analyzed through the application of Nu-SMV. The approach is interesting and original providing relevant results but the model can not contain any variables which significantly reduce the usability in the MANET because of the packet exchanges as well the important flows.

In this paper we cope with these constraints and bridge the existing gap in order to automatically generate test sequences for the conformance of the routing protocols in a MANET.

B. Contributions of this Paper

• While most of the works on MANET routing protocol testing is performed through simulator and emulator, we apply a formal testing approach based especially on the automatic generation of test scenarios from a formal model. • Taking into account the IETF RFC, we specified a formal model of the OLSR protocol [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR) -RFC3626[END_REF] in Promela [START_REF] Gerth | Concise Promela Reference[END_REF] allowing to provide an OLSR network containing any number of nodes (because of the instantiation of a node process). • Due to the mobility of the nodes, most of the common testing techniques are irrelevant for the MANET. We draw therefore inspiration from model-checking methods where deployed state compression techniques are reliable.

• We adapt the model-checker SPIN with an efficient generation testing algorithm by developing a tool prototype. Indeed, as mentioned above, several studies tackled that problem but no one applied a component-based testing approach to a model-checker in order to take into account the inherent constraints of a MANET and then avoid the state space explosion issue. • We automatically generate test sequences for some OLSR test objectives showing by the way that our adaptation is more efficient in some cases than the originating modelchecker. The rest of the paper is organized as follows. In the Section II, we present the main characteristics of OLSR, the concept of component-based conformance testing, the OLSR formal model as well the language utilized to specify the protocol and the SPIN model-checker. Then our test sequence generation approach is illustrated in the Section III. In the Section IV, OLSR test objectives are defined and designed from which test sequences are generated by SPIN and our tool. We comment the results in the Section IV-B before concluding in Section V.

II. OLSR COMPONENT-BASED TESTING

This section introduces the protocol OLSR on which our experiments are conducted. We define the concept of componentbased conformance testing, present the SPIN model-checker and illustrate the Promela model of OLSR.

A. The Optimized Link State Routing Protocol

The Optimized Link State Routing Protocol (OLSR) [START_REF] Clausen | Optimized Link State Routing Protocol (OLSR) -RFC3626[END_REF] is a proactive protocol that needs to react quickly to topology changes and find alternative paths consequently. For that purpose, it maintains several routing tables and exchanges topology information between nodes of the network. OLSR uses specialized aggregation nodes in order to reduce the number of packets used in the flooding of neighborhood information. These nodes are the Multipoint Relay (MPR). They are selected as MPR by some neighbor nodes and they announce periodically the topology information through Topology Control (TC) messages to the nodes which have selected it as MPR. In route calculation the MPR are also used to form the route from a given node to any destination in the network.

B. Component-based Conformance Testing

Conformance testing establishes the conformance of an implementation to its specification. In other words, conformance testing is devoted to the implementation behaves as it is expected by the specification. Commonly, specification is used to generate the tests for observable interactions of the implementation. Those tests are then executed against the real implementation and we observe if the outputs of this one are the expected ones. Accordingly, a verdict is emitted, a PASS when the outputs are those expected, a FAIL in the other case and an INCONCLUSIVE when non determinism is observed.

In case of component-based testing, the accent is put on the interactions of a particular implementation component in the context of the other components. This kind of test is also known as embedded component testing. Indeed, no direct access is given to the component to be tested. To perform component testing, a method is needed to drive the derivation of tests, i.e., to reach in the whole specification the transitions of the component to be tested. In our methodology, the component is characterized by its behavior in terms of interaction with its environment. The behavior of the component is expressed as test objectives to cover.

C. Promela and the Model-Checker SPIN

Promela (PROcess MEta LAnguage) [START_REF] Gerth | Concise Promela Reference[END_REF] is the modeling language supported by the model-checker tool SPIN. Promela is a high-level description language derived from the C language to specify communication systems. In Promela, system components are described as processes that can interact either by message passing, via channels, or memory sharing via global variables. The communication can be synchronous or asynchronous. Processes specify behavior of the concurrent entities of the distributed system. These processes can be instanciated such that wireless mobile nodes may be obtained from a single process. Channels and global variables define the environment in which the process run.

SPIN can be used for formal verification of distributed communication systems. The system description is given in Promela and requirements to be verified can be directly written as assertions in the code or by specifying properties as formulas in propositional linear temporal logic PLTL [START_REF] Pnueli | The temporal logic of programs[END_REF]. SPIN works on-the-fly, it means that the tool does not need to construct the complete state space to verify a property; instead it is done dynamically during processing. SPIN provides abstraction techniques such as states fusion, partial order reduction or BDD-like storage techniques.

D. Formal Model of OLSR

To generate the tests, we first need to model in a formal way the protocol. OLSR was specified in Promela which can be viewed as a transition system. This choice has been motivated especially because of the efficient model-checker SPIN and the existing related works. Our specification is devoted to the test of the OLSR implementation embedded in one single node in the context of other OLSR nodes. Besides, we need to take into account the constraints inherent to such networks.

We have to consider the mobility of nodes, the broadcasting of control messages such as HELLO messages and the dynamic modifications of the topology. These aspects raise challenges for the modeling. In our specification, we have made some choices:

• Broadcast: In our specification, broadcast is specified by unicasting the packets to every node taking into account a matrix of connectivity. By unicasting we mean that all packets are sent before enabling any other action. In Promela, the messages are sent to all neighbors through channels associated to the nodes.

• Connectivity: In our specification, the communications between the nodes are specified in using a dynamic matrix (the number of nodes varies), symmetrical of size N × N where N is the node number in our network. The matrix is symmetrical because we suppose that all links are bidirectional. This assumption allows to rapidly observe the routes creation and the packets sending as well.

Nevertheless, unidirectional links are easily specifiable in using an asymmetric matrix. In addition, in order to reduce the complexity, we suppose that the nodes are connected or not connected (1 or 0 in the matrix). We do not design intermediate state connection as we could have with the protocols of the lower layers (link/MAC). Indeed, our objective is the test of routing functionalities and not the physical or link layer studies. We use a global variable MaxNodes that instantiates the maximum number of nodes to be created.

• Topology: The topology can change in the specification by applying modification on the connectivity matrix either manually in having beforehand chosen the different moves of the nodes, or randomly.

To cope with a reasonable model, we did some abstractions. First, we do not consider the extensions that are mentioned for IPv6, we only consider IPv4. To simplify, we also do not take into account the HNA (Host Network Association) which is used to have a link to the other networks. We have also simplified the number of interfaces of each node by considering a node with a single interface characterizing its main address. Short pieces of the OLSR specification are illustrated by the Part 1 and Part 2 of Section IV-A.

III. COMPONENT TESTS GENERATION AND SPIN MODEL-CHECKER ALGORITHMS

In this section, we present an embedded test generation method, the Hit-or-Jump (HoJ) algorithm [START_REF] Cavalli | Hit-or-Jump : An algorithm for embedded testing with applications to IN services[END_REF] which is integrated into the model-checker SPIN [START_REF] Holzmann | The SPIN Model Checker -Primer and Reference Manual[END_REF]. The integration of our algorithm in the SPIN tool permits to obtain a guided random walk to generate OLSR test sequences. We propose a new algorithm to adapt the acceptance cycle detection algorithm of SPIN by using the HoJ method. Test objectives are used to describe finite behavior and accept state detection algorithm.

A. Outline of the HoJ Algorithm

The HoJ algorithm [START_REF] Cavalli | Hit-or-Jump : An algorithm for embedded testing with applications to IN services[END_REF] introduced in SPIN allows to cover all the interactions of the component in its context. The essence of our approach is as follows. At any moment, we conduct a local search from the current state in a neighborhood of the deployed Promela transition system. If an untested part of the component is found (a Hit, i.e., an interaction that has to be tested), we keep it for the final test sequence, and then continue the search process from there. Otherwise, we move randomly to the frontier of the neighborhood searched (Jump), and resume the process from there. This procedure avoids the building of a whole system accessibility graph. Accordingly, the space required is determined by the user, e.g., a depth limit or a maximum number of states, and it is independent of the system under consideration. On the other hand, a random walk may get trapped at certain part of the component under test [START_REF] Lee | Conformance Testing of Protocols Specified as Communicating Finite State Machines -A Guided Random Walk Based Approach[END_REF]. Our algorithm is designed to jump out of the trap and pursue the exploration further. We build at each step a partial accessibility graph to avoid the state-number explosion problem mentioned before. The algorithm finally produces a test sequence as a transition tour of the component in its context.

B. SPIN and HoJ integration

SPIN considers undesirable properties to be checked, which are defined either by Promela never claims (i.e., temporal claims) or directly by a PLTL formula. SPIN transforms the claim in a Bchi automaton and computes the synchronous product of this automaton with the Bchi automaton of the system (i.e., the Promela model). It means that the intersection of these both automata languages is produced providing then a scenario illustrating what should never happen.

In our method, the test objectives (i.e., the transitions of the component to be covered) describe a finite desirable behavior. Therefore, by considering the negation of these objectives (a set of propositions (i.e., boolean expressions) on the system states) and by processing the above mentioned product, we provide a test sequence related to the test objectives.

To control the system execution, a synchronous product of the sequence specified in the temporal claim with the interleaving sequences specified in the OLSR Promela model is provided. This synchronous product is a new Bchi automaton in which every state is defined as a pair (s, n) where s is a state from the system automaton, and n a state from the never claim. Every transition in the new automaton is defined by a pair of transitions (a, p), where a is an action of the system, and p a proposition of the never claim. This transition can only occur if the proposition p is valid in s (i.e., the source state of the transition). Note that an accept state (s, n) is a state of the product automaton where s is a state that corresponds to an uncovered component transition of the system and n is a state of the claim automaton where a marked proposition (by an accept label) is reached. Instead of seeking an acceptance cycle as done in the nested depth-first search (NDFS) algorithm of SPIN, our method search a path (without cycles) going from the initial state of the product automaton to the stop state (s, n) where n is a final state of the claim automaton. This path must contains all the accept states of the product automaton.

C. Accept State Detection Algorithm

As above mentioned, the main goal is to reach a stop state of the synchronous product automaton. During this depthfirst search (DFS), all the accept states (describing the test objectives) must be reached (cf. Figure 2). If a depth limit d (defined by the user) is reached from a current state (initialized to the initial state in line 1 of Figure 1) without detecting an accept state or stop state, a jump of depth d is carried out by building a partial search tree and by choosing uniformly and randomly a leaf node of this tree (cf. lines 16-20 in Figure 1). This tree has as root the current state and also has a depth d. The selected leaf node will be the new current state (as in line 21). From this later state, a new partial search (of an accept state or stop state) is performed (as in line 22). The algorithm terminates when a stop state is reached or when the complete exploration of the state space is performed (cf. line 7). Finally, the obtained path from the initial state to the stop state, which contains all the accept states constitutes the test sequence. The algorithm is depicted in the Figure 1 and illustrated by the Figure 2.

D. The Formulation of Test Objectives

The SPIN tool accepts correctness properties expressed in PLTL or directly in Promela never claim. In SPIN, the never claim must express a negative property. In our component test generation method, we use the never claim to describe the test objectives that model the OLSR component transitions to be tested. These test objectives describe finite desirable behaviors. Their formulation consists of a set of logical propositions on the model state which can correspond to the triggering of transitions or to the evaluation of variables. is marked by an accept label. We give below an example of a never claim with one accept label (i.e., accept prop1 in line 6 of the following claim) that identifies where the test objective holds. The never claim is noted ¬(⋄ prop1) in PLTL.

✂ ✁

In PROMELA, it is noted as in the following: ✂ ✁ The loop is left when all the propositions (i.e., test objectives) are checked in order to finally reach the final state of the never claim. For our experiments on OLSR (see Section IV), we need to define a never claim with several accept label that mark a set of propositions.

IV. EXPERIMENTAL RESULTS

Our experiments have been performed with a Processor Intel Pentium 4 (CPU 2.4GHz, RAM 512MB, Cache size 512 MB). The OLSR test sequences have been generated both by SPIN and our prototype tool based on the model-checker in which HoJ has been integrated, allowing then to compare the results.

A. OLSR Test Objectives

This section presents some examples of test objectives formulation. For sake of simplicity, we only detail four OLSR properties. The experiments are performed on a network modeled with five nodes moving randomly. We nevertheless assume that this random topology allows to observe the following properties especially to generate the respected test sequences. We formalize the test objectives for the node n1.

• Test Objective 1: To test the asymmetric link process.

A node n1 sends a HELLO message to its neighbors. Then, it can declare that it has an asymmetric link with a node if this node sends back a HELLO message with the source n1 added in its ASYM set. • Test Objective 2: To test the symmetrical link process.

A node n1 which has already a asymmetrical link with a node n2, can declare to have a symmetrical link with n2 if it sends a HELLO message saying to n1 that it has a symmetrical link with him. • Test Objective 3: To test that only a node that is established as a MPR can send TC messages (see Figure 3). • Test Objective 4: To test that a HELLO message is sent after a Hello interval. To perform our test generation, we express these test objectives inside the never claim. We identify in the formal specification, the component involved in the design of the test objectives. For that purpose, we label in the specification the transitions to be reached. These transitions will belong to the test sequence.

In order to generate the test sequence for the test objective 1, we put two (control-flow) labels in the specification, one in the HELLO message generation part (cf. label L0 in line 4 of the Part 1) and a second in the part devoted to the classification of the links (cf. label L1 line 8 of the Part 2). We show below how the labels L0 and L1 are put on the Promela specification. In this test objective 1, first a HELLO message has to be sent from n1 to n2 (cf. label L0 of the Part 1), then n2 receives it, answers and n1 classifies its link to this node as asymmetric (cf. label L1 of the Part 2). Two steps are needed in the never claim and two global variables are defined as it follows:

✄ 1 #define p1 (Node[1]@L0) 2 #define p2 (Node[1]@L1)
✂ ✁ Note that the variable p1, for instance, takes the value true if its associated process instance (N ode[1]) is currently in the state marked by L0 which is the first step of the test objective 1. Let checked be an array of boolean indexed by the boolean variables p1, p2 such that checked(p1) = true meaning as an example that the variable p1 takes true at least once. These boolean variables p1, p2 are used in the design of the test objective 1. Its associated never claim is described by the two propositions: prop1 = p1 ∧ ¬checked(p1); prop2 = p2 ∧ ¬checked(p2) ∧ checked(p1). The never claim of the test objective 1 is described as follows:

B. Results and Discussions

This section presents a comparative table (see Figure I) between the results obtained by the original SPIN and by our own prototype for the OLSR protocol in the same context. We have exercised our method to test a specific node in the context of four other nodes. The test objectives are expressed in order to cover some OLSR properties. We compared the stored states number (in data structures) and the stored or matched transitions number.

We note that for the two tools (SPIN and our own prototype), we obtained the same test sequence with the same depth. We did not try to obtain different test sequences by changing the depth of search. Our objective is to achieve to reach the transitions in the OLSR Promela model. We can notice that for the MPR with the SPIN tool, we did not achieve to reach the test objective related to the computation of the MPR. Nevertheless, with our prototype we obtain a result for this test objective. We can explain these results by our efficient strategy to explore the system. Indeed, we can get out a part of the specification that is not relevant for our search with the jump strategy. SPIN DFS carries out a back-tracking if the maximum search depth is reached without reaching an accept state or a stop state. Indeed, a maximal depth limit is predefined and the value is high.

On the contrary, our prototype works on partial graph and traverses shortest path due to the small depth limit set to obtain a jump. In this case we only back-track to the root node of the partial graph (i.e., current state) and executes a jump. Moreover, the jump allows us to get out the trap and to search our test objectives in other part of the graph. We can avoid very long test sequences with uninteresting paths according to a good depth search choice. To explain more precisely the MPR test objective, we have to say that the other test objectives are related to a subset of nodes as these properties are computed locally for a node. On contrary, for the property of MPR, the computation are done for all the nodes of the network, there is no knowledge a priori of which node can be computed as MPR. The flooding of HELLO messages and the classification of links are performed for all the neighborhood. This computation can explain the state space explosion even if the network is reduced to five nodes. With our modified version of SPIN, we obtain a result after a jump. In that work, we generated the test sequences related to OLSR properties. Since they were provided from a Promela model, they are represented as input/outputs sequences. Therefore, a following work is to formulate them in a executable manner and to apply them on a real implementation under test of OLSR as it is mentioned in a previous work [START_REF] Maag | A formal validation methodology for manet routing protocols based on nodes' self similarity[END_REF] in which we define testing architectures.

V. CONCLUSION

This paper discussed a new approach to generate test cases for an embedded component, which is a MANET routing protocol. This method conducts a search in the partial product of the whole formally specified OLSR system and the automaton of the formula that represents the test objectives, i.e., the transitions of the component to cover.

We have implemented inside the model-checker SPIN an efficient testing algorithm that allows to avoid the state space explosion. Therefore, through an OLSR specification written in Promela, we have exercised our prototype against SPIN. While the results are quite similar if the component to reach is not so deep into the model (that is, it does not need an important testing coverage), they differ when many interactions between the nodes are needed to observe a test objective. Indeed, our approach may take into account the dynamic topology of MANET networks and then provides test verdicts whereas this is not the case for the model-checker.

An immediate line of future is to exercise our prototype with different criteria of coverage. We present in the paper a coverage criterion that is the transitions coverage in order to produce a transitions tour of the component in its context. This criterion can be rapidly changed, may one want only to test some critical functionalities of a module. Specifically, it would help to test the scalability of our approach with dozen of nodes. Besides, it will be interesting to validate our approach through complex OLSR testing objectives. For that aspect, requirements such as HNA and two OLSR interfaces should be added to the formal model.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Accept State Detection Algorithm

Fig. 3 .

 3 Fig. 3. MSC of the test objective 3

3 : 4 : 5 fi ; i++; 6 : 2 if 3 : 4 -> linkCode_LT = SYM_LINK; 5 :: else -> 6 if 7 : 8 - 9 : 2 :

 3456234567892 : (Node_1[id].Node_2[i] == UNSPEC_LINK) -> skip; : else -> L0 : Ch[i] ! HELLO_MESSAGE,sendMe; : else -> break; 7 od; ✂ ✁ Part 1: Promela Specification of HELLO Message Generation with the Label L0 ✄ 1 inline calculLinkType(indice, linkCode_LT) { : (( LinkSet[indice].L_SYM_time.sec > timer.sec) || ((LinkSet[indice].L_SYM_time.sec == timer.sec) && (LinkSet[indice].L_SYM_time.msec >= timer.msec))) : (( LinkSet[indice].L_ASYM_time.sec > timer.sec) || ((LinkSet[indice].L_ASYM_time.sec == timer.sec) && (LinkSet[indice].L_ASYM_time.msec >= timer.msec))) > linkCode_LT = ASYM_LINK; L1 : skip; : else -> linkCode_LT = LOST_LINK; Promela Specification of Links Classification with the Label L1

4 : 5 :

 45 : prop1 -> checked(p1) = true; : prop2 -> checked(p2) = true; break; The never claim of the test objective 1


Pau Amaro-Seoane

Sofiane Aoudia

Stanislav Babak

Pierre Binétruy

Emanuele Berti

Alejandro Bohé

Chiara Caprini

Monica Colpi

Neil J Cornish

Karsten Danzmann

Jean-François Dufaux

Jonathan Gair

Oliver Jennrich

Philippe Jetzer

Antoine Klein

Ryan N Lang

Alberto Lobo

Tyson Littenberg

Sean T Mcwilliams

Gijs Nelemans

Antoine Petiteau

Edward K Porter

Bernard F Schutz

Alberto Sesana

Robin Stebbins

Tim Sumner

Michele Vallisneri
email: michele.vallisneri@jpl.nasa.gov

Stefano Vitale

Marta Volonteri

Henry Ward

Low-frequency gravitational-wave science with eLISA/NGO

Keywords: numbers: 04.25.dg, 04.80.Nn, 95.55.Ym, 97.80.Af, 97.60.Lf, 98.35.Jk, 98.62.Js, 98.80.Cq

We review the expected science performance of the New Gravitational-Wave Observatory (NGO, a.k.a. eLISA), a mission under study by the European Space Agency for launch in the early 2020s. eLISA will survey the low-frequency gravitational-wave sky (from 0.1 mHz to 1 Hz), detecting and characterizing a broad variety of systems and events throughout the Universe, including the coalescences of massive black holes brought together by galaxy mergers; the inspirals of stellar-mass black holes and compact stars into central galactic black holes; several millions of ultracompact binaries, both detached and mass transferring, in the Galaxy; and possibly unforeseen sources such as the relic gravitational-wave radiation from the early Universe. eLISA's high signalto-noise measurements will provide new insight into the structure and history of the Universe, and they will test general relativity in its strong-field dynamical regime.

Introduction

Over the last two decades, as many as 2,500 articles on space-based gravitationalwave (GW) detection included mentions of LISA (the Laser Interferometer Space Antenna) [START_REF] Prince | LISA: Probing the Universe with Gravitational Waves list[END_REF][START_REF] Jennrich | [END_REF]3], the space-based GW interferometer planned and developed together by NASA and ESA. This collaboration between the two agencies ended in early 2011 for programmatic and budgetary reasons. In fact, LISA, as brought forth by the entirety of those papers, was more than a space project: it was the concept (and the cherished dream) of a space-based GW observatory that would explore the lowfrequency GW sky, in a frequency band (10 -4 -1 Hz) populated by millions of sources in the Galaxy and beyond: compact Galactic binaries; coalescing massive black holes (MBHs) throughout the Universe; the captures of stellar remnants into MBHs; and possibly relic radiation from the early Universe.

All along its evolution, the LISA design remained based on three architectural principles developed and refined since the 1970s: a triangular spacecraft formation with Mkm arms, in Earth-like orbit around the Sun; the continuous monitoring of inter-spacecraft distance oscillations by laser interferometry; drag-free control of the spacecraft around freely falling test masses, the reference endpoints for the distance measurements, achieved using micro-Newton thrusters. The current incarnation of this concept is eLISA (evolved LISA), a mission under consideration by ESA alone (under the official name of NGO, the New Gravitational-wave Observatory) for launch in 2022 within the Cosmic Vision program.

The eLISA design would achieve a great part of the LISA science goals, as presented in [START_REF] Prince | LISA: Probing the Universe with Gravitational Waves list[END_REF], and endorsed by the 2010 U.S. astronomy and astrophysics decadal [START_REF] Blandford | The Astronomy and Astrophysics Decadal Survey sites[END_REF]. This article surveys eLISA's science performance (sensitivity, event rates, and parameter estimation), as scoped out by these authors in the spring and summer of 2011, and as discussed in full in Ref. [START_REF] Amaro-Seoane | [END_REF]. This article is organized as follows: in Sec. 2 we provide a very brief overview of eLISA and its GW sensitivity, while later sections are organized by science topics. In Sec. 3, we discuss the astrophysics of compact stellar-mass binaries in the Galaxy; in Sec. 4, the origin and evolution of the massive BHs found at the center of galaxies, as studied through their coalescence GWs; in Sec. 5, the dynamics and populations of galactic nuclei, as probed through the captures of stellar-mass objects into massive BHs; in Sec. 6, the fundamental theory of gravitation, including its behavior in the strong nonlinear regime, its possible deviations from general-relativistic predictions, and the nature of BHs; in Sec. 7, the (potentially new) physics of the early Universe, and the measurement of cosmological parameters with GW events. Last, in Sec. 8 we draw our conclusions, and express a wish.

The eLISA mission and sensitivity

We refer the reader to [START_REF] Amaro-Seoane | [END_REF] for a detailed description of the eLISA architecture. eLISA has a clear LISA heritage, with a few substantial differences. The eLISA arms will be shorter (1 Mkm), simplifying the tracking of distant spacecraft, alleviating requirements on lasers and optics, and reducing the mass of the propellant needed to reach the final spacecraft orbits. The orbits themselves may be slowly drifting away from Earth, again saving propellant, and the nominal mission duration will be two years, extendable to five. As much existing hardware as possible, including the spacecraft bus, will be incorporated from the LISA Pathfinder mission, scheduled for launch by ESA in 2014. The three spacecraft will consist of one "mother" and two simpler "daughters," with interferometric measurements along only two arms, for cost and weight savings that make launch possible with smaller rockets than LISA. (Note that LISA was to be built with laser links along the three arms, but it was not a requirement that they would operate throughout the mission.)

The eLISA power-spectral-density requirement for the residual test-mass acceleration is S acc (f ) = 2.13 × 10 -29 (1 + 10 -4 Hz/f ) m 2 s -4 Hz -1 , while the positionnoise requirement breaks up into S sn (f ) = 5.25 × 10 -23 m 2 Hz -1 for shot noise, and S omn (f ) = 6.28 × 10 -23 m 2 Hz -1 for all other measurement noises. With these requirements, eLISA achieves the equivalent-strain noise plotted in Fig. 1, and approximated analytically by

S(f ) = 20 3 4 S acc (f ) + S sn (f ) + S omn (f ) L 2 × 1 + f 0.41 c/2L 2 , (1)
where L = 1 Mkm, c is the speed of light, and S(f ) has already been normalized to account for the sky-averaged eLISA response to GWs. This noise allows the detection of a strain of about 3.7 × 10 -24 in a two-year measurement with an SNR of 1. The requirement on the useful measurement band is 10 -4 Hz to 1 Hz, with a goal of 3×10 -5 Hz to 1 Hz.

Compact binaries in the Galaxy

The most numerous sources in the low-frequency GW sky observed by eLISA will be short-period binaries of two compact objects such as white dwarfs (WDs) or neutron stars (NSs). These systems have weak GW emission relative to the much heavier massive-BH binaries, but are numerous in the Galaxy and even in the Solar neighborhood. To date, astronomers have observed about 50 ultra-compact binaries with periods shorter than one hour, comprising both detached systems and interacting binaries where mass is being transferred from one star to the other. Wide-field and synoptic surveys such as SDSS and PTF (and in the future, PanSTARRS, EGAPS, and LSST) will continue to enlarge this sample [7,8]. Interacting ultra-compact binaries with NS accretors are found by all-sky X-ray monitors and in dedicated surveys [9]. A large subset of known systems will be guaranteed verification sources for eLISA [10]; their well-modeled GW signals will be detected within the first few weeks to months of operation, verifying instrument performance. The most promising verification binaries are the shortest-known-period interacting systems HM Cnc (with Figure 1. eLISA equivalent-strain noise, averaged over source sky location and polarization, as a function of frequency. The solid red curve was obtained with the LISACode 2.0 simulator [START_REF] Petiteau | [END_REF], while the dashed blue curve is plotted from Eq.

f [Hz]
(1). For comparison, the dotted green curve shows the LISA sensitivity.

a period of 5.4 m [11]), V407 Vul (P = 9.5 m), and ES Cet and the recently discovered detached system SDSS J0651+28 (P = 12 m; [12]). eLISA will individually detect and determine the periods of several thousand currently unknown compact binaries (in our estimate, 3,500-4,100 systems for a two-year observation; [START_REF] Amaro-Seoane | [END_REF]14]), while the combined signals of tens of millions unresolvable systems will form a stochastic GW foreground at frequencies below a few mHz ( [15,16]; see Fig. 2.) About ∼ 500 close or high-frequency (> 10 mHz) sources will be seen with large SNRs, allowing the determination of sky position to better than 10 deg 2 , of frequency derivative to 10%, of inclination to 10 deg, and of distance to 10%. This large sample will allow a detailed study of the Galactic population, which is poorly constrained by EM observations and theoretical predictions [17].

Detections will be dominated by double WD binaries with the shortest periods (5-10 minutes). Their mergers are candidate progenitors for many interesting systems: type Ia [18] and peculiar supernovae [19,20]; single subdwarf O and B stars, R Corona Borealis stars and maybe all massive WDs [21]; and possibly the rapidly spinning NSs observed as ms radio pulsars and magnetars [22]. These binaries are short lived, very faint for telescopes, and scarce (few thousand in the whole Galaxy), so GWs will provide a unique window on their physics. eLISA will determine their merger rate, constrain their formation, and illuminate the preceding phases of binary evolution, most notably the common-envelope phase.

Common-envelope evolution is crucial to most binary systems that produce high-energy phenomena such as γ-ray bursts and X-ray emission, but our understanding of its physics and outcome is limited [23,24] and challenged by observations [25,26]. The standard scenario is as follows. Most stars in the Universe are in binaries, and roughly half of binaries are formed at close enough separations that the stars will interact as they evolve into giants or supergiants. Following runaway mass transfer, the companion of the giant can end up inside the outer layers (the envelope) of the giant; dynamical friction reduces the velocity of the companion, The solid/dashed black curves trace instrument noise alone/with confusion noise. Spectra are shown for the TDI observable "X" (see, e.g., [13]); subtraction is simulated for a two-year observation and threshold SNR = 7; resolvable systems are placed a factor SNR 2 above the combined instrument and confusion noise. Inset: time series of the residual foreground, which carries information about the number and distribution of binaries in the Galaxy.

shrinking the orbit and transferring angular momentum and energy into the envelope; the envelope eventually becomes unbound, leading to a very compact binary consisting of the core of the giant and the original companion [START_REF] Paczynski | Common Envelope Binaries Structure and Evolution of Close Binary Systems[END_REF].

eLISA will also test dynamical interactions in globular clusters, which produce an overabundance of ultra-compact X-ray binaries consisting of a NS accreting material from a WD companion. The eLISA angular resolution will be sufficient to distinguish WD binaries in clusters, verifying whether they are also plentiful.

The eLISA measurements of individual short-period binaries will provide a wealth of information on the physics of tidal interactions and the stability of mass transfer. For detached systems with little or no interaction, the evolution of the GW signal is dominated by gravitational radiation:

h ∝ M 5/3 f 2/3 D -1 , ḟ ∝ M 5/3 f 11/3 , f = 11 3 ḟ f , ( 2
)
where h is the GW strain, f the GW frequency, M = (m 1 m 2 ) 3/5 /(m 1 + m 2 ) 1/5 is the chirp mass with m 1 , m 2 the individual masses, and D is the distance. Thus, measuring h, f , and ḟ (which will be possible in 25% of systems) provides M and D; measuring also f (which may be possible for a few high-SNR systems) tests secular effects from tidal and mass-transfer interactions. Short-term variations are not likely to prevent detection [START_REF] Stroeer | [END_REF], and the precision of ḟ and f determination increases with the duration of the mission.

Tidal interactions are possible when at least one binary component does not corotate with the orbital motion, or when the orbit is eccentric. Their strength is unknown [29], and has important consequences on the tidal heating (and possibly optical observability) of WD binaries, as well as the stability of mass transfer. This process begins after gravitational radiation shrinks detached binaries to sufficiently close orbits (with P ∼ a few minutes) that one of the stars fills its Roche lobe and its material can leak to the companion. Mass transfer can be self-limiting, stable, or unstable, depending on the resulting evolution of the orbit and of the donor radius. Unstable transfer leads to mergers; stable systems (the interacting WD binaries known as AM CVn systems, as well as ultra-compact X-ray binaries) will be observed -and counted -by eLISA in the early stages of mass transfer [30]. Efficient tidal coupling can return angular momentum from the accreted material to the orbit [29,31,32], slowing the inspiral and increasing the fraction of WD binaries that survive the onset of mass transfer from 0.2% to 20% [33].

The unresolved foreground from Galactic binaries will provide a light additional noise component for the detection of loud broadband signals (see Fig. 2), but it also contains precious astrophysical information. Its overall level measures the total number of binaries (mostly double WDs); its spectral shape characterizes their history and evolution; and its yearly modulation [34], together with the distance determinations from many individual systems, constrains the distribution of sources in the different Galactic components. Thus eLISA will probe dynamical effects in the Galactic center, which may increase the number of tight binaries [35]; it will measure the poorly known scale height of the disk; and it will sample the population of the halo [36,15], which hosts two anomalous AM CVn systems and which may have a rather different compact-binary population than the rest of the Galaxy. Furthermore, the eLISA measurements of orbital inclinations for individual binaries, compared with the overall angular momentum of the Galaxy, will provide hints on the formation of binaries from interstellar clouds.

eLISA will also constrain the formation rate and numbers of NS binaries and ultra-compact stellar-mass BH binaries, throughout the Galaxy and without EM selection effects. These numbers are highly uncertain, but as many as several tens of systems may be detectable by eLISA [33,37], complementing the ground-based GW observations of these same systems in other galaxies (and at much shorter periods).

More generally, the astrophysical populations and parameters probed by eLISA will be different from, and complementary to, what can be deduced from EM observations. For instance, eLISA will be sensitive to binaries at the Galactic center and throughout the Galaxy, while GAIA [38] will be limited to the Solar neighborhood; GWs encode distances and orbital inclinations, while EM emission is sensitive to surface processes. Dedicated observing programs and public data releases will allow simultaneous and follow-up EM observations of binaries identified by eLISA.

Massive black-hole binaries

(See [START_REF] Amaro-Seoane | [END_REF] for a much deeper review.) According to the accretion paradigm [39,40,[START_REF] Krolik | Active galactic nuclei: from the central black hole to the galactic environment[END_REF], supermassive BHs of 10 6 -10 9 M power quasars-active galactic nuclei so luminous that they often outshine their galaxy host, which are detected over the entire cosmic time accessible to our telescopes. Quiet supermassive BHs are ubiquitous in our lowredshift Universe, where they are observed to have masses closely correlated with key properties of their galactic host (see [START_REF] Gültekin | [END_REF], and refs. therein) leading to the notion that galaxies and their nuclear MBHs form and evolve in symbiosis (see, e.g., [43,44,45]).

In the currently favored cosmological paradigm, regions of higher-density cold dark matter in the early Universe form self-gravitating halos, which grow through mergers with other halos and accretion of surrounding matter; baryons and MBHs are thought to follow a similar bottom-up hierarchical clustering process [46,47,48,49,50]. MBHs may be born as small seeds (10 2 -10 3 M ) from the core collapse of the first generation of "Pop III" stars formed from gas clouds in light halos at z ∼ 15-20 [51,50]; or as large seeds (10 3 -10 5 M ) from the collapse of very massive quasi-stars formed in much heavier halos at z ∼ 10-15 [52,53]; or by runaway collisions in star clusters [54]; or again by direct gas collapse in mergers [55] (See [56,57] and refs. therein). The seeds then evolve over cosmic time through intermittent, copious accretion and through mergers with other MBHs after the merger of their galaxies.

The cosmic X-ray background from active MBHs at z < 3 suggests that radiatively efficient accretion played a large part in building up MBH mass [58,59,60], so information about the initial mass distribution is not readily accessible in the local Universe. By contrast, eLISA will measure the masses of the original seeds from their merger events. Furthermore, it is unknown [61] whether accretion proceeds coherently from a geometrically thin, corotating disk [62] (which can spin MBHs up to the J/M 2 = 0.93-0.99 limit imposed by basic physics [63,64]) or chaotically from randomly oriented episodes [65] (which typically result in smaller spins). eLISA's accurate measurements of MBH spins will provide evidence for either mechanism [66].

After a galactic merger, the central MBHs spiral inward, together with their bulge or disc, under the action of dynamical friction, and pair as a pc-scale Keplerian binary [67,68,69,70,71]; MBH binaries are then thought to harden into gravitationalradiation-dominated systems by ejecting nearby stars (assuming a sufficient supply) [72,73,74] or by gas torques and flows in gas-rich environments [75,76,77]; the final binary coalescence is the most luminous event in the Universe (albeit in GWs). BH mergers have been explored only recently by numerical relativity [78], showing how the mass and spin of the final BH remnant arise from those of the binary components, and predicting remarkable physical phenomena such as large remnant recoils for peculiar spin configurations [79]. The predicted coalescence rate in the eLISA frequency band ranges from a handful up to few hundred events per year, depending on theoretical assumptions ( [80,81,82,83,84,85,86,87]).

eLISA will be sensitive to GW signals from all three phases of MBH coalescence (inspiral, merger, and ring-down [88]). To assess the eLISA science performance in this area, after experimenting with different waveform families, we modeled these signals with the "PhenomC" phenomenological waveforms [89], which stitch together post-Newtonian (PN) inspiral waves [90] with frequency-domain fits to numerically modeled late-inspiral and ringdown waves. (PhenomC waveforms were derived for binaries with aligned spins; we adapt them to the non-aligned case by projecting the orbital angular momentum and individual spins onto the angular momentum of the distorted BH after merger.)

The first metric of performance is the detection SNR, angle-averaged over sky position and source orientation, which is plotted in Fig. 3 as a function of total rest mass and cosmological redshift (left panel) and as a function of total rest mass and mass ratio for binaries at z = 4 (right panel). eLISA covers almost all the mass-redshift parameter space of MBH astrophysics: any equal-mass binary with M tot = 10 4 -10 7 M (the crucial "middleweight" range inaccessible to EM observations beyond the local Universe) can be detected (with SNR > 10) out to the highest To evaluate expected SNRs in the context of realistic MBH populations, we consider four fiducial scenarios (SE, LE, SC, LC) where MBHs originally form from Small (∼ 100 M ) or Large seeds (∼ 10 5 M ), and where they subsequently grow by Extended or Chaotic accretion. (See [91] for details; here we enhance that analysis by including random spin-orbit misalignments up to 20 deg in E models [92]). For each scenario we generate multiple catalogs of merger events, and join them in equal proportions into a single metacatalog. Figure 4 shows the resulting distribution of SNR with z: eLISA will detect sources with SNR 10 out to z 10, a limit imposed by masses of the expected binary population as a function of z.

For the same metacatalog, Fig. 5 shows the expected accuracy of parameter determination, estimated using a Fisher-matrix approach based on PN inspiral [93].) The errors in D L have a wider spread, from a few percent to virtual non-determination, while sky position Ω is typically determined to 10-1000 deg 2 . Compared to previous published estimates for LISA, the accuracy in determining both D L and Ω is reduced for eLISA by having interferometric measurements only along two arms (although three arms were always a goal, not a requirement, for LISA). The next order of analysis is to combine multiple MBH-coalescence observations, resulting in a catalog of binary/remnant parameters, into a single inference about the mechanisms of MBH formation and evolution throughout cosmic history. This problem was analyzed extensively by Sesana and colleagues [94] in the context of LISA. We repeated their analysis for eLISA, by generating 1,000 catalogs of detected mergers (over two years) for each of the four SE/LE/SC/LC scenarios, and comparing the relative likelihood p(A vs. B) = p(A|C)/[p(A|C) + p(B|C)] for each pair of scenarios (A, B), for C = A or B. We considered only detections with SNR > 8, and used spinless, restricted PN waveforms. Table 1 shows our results for a relative likelihood threshold 0.95: for instance, the first row on the left shows that if SE is true, it could be discriminated from LE and LC in 99% of realizations, but from SC only in 48% of realizations; the last row on the left shows that LC could not be ruled out in 2% of realizations when SE or SC are true, but in 22% of realizations when LE is true. This degeneracy between accretion mechanisms is an artifact of the spin-less assumption; including information about the spin of the final merged MBH (which can be measured in 30% of detections) provides essentially perfect discrimination.

Last, because no theoretical model will exactly capture the "true" formation and evolution history of MBHs, we investigated eLISA's ability of measuring the mixing fraction 0 < F < 1 in a mixture model FA + (1 -F)B that produces coalescence events with probability F from scenario A, and 1 -F from B. For instance, for the case F SE + (1 -F)LE with F = 0.45, F can be measured with an uncertainty of 0.1 (see right panel of Fig. 4). Although highly idealized, this example shows the potential of eLISA's observations to constrain MBH astrophysics along their entire In closing this section, we note that eLISA may also detect coalescences of BHs with masses of 10 2 -10 4 M (intermediate-mass BHs, or IMBHs). These events do not result from hierarchical galaxy mergers, but they occur locally under the extreme conditions of star clusters. IMBHs may form in young clusters by way of mass segregation followed by runaway mergers [95,96,97,98,99]; IMBH binaries may form in situ [100], or after the collision of two clusters [101,102]. Although the evidence for IMBHs is tentative [103, 104], eLISA may observe as many as a few coalescences per year [101] out to a few Gpc [89]; it may also detect stellar-mass BHs plunging into IMBHs in the local Universe [105].

Extreme-mass-ratio inspirals and the astrophysics of dense stellar systems

There is of course one galactic nucleus, our own, that can be studied and imaged in great detail [106,107,108,109,110,111]. The central few parsecs of the Milky Way host a dense, luminous star cluster centered around the extremely compact radio source SgrA * . The increase in stellar velocities toward SgrA * indicates the presence of a (4 ± 0.4) × 10 6 M central dark mass [111], while the highly eccentric, low-periapsis orbit of young star S2 requires a central-mass density > 10 13 M pc -3 [112]; a density > 10 13 M pc -3 is also inferred from the compactness of the radio source [113]. These limits provide compelling evidence that the dark point-mass at SgrA * is an MBH [112,114,115].

Unfortunately, the nearest external galaxy is 100 times farther from Earth than SgrA * , and the nearest quasar is 100,000 times farther, so imaging other galactic centers is prohibitive. It will however become possible with eLISA. This is because MBHs are surrounded by a variety of stellar populations, including compact stellar remnants (stellar BHs, NSs, and WDs) that can reach very relativistic orbits around the MBH without being tidally disrupted [116]. The compact stars may plunge directly into the event horizon of the MBH; or they may spiral in gradually while emitting GWs. These latter systems, known as extreme-mass ratio inspirals (EMRIs), will produce signals by eLISA for MBH masses of 10 4 -10 7 M . Stellar-mass BHs should be concentrated in cusps near MBHs [117,118,98,119,120] and generate stronger GWs thanks to their relatively larger mass, so they will provide most detections.

EMRIs are produced when compact stars in the inner 0.01 pc of galactic nuclei are repeatedly scattered by other stars into highly eccentric orbits where gravitational radiation takes over their evolution [116]; resonant relaxation caused by long-term torques between orbits increases the rate of orbit diffusion [121,122], although relativistic precession can hinder this mechanism [123]. EMRIs can also be made from the tidal disruption of binaries that pass close to the MBH [124], possibly ejecting the hypervelocity stars observed in our Galaxy (see, e.g., [125]); and from massive-star formation and rapid evolution in the MBH's accretion disk [126]. Different mechanisms will lead to different EMRI eccentricities and inclinations, evident in the GW signal [124].

The detection of even a few EMRIs will provide a completely new probe of dense stellar systems, characterizing the mechanisms that shape stellar dynamics in the galactic nuclei, and recovering information about the MBH, the compact object, and the EMRI orbit with unprecedented precision [116]. Especially coveted prizes will be accurate masses for 10 5 -10 7 M MBHs in small, non-active galaxies, which will shed light on galaxy-MBH correlations at the low-mass end; MBH spins, which will illuminate the mechanism of MBH growth by mergers and accretion (see Sec. 4); as well as stellar-BH masses, which will provide insight on stellar formation in the extreme conditions of dense galactic nuclei. The key to measurement precision is the fact that the compact object behaves as a test particle in the background MBH geometry over hundreds of thousands of relativistic orbits in a year; the resulting GW radiation encodes the details of both the geometry and the orbit [127,128,129,130].

To assess the eLISA science performance on EMRIs, we model their very complicated signals [131] using the Barack-Cutler (BC) phenomenological waveforms [132], which are not sufficiently accurate for detection, but capture the character and complexity of EMRI waveforms. We complement this analysis with more realistic Teukolsky-based (TB) waveforms obtained by solving the perturbative equations for the BH geometry in the presence of the inspiraling body [133]; these have been tabulated for circular-equatorial orbits and for some values of MBH spin [130,134].

To evaluate expected EMRI detection horizons and detection rates, we perform a Monte Carlo over 500,000 realizations of the source parameters, taking MBH rest mass in [10 4 , 5 × 10 6 ] M with a uniform log M • distribution; MBH spin uniformly in [0, 0.95]; compact-body mass of 10 M , representative of a stellar-mass BH; orbit eccentricity before the final plunge uniformly in [0.05, 0.4]; and all orbital angles and phases with the appropriate uniform distributions on the circle or sphere, with an equal number of prograde and retrograde orbits. We take the poorly known EMRI formation rate to scale with MBH mass as 400 Gyr -1 (M • /3 × 10 6 M ) -0.19 [135, 136,137], and we distribute systems uniformly in comoving volume. Our assumptions are consistent with the MBH mass function derived from the observed galaxy luminosity function using the M • -σ relation, and excluding Sc-Sd galaxies [138,139,134].

We further assume an observation time of two years, consider EMRIs in the last five years of their orbit [134], and require a detection SNR = 20 [140,141,142]. The left panel of Fig. 6 shows the resulting maximum horizon redshift for BC waveforms, as a function of MBH rest mass-that is, it shows the z at which an optimally oriented source with the most favorable MBH and orbit parameters (as found in the Monte Carlo) achieves the detection SNR. Thus, EMRIs in the eLISA range will be detectable as far z = 0.7. By contrast, EM observations of 10 4 -10 6 M MBHs are possible in the local Universe out to z 0.1. The right panel plots the distribution of SNRs as a function of z, which shows that nearby EMRIs in the local Universe will yield SNRs of many tens.

For comparison, the left panel of Fig. 6 shows also the horizons computed with sky-and orientation-averaged SNRs, using TB waveforms from circular-equatorial orbits with MBH spins a • /M • = 0 and 0.9. The difference between the BC and TB curves is consistent with the effects of sky-averaging: SNRs for optimally oriented systems are expected to be 2.5 times higher than averaged SNRs. The a • /M • = 0.9 systems are favored because high MBH spin allows for orbits closer to the event horizon and higher GW frequencies, which shifts the peak eLISA sensitivity to higher masses.

The resulting number of expected eLISA detections over two years is ∼ 50, as evaluated with the BC-waveform Monte Carlo, and ∼ 30/35/55 (for a • /M • = 0/0.5/0.9), as evaluated with TB-waveform sky-averaged horizons. The higher TB event rate is explained by the inclusion of eccentric systems, which radiate more energy in the eLISA band, and it should be more reliable because of the broad sampling of source parameters. Remember however that EMRI rates are highly uncertain [116,135,136,123]. Even with as few as 10 events, the slope of the MBH mass function in the 10 4 -10 6 M range can be determined to 0.3, the current level of observational uncertainty [143].

Because EMRI waveforms are such complex and sensitive functions of the source parameters, these will be estimated accurately whenever an EMRI is detected [140,141,142]. In particular, we expect to measure the MBH mass and spin, as well as the compact-body mass and eccentricity to better than a part in 10 3 [132]. As an example, Fig. 7 shows the posterior distributions of the best-determined parameters for a z = 0.55 source detected by eLISA with SNR = 25, as computed with the Markov Chain Monte Carlo algorithm of [144]; for this source, the luminosity distance D L would be determined to 1%, and the sky location to 0.2 deg 2 . Even with relatively low SNR, parameter-estimation accuracy is excellent. In general, we find that the eLISA and LISA parameter-estimation performance is very similar for EMRIs detected with the same SNR (but of course different distances), so the reader can refer to treatments for LISA in the literature [132,145,146,142].

-2×10 -6 2×10 -6 6×10 -6 0 -1×10 -5 -5×10 -6 5×10 -6 1×10 -5 0 -6×10 -6 -3×10 -6 3×10 -6 6×10 -6 0 -2×10 -5 -1×10 -5 1×10 -5 2×10 -5 0 (M • est -M • true )/M • true (a • /M • ) est -(a • /M • ) true

Precision measurements of strong gravity

Einstein's theory of gravity, general relativity (GR), has been tested rigorously in the Solar system and in binary pulsars [147,148]; these tests, however, probe only the weak-field regime where the characteristic perturbative parameter = v 2 /c 2 ∼ GM/(Rc 2 ) is very small, ∼ 10 -6 -10 -8 (here v is the velocity of gravitating bodies, M their mass, and R their separation). By contrast, eLISA's GW observations of coalescing MBHs (Sec. 4) and of EMRIs (Sec. 5) will allow us to confront GR with precision measurements of its dynamical, strong-field regime, and to verify that astrophysical BHs are really the Kerr mathematical solutions predicted by GR. Before considering the GR tests possible with each of these sources, we note that, by the second half of this decade, second-generation ground-based detectors are expected to routinely observe the coalescences of stellar-mass BHs and (possibly) of asymmetric systems such as a NS inspiraling into a 100 M BH. However, they will do so with 10-100 times lower SNRs than eLISA (for the brightest sources), and for up to 1,000 times fewer GW cycles; thus, eLISA will test our understanding of gravity in the most extreme conditions with a precision that is two orders of magnitude better than that achievable from the ground. (Although most of the references cited in the rest of this section were developed for LISA, their broad conclusions are applicable to sources detected with comparable SNRs by eLISA.)

All three phases of MBH coalescence offer opportunities for precision measurements. The year-long inspiral signals can be examined for evidence of a massive graviton, resulting in a frequency-dependent phase shift of the waveform, improving current Solar-system bounds [149,150]; they can yield stringent constraints on other theories with deviations from GR parametrized by a set of global parameters, such as massless and massive Brans-Dicke theories [151,152], theories with an evolving gravitational constant [153], Lorentz-violating modifications of GR [154]; last, various authors have considered testing inspiral waves for hypothetical, generic modifications of their amplitude and phasing [155,156,157,158].

The merger of comparable-mass MBH binaries produces an enormously powerful GW burst, which eLISA will measure with SNR as high as a few hundred, even at cosmological distances. The MBH masses and spin can be determined with high accuracy from the inspiral waveform; given these physical parameters, numerical relativity can predict the shape of the merger waveform, as well as the mass and spin of the final remnant MBH [159], and these can be compared directly with observations, providing an ideal test of pure GR in a highly dynamical, strong-field regime.

The frequencies and damping times of the quasinormal modes (QNMs) in the final ringdown [160] are completely determined by the mass and the spin of the remnant, and therefore can be used to measure them [161,162], while their relative amplitudes hold information about the pre-merger binary [163], again providing a check of consistency between GR predictions for the phases of coalescence. Furthermore, the measurement of at least two QNMs [162] will test the Kerr-ness of the MBH [164] against exotic proposals such as boson stars and gravastars [165,166,167,168]. Modifications of GR that lead to different emission would also be apparent [169,170].

EMRIs are expected to be very clean astrophysical systems, except perhaps in few systems with strong interactions with the accretion disk [171,172,173], or with perturbations due to a second nearby MBH or star [174,175]. Over day-long timescales, EMRI orbits are essentially geodesics of the background geometry; on longer timescales, the loss of energy and angular momentum to GWs causes a slow change of the geodesic parameters. In the last few years of their evolution, as observed by eLISA, EMRI orbits are highly relativistic (R < 10 R • ) and display extreme forms of periastron and orbital plane precession. Indeed, EMRI GWs encode all the mass and current multipoles of the MBH [127,176], which for a Kerr BH are uniquely determined by the mass and spin alone (another manifestation of the "no-hair" theorem). For EMRIs with SNR = 30, eLISA will measure mass and spin to a part in 10 3 -10 4 , and the mass quadrupole moment M 2 to a part in 10 2 -10 4 , thus testing the no-hair theorem directly [129]. See [177,178] for reviews of different ways to test the nature of astrophysical BHs.

Other tests of the Kerr-ness of the central massive object have been proposed: for a boson star, the EMRI signal would not shut off after the last stable orbit [179]; for a gravastar, QNMs could be excited resonantly [168]; for certain non-Kerr axisymmetric geometries, orbits could become ergodic or experience resonances [180, 181]; for "bumpy" BHs, orbits would again carry distinctive signatures [127,182,183,184]. Modifications in EMRI GWs would also arise if the true theory of gravity is in fact different from GR, as are dynamical Chern-Simons theory [185,186], scalar-tensor theories (with observable effects in NS-BH systems where the NS carries scalar charge [151,187]), Randall-Sundrum-inspired braneworld models [188, 189], theories with axions that give rise to "floating orbits" [190,191], as well as generic, phenomenologically parametrized theories [192].

Cosmology and new physics from the early Universe

GWs produced after the Big Bang form a fossil radiation: expansion prevents them from reaching thermal equilibrium with the other components because of the weakness of the gravitational interaction. Thus, relic GWs carry information about the first instants of the Universe. If their wavelength is set by the apparent horizon size c/H * = c(a/ ȧ) * at the time of production, when the temperature of the Universe [193].) Spectra of stochastic backgrounds from cosmic strings for large loops (0.1 the horizon size, solid lines), for two values of the string tension Gµ/c 4 spanning a range of scenarios motivated by braneworld inflation; and for small loops (with size α = 50 Gµ, dashed line). The cosmic-string spectrum is distinguishably different from that of first-order phase transitions or any other predicted source: it has nearly constant energy per logarithmic frequency interval over many decades at high frequencies, and falls off after a peak at low frequencies, since large string loops are rare and radiate slowly. Cosmic strings may also produce distinctive bursts, produced by a sharply bent bits of string moving at nearly the speed of light [212,213,214,215].

is T * , the redshifted frequency is

f ≈ 10 -4 Hz H * × 1 mm c ≈ 10 -4 Hz k B T * 1 TeV , (3)
so the eLISA frequency band corresponds to the horizon at and beyond the Terascale frontier of fundamental physics. This allows eLISA to probe bulk motions at times about 3 × 10 -18 -3 × 10 -10 s after the Big Bang, a period not directly accessible with any other technique. Taking a typical broad spectrum into account, eLISA has the sensitivity to detect cosmological backgrounds caused by new physics at energies ∼ 0.1-1000 TeV, if more than a (modest) fraction ∼ 10 -5 of the energy density is converted to GWs at the time of production. Various sources of cosmological GW backgrounds are presented in detail in [193]. They include first-order phase transitions, resulting in bubble nucleation and growth, and subsequent bubble collisions and turbulence [194,195,196,197,198]; the dynamics of stabilization for the extra dimensions required by superstring theory [199,200], which may also appear as non-Newtonian gravity in laboratory experiments at the sub-mm scale; networks of cosmic (super-)strings [201,[START_REF] Vilenkin | Cosmic strings and other topological defects[END_REF], which continuously produce loops that decay into GWs (see Fig. 8); the transition between inflation and the hot Big Bang in the process of preheating [203,204,205,206,207]; and the amplification of quantum vacuum fluctuations in some unconventional versions of inflation [208,209,210]. Although the two-arm eLISA does not provide a Sagnac TDI combination [211] to calibrate instrument noise against possible GW backgrounds, the clear spectral dependence predicted for some of these phenomena provides an observational handle, as long as the background lies above the eLISA sensitivity curve.

As discussed in Sec. 4, observations of GWs from MBH binaries probe the assembly of cosmic structures. In addition, binaries can serve as standard sirens to measure cosmological parameters [216,217] because, as discussed around Eq. ( 2), measuring the amplitude and frequency evolution of a binary signal yields the absolute luminosity distance to the source. However, binary GWs cannot provide the source's redshift unless the other source parameters are known independently (because the rest mass of the binary is the only length/time scale in the waveform, the frequency evolution of a redshifted signal is indistinguishable from the signal from a heavier binary). The optical redshift of the host galaxy can be obtained if an EM counterpart to MBH coalescence is observed (see, e.g., [218,219,220], and [221] for a recent review).

While there are many uncertainties in the nature and strength of such counterparts, some may be observable in the local Universe. At z < 1, we expect that eLISA MBH-inspiral measurements could provide sky locations to better than 400 deg 2 for 50% of sources, and to 10 deg 2 for 11%. (The inclusion of merger and ringdown in the analysis should further improve these numbers.) Such large areas will be covered frequently and deeply by optical and radio surveys such as LSST [222] and the VAST project [223], identifying sufficiently distinctive transients. The accurate knowledge of the counterpart's redshift and position would then improve the uncertainty of GW-determined parameters, with D L known to 1% for 60% of sources, and 5% for 87%. Such precise luminosity distance-redshift measurements will be complementary to other cosmographical campaigns [224,225], and will improve the estimation of cosmological parameters. Even without counterparts, one may proceed by considering all possible hosts in a distance-position error box, and enforcing consistency between multiple GW events [226]; this should be possible for MBH binaries (and EMRIs [227]) in the local Universe, yielding the Hubble constant to a few percent.

Conclusions

While LISA was always meant to be the definitive mission in its frequency band, eLISA is being designed to provide the maximum science within a cost cap. Nevertheless, as described above, eLISA will achieve a great part of the LISA science goals. It will represent the culmination of twenty years of exciting, painstaking work, pioneering the new science of observational low-frequency GW astronomy. It will truly begin to unveil the hidden, distant Universe. May it fly soon, and safe.

Figure 2 .

 2 Figure 2. Main figure: power spectral density of the stochastic GW foreground from Galactic binaries, before (blue) and after (red) the subtraction of individually resolvable systems, which are plotted as green and red/blue dots (for detached and mass-transferring systems). A few known verification binaries are shown as white dots.The solid/dashed black curves trace instrument noise alone/with confusion noise. Spectra are shown for the TDI observable "X" (see, e.g.,[13]); subtraction is simulated for a two-year observation and threshold SNR = 7; resolvable systems are placed a factor SNR 2 above the combined instrument and confusion noise. Inset: time series of the residual foreground, which carries information about the number and distribution of binaries in the Galaxy.

Figure 3 .Figure 4 .

 34 Figure 3. Left: constant-level contours of sky-and polarization-averaged SNR for equal-mass non-spinning binaries as a function of total rest mass Mtot and cosmological redshift z. The SNR includes inspiral, merger and ringdown. Right: SNR contours as a function of Mtot and mass ratio q = m 1 /m 2 .

Figure 6 .

 6 Figure 6. Left: maximum horizon redshift vs. MBH rest mass, BC waveforms (red curve); averaged horizon redshift vs. MBH rest mass, TB waveforms with a•/M• = 0 and 0.9. Assumptions are given in the main text; the maximum is computed as the highest z with SNR > 20 in a given mass bin. Right: maximum EMRI SNR vs. redshift, BC waveforms.

Figure 7 .

 7 Figure 7. Posterior probability plot for source parameters (MBH rest mass M•, MBH spin a•, compact-body mass m, and orbit eccentricity at plunge e), in the SNR = 25 detection of a 10 + 10 6 M EMRI at z = 0.55, with a•/M• = 0.7 and e plunge = 0.25.

Figure 8 .

 8 Figure 8. (From[193].) Spectra of stochastic backgrounds from cosmic strings for large loops (0.1 the horizon size, solid lines), for two values of the string tension Gµ/c 4 spanning a range of scenarios motivated by braneworld inflation; and for small loops (with size α = 50 Gµ, dashed line). The cosmic-string spectrum is distinguishably different from that of first-order phase transitions or any other predicted source: it has nearly constant energy per logarithmic frequency interval over many decades at high frequencies, and falls off after a peak at low frequencies, since large string loops are rare and radiate slowly. Cosmic strings may also produce distinctive bursts, produced by a sharply bent bits of string moving at nearly the speed of light[212,213,214, 215].

  Figure 5. Parameter-estimation accuracy (relative frequency of fractional or absolute errors over SE/LE/SC/LC metacatalog) for primary and secondary redshifted MBH masses and dimensionless spins (m 1 and m 2 , a 1 /m 1 and a 2 /m 2 , respectively), luminosity distance D L and sky position ∆Ω. waveforms with spin-induced precession, augmented with PhenomC merger-ringdown waveforms. eLISA can determine the redshifted component masses (m redshift = (1+z) m rest ) to 0.1-1 %; the primary-MBH spins to 0.01-0.1; and the secondary-MBH spins to 0.1 in a fraction of systems. (Compare with EM MBH-mass uncertainties ∼ 15-200%, except for the Milky Way MBH, and with very large MBH-spin uncertainties from Kα iron line fits

	p.d.f.
	log 10 (δm 1 /m 1 )	log 10 (δm 2 /m 2 )	log 10 (δD L /D L )
	p.d.f.
	log 10 δ(a 1 /m 1 )	log 10 δ(a 2 /m 2 )	log 10 (ΔΩ/deg 2 )

Table 1 .

 1 Model discrimination with eLISA MBH-binary observations. The upper-right half of each table shows the fraction of realizations in which the row model would be chosen over the column model with a likelihood threshold > 0.95, when the row model is true. The lower-left half of each table shows the fraction of realizations in which the row model cannot be ruled out against the column model when the column model is true. In the left table we consider only the measured masses and redshift for observed events; in the right table we include also the observed distribution of remnant spins.

			without spins				with spins
		SE	SC	LE	LC		SE	SC	LE	LC
	SE	×	0.48 0.99 0.99	SE	×	0.96 0.99 0.99
	SC 0.53	×	1.00 1.00	SC 0.13	×	1.00 1.00
	LE 0.01 0.01	×	0.79	LE 0.01 0.01	×	0.97
	LC 0.02 0.02 0.22	×	LC 0.02 0.02 0.06	×

cosmic history, in mass and redshift ranges inaccessible to EM astronomy.

Acknowledgments

This research was supported by the Deutsches Zentrum für Lüft-und Raumfahrt and by the Transregio 7 "Gravitational Wave Astronomy" financed by the Deutsche Forschungsgemeinschaft DFG (German Research Foundation). EB was supported by NSF Grant PHY-0900735 and by NSF CAREER Grant PHY-1055103. AK was supported by the Swiss National Science Foundation. TBL was supported by NASA Grant 08-ATFP08-0126. RNL was supported by an appointment to the NASA Postdoctoral Program at the Goddard Space Flight Center, administered by Oak Ridge Associated Universities through a contract with NASA. MV performed this work at the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. Copyright 2012.