Qi Wang
email: wangqi08@ict.ac.cn

Katia Jaffrès-Runser

Yongjun Xu

Jean-Luc Scharbarg
email: jean-luc.scharbarg@enseeiht.fr

Zhulin An
email: anzhulin@ict.ac.cn

Christian Fraboul
email: christian.fraboul@enseeiht.fr

TDMA versus CSMA/CA for wireless multi-hop communications: a comparison for soft real-time networking

Keywords: Probabilistic worst-case end-to-end delay, TDMA, CSMA/CA, IEEE802.11 DCF, Wireless multi-hop networks

Wireless networks have become a very attractive solution for soft real-time data transport in the industry. For such technologies to carry real-time traffic, reliable bounds on end-toend communication delays have to be ascertained to warrant a proper system behavior. As for legacy wired embedded and real-time networks, two main wireless multiple access methods can be leveraged: (i) time division multiple access (TDMA), which follows a time-triggered paradigm and (ii) Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), which follows an event-triggered paradigm. This paper proposes an analytical comparison of the time behavior of two representative TDMA and CSMA/CA protocols in terms of worst-case end-toend delay. This worst-case delay is expressed in a probabilistic manner because our analytical framework captures the versatility of the wireless medium. Analytical delay bounds are obtained from delay distributions, which are compared to fine-grained simulation results. Exhibited study cases show that TDMA can offer smaller or larger worst-case bounds than CSMA/CA depending on its settings.

I. INTRODUCTION

Wireless multi-hop networks (i.e., ad hoc, sensor, mesh networks) are currently being intensively investigated for realtime applications because of their appealing ease of deployment and scalability [START_REF] Zhuo | iqueue-mac: A traffic adaptive duty-cycled mac protocol with dynamic slot allocation[END_REF], [START_REF] Petersen | Wirelesshart versus isa100.11a: The format war hits the factory floor[END_REF]. Many industrial applications require delay guarantees in their networks: packets of critical flows must arrive at their destination within a fixed delay bound. Guaranteeing hard real-time communications in wireless networks is difficult due to the unreliability of the wireless channel. However, it is possible to guarantee soft real-time requirements with a dedicated protocol stack design. Such networks can tolerate a really small probability for the endto-end delay of flows to exceed a fixed time limit. In these networks, it is thus possible to derive a probabilistic worstcase delay bound D w with a given confidence level.

As for legacy wired embedded and real-time networks, two main types of multiple access methods can be leveraged: (i) time division multiple access (TDMA), which follows a timetriggered paradigm and (ii) Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), which follows an event-triggered paradigm. So far, wireless real-time networking solutions rely on a mesh topology where TDMA is exploited for its high determinism [START_REF] Petersen | Wirelesshart versus isa100.11a: The format war hits the factory floor[END_REF]. CSMA/CA is the solution chosen for mainstream non time-sensitive wireless networking for its scalability and elastic bandwidth management capability.

Several studies [START_REF] Zhuo | iqueue-mac: A traffic adaptive duty-cycled mac protocol with dynamic slot allocation[END_REF] have looked into the benefits of CSMA/CA solutions for soft real-time networking and compared their performance to TDMA solutions. Most of these works have evaluated both approaches using simulations and experiments. We propose in this paper to look at the problem from a theoretical point of view. There is still a need for a comprehensive analytical framework capable of calculating the worst-case delay bounds of flows carried on a given wireless network. The problem is not easy since wireless communications have to be modeled with a link transmission probability. Modeling the multi-hop, multi-flow interactions requires advanced performance evaluation models (e.g. Markov chain, Z-transforms, etc. ) whose assumptions are not always realistic.

This paper introduces a new method to calculate the delay distribution of a basic TDMA protocol. It relies on an analytical framework that we have previously defined to capture the performance (in average) of multi-hop multi-flow wireless networks [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF]. From this delay distribution calculation, we can derive the probabilistic worst-case delay bound of TDMA for any topology and flow pattern. This delay distribution and worst-case bound are validated against extensive simulations. Next, we leverage this new TDMA bound calculation to compare the performance of TDMA to the one of CSMA/CA on two elementary network topologies. Therefore, the analytical model of [START_REF] Wang | A thorough analysis of the performance of delay distribution models for IEEE 802.11 DCF[END_REF] we had validated for CSMA/CA is applied to the selected topologies. Several TDMA configurations are tested. As expected, TDMA can be made more or less efficient than CSMA/CA depending on its settings. Interesting to notice is that our model clearly captures the longer tail of the delay distribution of CSMA/CA compared to TDMA. This paper is organized as follows. Section II introduces network models and protocols related to both multiple access schemes. Section III pictures the main elements of the analytical models proposed herein for the end-to-end delay distribution computations of TDMA and CSMA/CA. Section IV validates our analytical models against simulation. Following, it compares the performance of TDMA and CSMA/CA on two topologies. Finally, Section V concludes the paper.

II. SYSTEM MODEL AND PROTOCOLS

A. Multi-hop topologies

In this paper, we investigate two different atomic topologies to highlight different problems that may occur in a wireless multi-hop mesh communication. The first one is a basic multihop linear topology, where all packet are forwarded from one source node S to a destination node D using relay nodes. In our case, we choose a topology where three nodes relay the frames from S to D (cf. Fig. 1(a)). The more relays are exploited, the higher the odds for the transmission to fail. Typically, end-to-end communications exceeding four to five hops get difficult to implement in practice. The second topology investigated is the 2-relay/2-flow topology of Fig. 1(b). Here, the two relays have to forward packets that belong to two flows, simultaneously. The first flow is emitted by S 1 going to D 1 and the second flow is emitted by S 2 , going to D 2 . This situation is critical since the relays have to listen to both flows and to re-emit them concurrently.

Source nodes generate strictly periodic flows of frames. As we will explain later in the section IV, we set the frame generation period such as there is only one frame in the emission buffer of the source at all times. Thus, the only delay we are computing analytically or measuring by simulation is the MAC delay, i.e. the time for the frame to gain access to the channel. There is no delay related to queuing in this work.

B. CSMA/CA network model and protocol

We assume that all nodes of the network follow the stateof-the-art IEEE802.11 DCF MAC protocol. We refer the reader to the standard for a detailed description of the protocol.

C. TDMA network model and protocol

A perfectly synchronized TDMA is considered. A superframe of |T | time slots is repeated indefinitely. For the 2relay/2-flow scenario, |T | = 4. The source S 1 emits its frames in time slot 1, S 2 in slot 2, relay R 1 in slot 3 and R 2 in slot 4. Similarly, for the 3-relay scenario, |T | = 4 with the source emitting in time slot 1, and relays R i in time slot number i+1.

In our TDMA network model [START_REF] Wang | Deriving pareto-optimal performance bounds for 1 and 2-relay wireless networks[END_REF], each relay node is characterized by a set of forwarding probabilities x uv ij that govern its forwarding decisions. Assume node j receives a packet from node i in the current superframe s on time slot u. TDMA scheduling algorithm describing the forwarding and emission decisions taken by any relay node j is that it will decide with probability x uv ij to emit this packet in time slot v of next superframe s + 1. Node j only re-emits once as

v x uv ij = 1.
For the two investigated topologies, the Paretooptimal forwarding probabilities are derived using a multiobjective optimization problem formulation where capacityachieving delay and energy are minimized concurrently. The capacity-achieving metrics are calculated such as to achieve perfect transmission (i.e. all packets arrive at their destination).

III. ANALYTICAL DELAY DISTRIBUTION AND WORST-CASE DELAY MODELS

This section introduces the analytical models to derive the delay distributions of both CSMA/CA and TDMA protocols. The probabilistic worst-case end-to-end delay is derived from the delay distribution as defined next.

A. Worst-case delay definition

The delay distribution for a flow ending at destination D j is given by the probability mass function (PMF) and denoted by the probability P [d j = k], with k ∈ R + being positive end-to-end delay values. PMF can be computed for each flow.

The probabilistic worst-case delay for the flow ending at destination D j is defined as the delay D w for which the probability P [d j ≥ D w ] to find a delay larger than D w is arbitrarily small (for instance smaller than δ = 10 -9 ). Formally, for a flow ending at D j :

max D w s.t. P [d j ≥ D w ] ≤ δ (1)
Next, we concentrate on the PMF derivation for both CSMA/CA and TDMA schemes.

B. Delay distribution for CSMA/CA

To be able to apply the Markov model of [START_REF] Bianchi | Performance analysis of the ieee 802.11 distributed coordination function[END_REF], where source and relay nodes compete continuously for the channel (we are at network saturation), we have to add supplementary interfering nodes. For each single-hop communication, we assume there are a total of n = 5 nodes contending for channel access simultaneously, including the source of interest. To compute the PMF of end-to-end delay in a multi-hop communication, we calculate first the Probability Generating Function (PGF) of the MAC delay for a one-hop communication. We assume that the delay experienced over one hop is independent of the delay of the other hops. This assumption is reasonable as we are in the saturated scenario, where all emitting nodes constantly contend for the medium. Knowing that the PGF of the sum of independent random variables is equal to the product of the PGF of each variable, the analytical PGF of the multi-hop total delay D multihop (Z), Z ∈ C can be easily derived as the product of the PGFs of MAC delays calculated for each hop, where C is the set of complex numbers.

D multihop (Z) = D m1st (Z) * D m 2nd (Z) * ... * D mtst (Z)
(2) with D mtst (Z) the PGF of the t-est hop MAC delay. To retrieve the PMF, the numerical Lattice-Poisson inversion method of [START_REF] Vu | Accurate delay distribution for IEEE 802.11 DCF[END_REF] is applied with accuracy 10 -8 .

C. Delay distribution for our TDMA protocol

In our model, the delay is measured in hops. A packet may experience several paths, each one of different length in number of hops. It takes one superframe duration for the packet to travel one hop further. So all metrics of delay are expressed in hops, and can be easily converted in time units by multiplying them by |T | × τ p , with τ p the slot duration. D j in time slot v at time epoch (s + 1). The relaying matrix Q is structured as follows:

Q =     0 Q 12 • • • Q 1N Q 21 0 • • • Q 2N . . . . . . Q N 1 • • • Q N -1N 0     0 is a |T |-
Q ij =     Q 11 ij • • • Q 1|T | ij . . . . . . Q |T |1 ij • • • Q |T ||T | ij     (3)
where Q uv ij is the probability for a node j to retransmit on time slot v a packet that has been transmitted by node i on time slot u. From our network model, it equals to Q uv ij = p u ij x uv ij . The arrival matrix D is given by:

D =    D 1D1 • • • D 1D |D| . . . . . . D N D1 • • • D N D |D|    D iDj is a |T |-

2) Delay distribution:

We assume that one hop introduces a delay of one time unit. Consequently, a h-hop transmission introduces a delay of h units. The delay distribution P (d(D j ) = h) is the probability for a transmission towards D j to be done in h hops. After s time epochs, a packet can travel up to h = s+1 hops. Thus, the probability mass function (PMF) is given by, gives the total packet arrival rate obtained in D j : f (D j ) = ∀Si∈QS f (S i , D j ). The normalized rate provided by source S i , f (S i , D j ) : f (S i , D j ) = ∀p∈P P (p) • τ Si where P is the set of all possible paths from S i to D i , and P (p) is the probability for a packet emitted by S i to arrive in D i . This probability is directly obtained from Q and D matrices.

P (d(D j ) = h) = DS •ID(Dj ) f (Dj ) h = 1 QS •Q h-2 •D•ID(Dj ) f (Dj ) ∀h ≥ 2 I D (D j )

IV. RESULTS

This section validates the delay distribution models and compares D w for TDMA and CSMA/CA wireless multi-hop networks for the topologies of Fig. 1. Several settings related to TDMA slot duration and the chosen energy-delay trade-off configuration are investigated.

A. Simulation settings

Wireless topologies and protocols are simulated using the realistic discrete event-driven network simulator WSNet 1 . In all topologies, sources only generate frames and destinations only receive them. The sources emit a periodic flow of frames whose period is set differently according to the protocol in use. The end-to-end delay is the duration between arrival of the frame in the source buffer and the arrival of the frame in destination buffer. Frames have a constant size of 2560 bytes of payload and 24 bytes of PHY header (it is the standard maximum IEEE802.11 frame size). The data rate is 11Mbps. Simulations are performed for the duration necessary to complete the transmission of 100 000 frames.

1) TDMA settings: Results are given assuming an AWGN channel and a BPSK modulation without coding providing a bit error rate of BER(γ) = Q( √ 2γ) = 0.5 * erfc( √ γ), with γ the per bit signal to noise and interference ratio experienced on the link. In all topologies, only two nearby nodes communicate with each other (no other node is interfering), they experience a perfect link quality. Moreover, a perfect TDMA is considered, where all nodes are perfectly synchronized. The duration of each time slot is sufficient for emitting a complete frame. The time slot durations τ p values are considered here: (i) τ p = 2.1ms, the minimum slot duration for sending the maximum frame size of IEEE802.11 at 11 Mbps, ii) τ p = 10ms, the regular slot duration chosen by WirelessHART or ISA100.11a TDMA protocols. Note that both slot durations are long enough to carry a frame of 2584 bytes, whether using IEEE802.11 at 11Mbps or IEEE802.15.4 at 250kbps.

2) CSMA/CA settings: Presented results for the IEEE 802.11 DCF MAC delay are given with RTS/CTS mechanism. DSSS-PHY layer is assumed and main DCF timing as in [START_REF] Wang | A thorough analysis of the performance of delay distribution models for IEEE 802.11 DCF[END_REF]. By setting the source periodicity to the average end-to-end delay obtained by the Markov chain model, the simulation reaches the steady state assumed analytically. All nodes of the network have to be in the range of four nodes that are constantly competing for channel access.

B. Delay distribution and D w comparative analysis

The analytical delay distribution for TDMA and CSMA/CA protocols are verified by simulations. For the 2-relay TDMA networks, there is a single Pareto-optimal solution. As seen in Fig. 2, the analytical delay distribution for one source-destination pair compared with the simulation results for 2-relay TDMA network matches well for most of the delay values that appear the most frequently. The tail of the distribution is very difficult to validate with simulations since such delays are very rare events, with very small probabilities (y-axis of plot is in logscale). However, looking at the overall fit, and the RMSE of 1.7069 * 10 -3 for the computed values, we can conclude that the model seems to be accurate enough (for soft real-time guarantees). For the 3-relay TDMA networks, there are several Pareto solutions and we have picked three Pareto optimal solutions to show their delay distribution. Their distributions are plotted in Fig. 3(a), Fig. 3(b) and Fig. 3(c), respectively. The RMSE between analytical and simulated delay PMF is of 4.9428 * 10 -3 for the Pareto optimal solution with smallest delay. For largest and the one in between, RMSE is of 4.9523 * 10 -3 and of 1.0803 * 10 -2 , respectively. For the 2-relay and 3-relay CSMA/CA network, from the Fig. 2 and Fig. 3, the analytical and simulated delay distribution match well, even for the tail of delay distribution. The RMSE is of 4.7666 * 10 -2 for the 2-relay scenario and of 6.1348 * 10 -2 for the 3-relay scenario.

The worst case delay bound D w comparisons for TDMA and CSMA/CA networks has been derived for two time slot duration values. D w for the 2-relay and 3-relay scenarios are given for different values of δ in Table I. As shown in Fig. 2, we can see that D w of TDMA network is larger than the one of CSMA. This plot has been derived for a time slot duration of 10ms. For a time slot duration of 2.1ms, however, TDMA is faster than CSMA/CA. This fact highlights that the efficiency of TDMA can be largely improved by adjusting to a smaller period of course. But in practice, synchronization errors are overcome by oversizing the slots at the cost of overall performance. However, the tail for TDMA systems is shorter than the one of CSMA. Thus, TDMA systems exhibit a slower increase in D w if δ values drop.

V. CONCLUSION

This paper provides an overview of two models whose aim is to calculate the worst-case delay bounds D w for TDMA and CSMA/CA-based wireless multi-hop networks. Original to this work is the analytical delay distribution model for TDMA. The CSMA/CA analysis stems from previous works of ours. Both models are validated by simulations for two elementary topologies. After calculating the D w bounds for TDMA and CSMA/CA for both topologies, we have investigate the impact of the TDMA slot duration on D w . We can show that this choice clearly impacts the worst-case bound performance of TDMA, as expected. In future works, we will concentrate on adding synchronization overhead into our TDMA model. Moreover, for both TDMA and CSMA/CA, we plan to introduce a more precise analytical model to capture the physical layer of mainstream sensors.

Fig. 1 .

 1 Fig. 1. Investigated topologies.

1 ) 5 )Fig. 2 .

 152 Fig.2. Worst-case bounds (δ=10 -5 ) for 2-relay topology and a slot of 10ms.

  by-|T | diagonal matrix whose diagonal elements D u iDj give the probabilities for a packet transmitted by a node i in time slot u to arrive at destination D j and D u iDj = p u iDj . Q S and D S are the relaying and arrival matrices for the packets sent by the sources. They have the same structure as Q and D, where Q Sij follows the pattern given by (3) and D SiDj is a |T |-by-|T | diagonal matrix whose diagonal elements are D u SiDj = p u SiDj .

  is a selection vector of dimension |D||T | where the |T | elements relative to destination D j are equal to 1 and the others are equal to 0. I D (D j ) accumulates the packet arrival rate in each time slot at destination D j . f (D j )

5 )Fig. 3 .

 53 Fig. 3. The comparison of worst case delay bound (δ = 10 -5 ) for 3-relay TDMA and CSMA/CA networks -time slot duration of 10ms.

TABLE I

 I

		.	D W FOR ALL TOPOLOGIES (UNIT: MS)
	Scenario	δ	DW for TDMA (τp = 2.1ms)	DW for TDMA (τp = 10ms)	DW for CSMA/CA (IEEE802.11 DCF)
		10 -5	246	1170	536
	2-relay	10 -7	347	1650	1286
		10 -9	435	2070	1596
	3-relay (smallest E2E delay)	10 -5 10 -7 10 -9	152 185 219	720 880 1040	606 1586 1926

VI. ACKNOWLEDGMENTS

This work is supported by Important National Science and Technology Specific Projects (2014ZX03006-003) and Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute (BY2013095-4-21).


Sandra Bardot

Marcos Serrano

Bernard Oriola

Christophe Jouffrais

Identifying how Visually Impaired People Explore Raised-line Diagrams to Improve the Design of Touch Interfaces

come   L'archive ouverte pluridisciplinaire

Open Archive TOULOUSE Archive Ouverte (OATAO)

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible.

This is an author-deposited version published in : http://oatao.univ-toulouse.fr/ Eprints ID : 18988

The contribution was presented at CHI 2017 : https://chi2017.acm.org/ To link to this article URL : https://doi.org/10.1145/3025453.3025582 To cite this version : Bardot, Sandra and Serrano, Marcos and Oriola, Bernard and Jouffrais, Christophe Identifying how Visually Impaired People Explore Raised-line Diagrams to Improve the Design of Touch Interfaces. (2017) In: SIGCHI Conference on Human Factors in Computing Systems (CHI 2017), 6 May 2017 -11 May 2017 (Denver, United States). Any correspondence concerning this service should be sent to the repository administrator: staff-oatao@listes-diff.inp-toulouse.fr Common Drawings (C-Drawings) and Perspective Drawings (P-Drawings) Mathematical graphs (Graphs) Neighborhood maps (N-Maps) Geographical maps (G-Maps) free exploration driven exploration Touch robustness: Content Simplification: Multimodal Information Sharing: Interaction Menus: Scand.J.Psychol 39 Proceedings of the 18th International Conference on Human-Computer Interaction with Mobile Devices and Services CHI '12 Extended Abstracts on Human Factors in Computing Systems Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems Proceedings of the 14th international ACM SIGACCESS conference on Computers and accessibility Proceedings of the 2015 International Conference on Interactive Tabletops & Surfaces Perception Percept Psychophys Behavioural Brain Research 135 Proceedings of the 24th annual ACM symposium on User interface software and technology . Multisensory Research chapter in The Psychology of Learning and Motivation Psychological Research 76 Percept Psychophys Acta Psychol (Amst) 84 Proceedings of XXII International Cartographic Conference In Perception Proceedings of the SIGCHI Conference on Human Factors in Computing Systems Transactions on Haptics


Walter Finsinger
email: walter.finsinger@um2.fr

Thomas Giesecke

Simon Brewer

Michelle Leydet

Emergence patterns of novelty in European vegetation assemblages over the past 15 000 years

Keywords: Biological novelty, EPD, Europe, pollen, post-glacial

Plant communities are not stable over time and biological novelty is predicted to emerge due to climate change, the introduction of exotic species and land-use change. However, the rate at which this novelty may arise over longer time periods has so far received little attention. We reconstruct the emergence of novelty in Europe for a set of baseline conditions over the past 15 000 years to assess past rates of emergence and investigate underlying causes. The emergence of novelty is baseline specific and, during the early-Holocene, was mitigated by the rapid spread of plant taxa. Although novelty generally increases as a function of time, climate and human-induced landscape changes contributed to a non-linear post-glacial trajectory of novelty with jumps corresponding to periods of rapid changes. Emergence of novelty accelerated during the past 1000 years. Historical cultural landscapes experienced a faster novelty development due to the contribution from anthropogenic land-cover changes.

INTRODUCTION

The inevitable consequence of individualistic changes in species distributions [START_REF] Gleason | The individualistic concept of the plant association[END_REF]) is that modern associations will be reshuffled into substantially different associations with respect to historical and present baseline conditions [START_REF] Hobbs | Novel ecosystems: implications for conservation and restoration[END_REF][START_REF] Hobbs | Managing the whole landscape: historical, hybrid, and novel ecosystems[END_REF] through several mechanisms. Parts of the modern climate space may disappear and currently unavailable portions of the climate space may unfold, thereby potentially restricting suitable habitats for species lacking a pre-adaptation to abiotic novelty in climate conditions [START_REF] Williams | Novel climates, no-analog communities, and ecological surprises[END_REF][START_REF] Reu | Future no-analogue vegetation produced by no-analogue combinations of temperature and insolation: no-analogue vegetation, temperature and insolation[END_REF][START_REF] Ordonez | Mapping climatic mechanisms likely to favour the emergence of novel communities[END_REF]. Rapid rates of climate change could cause biological novelty, if suitable climate space shifts across the landscape faster than species dispersal velocity [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF][START_REF] Ordonez | Mapping climatic mechanisms likely to favour the emergence of novel communities[END_REF]. Rates of change in radiative forcing by greenhouse gases during the 20th century already have exceeded any rates sustained during the past 22 000 years [START_REF] Joos | Rates of change in natural and anthropogenic radiative forcing over the past 20,000 years[END_REF]) and rates of climate change are predicted to exceed those experienced by ecosystems during the past 20 000 years [START_REF] Diffenbaugh | Changes in ecologically critical terrestrial climate conditions[END_REF]. In addition to the effects of climate change, human agency is considered the major driver of the rise of novelty today [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF] due to widespread landscape management, the spread of alien invasive species, and land-use.

Vegetation models can be used to predict the emergence of biotic novelty [START_REF] Reu | Future no-analogue vegetation produced by no-analogue combinations of temperature and insolation: no-analogue vegetation, temperature and insolation[END_REF]. However, the predictive power of vegetation models to forecast the reshuffling of species into novel associations in future novel climate combinations may be rather limited [START_REF] Williams | Novel climates, no-analog communities, and ecological surprises[END_REF]. Whether or not climate change propagates into the recombination of species may depend on the extent of their fundamental niches rather than on their modern realized niches, which are at the basis of most vegetation models [START_REF] Reu | Future no-analogue vegetation produced by no-analogue combinations of temperature and insolation: no-analogue vegetation, temperature and insolation[END_REF]. This difference between modern realized and fundamental niches might arise from the different climate space available at present-day, and from the effects of competition among species and actual disturbance regimes [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF]. Additionally, in some parts of the species' range populations were favoured or became locally extinct due to land-use pressure and anthropogenic disturbance [START_REF] Bradshaw | Regional spread and standscale establishment of Fagus sylvatica and Picea abies in Scandinavia[END_REF][START_REF] Tinner | The past ecology of Abies alba provides new perspectives on future responses of silver fir forests to global warming[END_REF]. Further, vegetation models are constrained by a limited set of environmental variables, and the effects of, for example, land-use changes and disturbances by wildfires are not fully implemented [START_REF] Reu | Future no-analogue vegetation produced by no-analogue combinations of temperature and insolation: no-analogue vegetation, temperature and insolation[END_REF][START_REF] Radeloff | The rise of novelty in ecosystems[END_REF].

The large majority of studies attempting to reconstruct the emergence of novelty are limited to relatively short time periods, typically no longer than a few centuries from past baselines to the present [START_REF] Hobbs | Novel ecosystems: implications for conservation and restoration[END_REF][START_REF] Radeloff | The rise of novelty in ecosystems[END_REF]. Therefore, the long-term dynamics of emergence of biotic novelty and the relationships to rates of environmental change are largely unknown. However, understanding the dynamics of novelty emergence has fundamental implications for ecology, evolution and conservation [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF][START_REF] Jackson | Modern analogs in Quaternary paleoecology: here Today, Gone Yesterday, Gone Tomorrow?[END_REF], as it relates to the broader question of whether species associations persist over time or are ephemeral. Several open questions were recently discussed by [START_REF] Jackson | Novel Ecosystems: Intervening in the New Ecological World Order[END_REF] including: does novelty always increase as a linear (or curvilinear) function of time from the observer, such that novelty is always high far in the future? Is novelty related to rates of environmental changes, such that it rises at times of high rates of environmental change? Can human agency accelerate the processes that lead to the rise of novelty?

Pollen records document vegetation composition changes on centennial to millennial timescales. These archival records suggest that ecological change is a key feature in a world of continual environmental flux [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF] and palaeoenvironmental databases [START_REF] Brewer | Late-glacial and Holocene European pollen data[END_REF] shed light on the dynamics of vegetation change at subcontinental scales [START_REF] Huntley | An Atlas of Past and Present Pollen Maps for Europe: 0-13,000-Years Ago[END_REF][START_REF] Williams | The ice age ecologist: testing methods for reserve prioritization during the last global warming: reserve selection and the ice age ecologist[END_REF]. The pattern of European land-cover change is increasingly well documented by fossil pollen records [START_REF] Brewer | Late-glacial and Holocene European pollen data[END_REF]) and the representation is being refined using quantitative assessments [START_REF] Gaillard | Holocene land-cover reconstructions for studies on land cover-climate feedbacks[END_REF]. These pollen records demonstrate that late-glacial to early-Holocene climatic changes triggered the spread and expansion of plant populations [START_REF] Birks | Two terrestrial records of rapid climatic change during the glacial-Holocene transition (14,000-9,000 calendar years BP) from Europe[END_REF][START_REF] Williams | Rapid and widespread vegetation responses to past climate change in the North Atlantic region[END_REF]. The clearance of European forests for agriculture, fuel and industrial resources started during the mid-Holocene and progressed over millennia [START_REF] Fyfe | From forest to farmland: pollen-inferred land cover change across Europe using the pseudobiomization approach[END_REF], reaching the lowest tree cover during the 18th century (Millennium Ecosystem Assessment 2005). Factors that are expected to cause a rise of biological novelty in the future have also acted in the past. For example, the high within-site rates of vegetation change (RoC) associated to the post-glacial spread of plants and to past anthropogenic land-cover changes [START_REF] Huntley | Dissimilarity mapping between fossil and contemporary pollen spectra in Europe for the past 13,000 years[END_REF][START_REF] Seddon | Climate and abrupt vegetation change in Northern Europe since the last deglaciation[END_REF], often coupled to the spread of agriculture may be compared to the currently observed spread of alien species and land-use changes. Based on this, we use the fossil record to investigate the long-term temporal and spatial patterns of emergence of novelty and its relations with RoC.

The degree of dissimilarity between contemporary and fossil pollen assemblages has been extensively investigated for a number of regions [START_REF] Overpeck | Quantitative interpretation of fossil pollen spectra: dissimilarity coefficients and the method of modern analogs[END_REF][START_REF] Huntley | Dissimilarity mapping between fossil and contemporary pollen spectra in Europe for the past 13,000 years[END_REF][START_REF] Bush | Amazonian paleoecological histories: One hill, three watersheds[END_REF]. Many of these studies revealed the past occurrence of pollen assemblages without close modern counterparts ('no-modern analogues'), thereby supporting [START_REF] Gleason | The individualistic concept of the plant association[END_REF] inferences on the individualistic range dynamics (Matthews 1996) and replacing, as previously suggested [START_REF] Davis | Quaternary history and the stability of forest communities[END_REF], the static view of coevolved plant communities.

But, rather than looking into the past with the eyes of a modern observer, here, we look forward from the past to reconstruct the long-term emergence of novelty, enabling comparisons between past and recent rates of novelty emergence. Given the presumed relationships between rates of environmental change and novelty [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF][START_REF] Radeloff | The rise of novelty in ecosystems[END_REF], we expect that the rate at which novelty arises is faster at times of rapid environmental changes, such as those characterizing the late-glacial to interglacial transition and the late-Holocene anthropogenic land-cover changes, which led to high rates of vegetation change (RoC) [START_REF] Huntley | Dissimilarity mapping between fossil and contemporary pollen spectra in Europe for the past 13,000 years[END_REF][START_REF] Seddon | Climate and abrupt vegetation change in Northern Europe since the last deglaciation[END_REF]. Smaller amplitude Holocene climate variations (NGRIP Members 2004) and the more gradual and site-specific impact of earlier human-induced landscape changes are expected to have given rise to slower emergence of novelty.

MATERIALS AND METHODS

We define biological novelty as the degree of dissimilarity between entities (here pollen assemblages) in a baseline set and their closest counterpart in future target sets [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF]. Hence, across-site 'novelty' as defined here is distinct from within-site 'vegetation change' (RoC), because places that change the most are not necessarily the most novel [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF]: a similar pollen assemblage may be found at any time in a different region due to range shifts of taxa.

To explore the novelty dynamics relative to past baseline conditions, we use a compilation of M = 772 pollen records (Fig. 1a) from the European Pollen Database (EPD) [START_REF] Brewer | Late-glacial and Holocene European pollen data[END_REF] with associated age information based on calibrated-age-scale chronologies (cal BP; were 0 cal BP = AD 1950) and metadata (Appendix S1). For each record, we extracted pollen counts of the 43 most important terrestrial pollen taxa (Table S1) and collated the counts into N = 31 consecutive 500-year wide age bins centred on full 500-year intervals between 15 000 and 0 cal BP (see Appendix S1). Collated counts were converted to proportions based upon the pollen sum of the 43 terrestrial pollen taxa. Thereafter, all data in each of the 30 age bins from 15 000 to 500 cal BP was considered as a data set describing the 'baseline conditions' (S 0n ) at a given time in the past (t 0n ; with n = 1,. . .,30), and for each baseline system, we built a series of 'target datasets' (S T = {S 0n+1 ,. . .,S 0n+k }; with k = NÀn) as the sets of all samples from all records for a given time that post-date the baseline. These represent the set of all 'future' systems from that baseline, and allow us to assess novelty in both time and space (Fig. 1b).

We use the chord distance (CD) as a measure for dissimilarity between pollen assemblages [START_REF] Overpeck | Quantitative interpretation of fossil pollen spectra: dissimilarity coefficients and the method of modern analogs[END_REF][START_REF] Williams | Novel climates, no-analog communities, and ecological surprises[END_REF] to estimate within-site RoC and across-site novelty (for results obtained with other dissimilarity coefficients see Appendix S1). RoCs were computed as CD scores within each record between consecutive age bins [between S 0n and S 0n+1 ; as CD scores 9 (500 years À1 )] [START_REF] Huntley | Dissimilarity mapping between fossil and contemporary pollen spectra in Europe for the past 13,000 years[END_REF]). Across-site novelty was estimated iteratively between each S 0n baseline and each S T target system in the future of S 0n (Fig. 1b). To estimate the degree of novelty, we used the analogue-matching technique [START_REF] Overpeck | Quantitative interpretation of fossil pollen spectra: dissimilarity coefficients and the method of modern analogs[END_REF], which for each record i in S 0n identifies among all records in the selected S T dataset the record j giving the smallest CD score (CD ij,min ; i.e. the closest analogue) [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF] (Fig. 1c).

Novelty is a continuous variable, while the categorical differentiation of 'novel' vs. 'non-novel' ecosystems has proven difficult theoretically [START_REF] Aronson | The road to confusion is paved with novel ecosystem labels: a reply to Hobbs et al[END_REF]. We focused here on patterns of novelty rather than trying to strictly delineate novel vs. non-novel ecosystems, but used the nth percentile of all CD ij,min scores as a threshold to assess at what point novelty (the CD ij,min score) is large enough to represent a genuinely novel assemblage (see Appendix S1).

We extracted the geographical coordinates of the records to compute the displacement distance (km) on a geodetic ellipsoid between the location of each record i and its closest counterpart j, and divided that by the age difference between S 0n and S T to estimate the average velocity of displacement (km year À1 ) to the closest analogue in the target set.

Based on the values obtained above, we calculated median RoC and novelty scores for each S 0n to S 0n+1 couplet to detect periods characterized by overall higher within-site RoC and across-site novelty at time lags equal to 500 years from baseline conditions. We binned and differenced the Greenland d 18 O record (NGRIP Members 2004) to represent large-scale climate changes, and used linear mixed-effect models to explore the responses of RoC and novelty to the climate changes for the time periods before and after 8ka BP (see Appendix S1). We partitioned the within-site and the site-to-site variances to estimate the level of variability in site responses. To illustrate the geographical distribution of RoC and novelty at lags +500 years, we produced gridded maps of RoC and CD ij,min values grouped into quartiles for selected baseline ages. Values for grid cells of 50 9 50 km were obtained by application of a tricube distance-weighting function with a horizontal search radius of 300 km.

To illustrate the temporal dynamics of novelty emergence for each baseline system S 0n , we computed for each set of baseline-to-target couplet (S 0n À S T ) the median degree of novelty (CD ij,min ), the median distance (in km) and the median displacement velocity (in km year À1 ) to the closest analogue. We estimated the rate of novelty change as the difference between median novelty values for consecutive S T systems (as median novelty 9 500 years À1 ). These variables are arranged in triangular matrices with dimensions of 15 9 15 and were represented graphically using heat maps.

All data analyses were carried out using the R statistical language and associated packages (see Appendix S1).

RESULTS

Rates of vegetation change and novelty between consecutive time slices

Median RoC scores are highest (> 0.2) during the Bølling, the early-Holocene (from 11 500 to 10 000 cal BP) and the past 1500 years (Fig. 2c), indicating that these are the periods with highest within-site rate of vegetation change. Lowest values are detected when evaluating within-site vegetation change from 12 500 to 12 000 cal BP and during the mid-Holocene (9000-5500 cal BP). The closest analogues were allowed to occur in any of the sites of the target dataset, including the same site. This allows a check as to whether the closest analogues occur within the baseline sites. In this case, the RoC and novelty scores would be equivalent, which they are not (Fig. 2). Compared to RoC, the median and the quartile novelty scores are equally elevated for the last 9000 years, while they are lower for the late-glacial, and the early-and late-Holocene indicating that in those periods the baseline assemblages and the closest analogues are not from the same sites. This is confirmed by the geographical distances to the closest analogue (Fig. 2d), which are high during the late-glacial, the early-Holocene, and the late-Holocene. The highest distances to the closest analogue are found for the early-Holocene, while novelty is relatively low for the same period. By contrast, baseline assemblages between 8000 and 2000 cal BP have lowest geographical distances to the closest analogue. Varying site density (Fig. 2f) has no significant effects on the displacement-distance trends (see Appendix S1).

Linear mixed-effect models show significant relationships between climatic changes (differenced NGRIP d 18 O values) and RoC and novelty for both pre-8ka and post-8ka periods. However, the relationships are strongest for RoC in the pre-8ka BP period (see Appendix S1). This can be further seen in the variance components of the models, with a larger amount of variance explained within sites (c. 88%) for RoC pre-8ka BP, than in the other models (c. 54-67%), indicating higher spatial variability in RoC response post-8ka BP, and novelty in both periods.

The spatial distribution of RoC and novelty scores (Figs 3 and 4) shows stable vegetation composition in northern Europe vs. continuous change further south for the last 9000 years. Similarities between the two assessments of compositional change are also seen for the Younger Dryas. In contrast, early-Holocene novelty is relatively low in central Europe while RoC values are high.

Long-term emergence of novelty relative to past baseline conditions

To illustrate the emergence of novelty from the virtual perspective of an observer living in the past, we summarized the © 2017 John Wiley & Sons Ltd/CNRS novelty scores using the median value for each baseline-to-target couplet (Fig. 5a). For every baseline, the development of novelty in its contingent futures can be followed moving along the x-axis. Hence, the squares along the diagonal represent the median novelty for a single 500-year time-step from the baseline, as plotted in Fig. 2d. Median novelty to the nearest counterpart in target bins often increases as time from baseline increases (Fig. 5a). However, for some baselines median novelty decreases, in other words novelty 'cycled backward'. Hence, novelty does not increase as a constant, linear function of time from baseline conditions, and different trajectories can be discerned depending on the composition of baseline pollen assemblages. Contour lines (Fig. 5a), separating median novelty values at equal intervals, are sometimes packed together as a result of steeper increases of median novelty indicating more rapidly reshuffling of communities that were present in the baseline sets. Conversely, when median novelty levels off, contour lines are stretched further apart. For example, early-Holocene baseline landscapes found similarly close counterparts in mid-to-late-Holocene targets, and several late-glacial baselines had more dissimilar counterparts in the mid-Holocene than in late-Holocene targets. These novelty-emergence trends are mirrored by the proportion of sites experiencing a relatively high acrosssite turnover that is broadly comparable to present-day vegetation turnover between biomes (see Appendix S1).

To highlight the changes of novelty through time, Fig. 5b shows the rate of novelty change between consecutive target systems. For most baselines younger than 7000 cal BP, median novelty continuously increased and jumped when © 2017 John Wiley & Sons Ltd/CNRS compared to target sets younger than 1000 cal BP. For earlier baselines, the trajectory of novelty development is more variable, including distinct jumps at 11 000 and 9000 cal BP, strongest backwards cycling centred around 1000 cal BP, and levelling off or decreasing novelty during the late-Holocene.

The median displacement distance to the closest analogues in target sets (Fig. 5c) generally increases as a function of time and the highest median displacement distances (> 1200 km) are found when considering late-glacial and early-Holocene baselines and late-Holocene targets. Lowest median displacement distances (< 200 km) lasted longer for mid-and late-Holocene baselines than for most late-glacial baselines, and the highest median displacement velocities (ca. 0.3 km year À1 ) are displayed for early-Holocene baselines (Fig. 5d). Varying site density (Fig. 2f) has no influence on the displacementdistance trends (Appendix S1).

Median displacement velocities between closest analogues at the two endpoints of the baseline-target couplets, show opposite long-term trends (Fig. 5d). Long-term velocity decreases for late-glacial and early-Holocene baseline assemblages, indicating that the fastest shifts occurred shortly after baseline conditions, whereas later shifts were slower. By contrast, midand late-Holocene baseline assemblages experienced gradually increasing velocities, because closest analogues were found initially closer to the site. An increase in displacement velocities characterizes all late-Holocene baselines younger than 4000 cal BP when compared to target sets of the past 1000 years, indicating that an acceleration of displacement velocities occurred.

DISCUSSION

Until now, analyses of novelty emergence have been limited to short time periods from past baselines to the present [START_REF] Hobbs | Novel ecosystems: implications for conservation and restoration[END_REF][START_REF] Radeloff | The rise of novelty in ecosystems[END_REF]. Here, we sampled the fossil pollen record over a c. 15 ka time scale to investigate how novelty was related to RoC at time lags of 500 years, and reconstruct the longer term emergence of novelty in different snapshots of the contingent futures for several baselines in the past. Our results provide new insights into several key aspects of novelty development in relation to environmental changes. We show that (1) the largest rise in RoC at the beginning of the Holocene was not associated with rising novelty because the spread of plants mitigated the effects of short-term rates of environmental changes on novelty emergence, (2) novelty rose fast with human land-use, and landuse change had a greater effect than post-glacial climatic changes, (3) although novelty generally increases as a function of time, its temporal emergence followed baseline-specific trajectories, and (4) emergence of novelty accelerated due to the contribution of anthropogenic land-cover changes.

We considered the emergence of novelty as a pervasive and continuous process [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF] and avoided categorizing novelty as a binary variable (e.g. 'novel' vs. 'nonnovel'). Nevertheless, using the 75th and 95th percentiles of all CD ij,min distances for all baselines and all target sets as thresholds to determine the abundance of genuinely novel counterparts (Appendix S1) yields the same patterns as the median degree of novelty (Fig. 5a). Therefore, median novelty is a representative estimate of baseline assemblages experiencing genuinely novel conditions, i.e. shifts in vegetation composition in the order of magnitude of present-day turnover between vegetation types or biomes. Other thresholds would lead to correspondingly larger or more restricted estimates of the area of novel ecosystems, but the spatiotemporal patterns of novelty (Figs 4 and5) would remain unchanged.

SHORT-TERM EMERGENCE OF NOVELTY IN RELATION TO RATES OF VEGETATION CHANGE

At the scales considered here, we found a strong association between novelty and RoC, both temporally (Figs 2b andc) and spatially (Figs 3 and4). High rates of environmental changes have been advocated as a potential cause of higher novelty based on the assumptions that (1) favourable climatic conditions may shift across the landscape faster than species disperse into new areas of suitable climate space [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF]Ohlem€ uller et al. 2006), and that (2) land-use pressure induced habitat transformation, habitat fragmentation and spread of alien invasive species may promote the reshuffling of species into novel ecosystems [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF]. While we did not estimate post-glacial velocities of climatic change [START_REF] Ordonez | Climatic and biotic velocities for woody taxa distributions over the last 16 000 years in eastern North America[END_REF] or anthropogenicinduced rates of environmental change, highest rates of environmental change occurred when RoC scores were high (Fig. 2c): (1) during the late-glacial and the early-Holocene, which were characterized by pronounced and frequent changes in vegetation composition [START_REF] Birks | Two terrestrial records of rapid climatic change during the glacial-Holocene transition (14,000-9,000 calendar years BP) from Europe[END_REF][START_REF] Giesecke | The pace of Holocene vegetation changesynchronous developments versus chance[END_REF] and in climatic conditions (Fig. 2b), and (2) during historical times, with the increase in human populations and accompanying land-use [START_REF] Huntley | Dissimilarity mapping between fossil and contemporary pollen spectra in Europe for the past 13,000 years[END_REF][START_REF] Seddon | Climate and abrupt vegetation change in Northern Europe since the last deglaciation[END_REF]. However, the magnitude of the responses varied, as novelty was generally lower than RoC scores (Fig. 2c andd and legends to Figs 3 and4). Based on linear mixed models, climate change is a stronger predictor for within-site variation in RoC, while the novelty response displays a larger betweensite variance (see Appendix S1). These patterns suggest that novelty and RoC may differ in the degree at which they respond to environmental changes, and that across-site novelty varies at a slower pace than the location-specific vegetation changes. The underlying causes of lower novelty might be best illustrated considering the early-Holocene time period, when the association between RoC and novelty was weakest (Fig. 2c andd) and changes in RoC and novelty had a significant positive relationship with d 18 O changes (see Appendix S1). This period was marked by highest geographical distances to closest analogues (Fig. 2e) and by high rates of spread of early-successional plants, such as Pinus, Betula, Ulmus and Corylus [START_REF] Feurdean | Tree Migration-Rates: Narrowing the Gap between Inferred Post-Glacial Rates and Projected Rates[END_REF]. Therefore, we interpret the low early-Holocene emergence of novelty as the consequence of the rapid post-glacial range shifts of taxa. The vegetation composition changed rapidly at most locations, as shown by the highest within-site variance in the linear mixedeffect models for RoC pre-8ka BP (see Appendix S1). Hence, the high rates of spread meant that replacement by lownovelty counterparts occurred across the landscape, thereby reducing the novelty. This finding is at odds with the assumption that favourable climatic conditions can shift across the © 2017 John Wiley & Sons Ltd/CNRS landscape faster than species disperse into new areas of suitable climate space [START_REF] Jackson | Responses of plant populations and communities to environmental changes of the late Quaternary[END_REF]Ohlem€ uller et al. 2006).

It is difficult to say if rates of spread will mitigate the emergence of novelty in the future. Our estimates of early-Holocene median displacement velocities (c. 0.35 km year À1 ; Fig. 5e) are consistent with predicted mean climate velocities for the temperate broadleaf and mixed forests biome [START_REF] Loarie | The velocity of climate change[END_REF]) and with climate-displacement estimates for the past century [START_REF] Ordonez | Mapping climatic mechanisms likely to favour the emergence of novel communities[END_REF]). However, it is possible that such high rates of spread were limited to the particular environmental conditions encountered during the early-Holocene. At that time, landscapes were fairly open and dominated by early-successional pioneer taxa spreading fast as a result of their life-history strategies (fast growth, large seed production, good dispersal), and greater stress tolerance to large amplitude temperature change and drought [START_REF] Bhagwat | Species persistence in northerly glacial refugia of Europe: a matter of chance or biogeographical traits?[END_REF]. Competition was probably low, and even later-successional taxa with heavy seeds like Quercus reached high rates of spread [START_REF] Giesecke | Did thermophilous trees spread into central Europe during the Lateglacial?[END_REF].

The median novelty for recent target sets exceeds the background of post-glacial novelty (Fig. 2). Over the Middle Ages and the Industrial Revolution, land-cover changes associated with booming human population and agriculture became major determinants for vegetation changes, particularly in Southern and Central Europe [START_REF] Kaplan | The prehistoric and preindustrial deforestation of Europe[END_REF][START_REF] Gaillard | Holocene land-cover reconstructions for studies on land cover-climate feedbacks[END_REF]. Pasture grassland and arable or disturbed land increased, which led to a decrease in forest cover [START_REF] Fyfe | From forest to farmland: pollen-inferred land cover change across Europe using the pseudobiomization approach[END_REF]. Moreover, cultural landscapes became ever more characterized by forest-management practices, and by introduced or cultivated trees for wood and food production [START_REF] Conedera | The cultivation of Castanea sativa (Mill.) in Europe, from its origin to its diffusion on a continental scale[END_REF]). The finding of strongest novelty rise for these target sets thus demonstrates that in Europe the effects of landuse were more important than post-glacial climatic changes for the emergence of novelty at a time lag of 500 years.

We found lower novelty, thus more persistent analogy with their future closest counterparts, for late-Holocene Fennoscandian sites than for Central and Southern European sites (Fig. 4). These spatial patterns are at odds with vegetation-modelling results [START_REF] Reu | Future no-analogue vegetation produced by no-analogue combinations of temperature and insolation: no-analogue vegetation, temperature and insolation[END_REF], which predict higher biological novelty in eastern Scandinavia based only on the effects of abiotic factors. By contrast, our findings are consistent with prior results that inferred lower novelty in Fennoscandia based on the effects of abiotic factors plus human population for historical to modern (AD 1900(AD -2000) ) and for modern to projected (AD 2000(AD -2050) ) baseline-to-target couplets [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF]. Hence, our results support the view that land-use adds complexity to the modelling of future biological novelty that should be accounted for in analyses of the probability of future effects of climate forcing and land-use change scenarios [START_REF] Ordonez | Combined speeds of climate and land-use change of the conterminous US until 2050[END_REF]). Yet, at these short-term time lags, most baseline sites did not encounter genuinely novel assemblages (see Appendix S1).

Long-term emergence of novelty

To our knowledge, this study is the first to separately analyse the long-term emergence of novelty for a large set of prehistorical and historical baselines. Our data show that novelty often increases as a function of time from the virtual perspective of an observer living in the past (Fig. 5a), and thereby confirms earlier theoretical considerations [START_REF] Jackson | Vegetation, environment, and time: the origination and termination of ecosystems[END_REF][START_REF] Jackson | Novel Ecosystems: Intervening in the New Ecological World Order[END_REF] that were based on the evidence of the rather recent emergence of some modern ecosystems, and the occurrence in the past of no-modern analogue vegetation assemblages [START_REF] Overpeck | Mapping eastern North American vegetation change of the past 18 ka: no-analogs and the future[END_REF][START_REF] Jackson | Modern analogs in Quaternary paleoecology: here Today, Gone Yesterday, Gone Tomorrow?[END_REF]). However, we found that the emergence of novelty followed different, baseline-specific trajectories (Fig. 5a), confirming the view that it is only meaningful to talk about levels of novelty relative to a specific temporal baseline [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF].

We found that novelty did not develop as a constant, linear function of time from past baseline conditions (Fig. 5b), which would imply a gradually changing world with steadily accumulating changes [START_REF] Jackson | Novel Ecosystems: Intervening in the New Ecological World Order[END_REF]): evidence of novelty jumps occurring several millennia after baselines at times of rapid environmental changes indicate an accelerated reshuffling of vegetation composition across sites. The most distinct of all novelty jumps occurred around 8000 cal BP for Bølling baseline conditions (Fig. 5b). At that time, most of the open pine-and birch-dominated woodlands that characterized the Bølling landscapes of Western and Central Europe had gone. Further, European forest cover was overall at its Holocene maximum, although regional variability accounts for slightly shifted timing of maximum forest cover [START_REF] Fyfe | From forest to farmland: pollen-inferred land cover change across Europe using the pseudobiomization approach[END_REF]. In Central Europe, both Fagus and Abies expanded and compositional changes occurred probably in response to shifting climatic modes around 8200 cal BP [START_REF] Tinner | Holocene expansions of Fagus silvatica and Abies alba in Central Europe: where are we after eight decades of debate?[END_REF]. While this requires further investigation, it offers an example of how terrestrial ecosystems respond to non-linear environmental changes.

Our data indicate that environmental changes related to anthropogenic land-cover changes accelerated the emergence of novelty. Because novelty increased faster during the past millennium relative to baselines younger than 6000 cal BP (Fig. 5b), we interpret the jumps at 1000 cal BP as the consequence of the rapid emergence of pre-industrial and industrial cultural landscapes [START_REF] Kaplan | The prehistoric and preindustrial deforestation of Europe[END_REF][START_REF] Fyfe | From forest to farmland: pollen-inferred land cover change across Europe using the pseudobiomization approach[END_REF]. As increasing median displacement velocities to closest analogues are associated with this acceleration (Fig. 5d), it shows that anthropogenic land-cover changes were spatially widespread.

Conversely, we found backwards cycling of novelty (i.e. the transition from high to less novelty) between late-glacial baselines and late-Holocene targets, and a levelling-off of novelty between early-Holocene baselines and late-Holocene targets (Fig. 5a). [START_REF] Jackson | Novel Ecosystems: Intervening in the New Ecological World Order[END_REF] hypothesized the possibility of backwards cycling of novelty with glacial-interglacial cycles, based on the qualitative evidence that last glacial maximum environments and vegetation would have been more similar to those of other glacial maxima than to the interglacial periods. By contrast, because the late-Holocene vegetation composition changes and forest-cover reductions in Europe are mostly attributed to land-use intensification and forest clearance [START_REF] Henne | Impacts of changing climate and land use on vegetation dynamics in a Mediterranean ecosystem: insights from paleoecology and dynamic modeling[END_REF][START_REF] Fyfe | From forest to farmland: pollen-inferred land cover change across Europe using the pseudobiomization approach[END_REF], our results imply that novelty cycled backwards or levelled-off due to the contribution of land-use changes. Similar observations were made comparing early-Holocene assemblages from Central Italy to modern pollen assemblages [START_REF] Finsinger | Early to mid-Holocene climate change at Lago dell'Accesa (central Italy): Climate signal or anthropogenic bias?[END_REF].

The somewhat surprising finding of backwards cycling and of non-increasing novelty from late-glacial and early-Holocene baselines to pre-industrial cultural landscapes may be partly due to the low pollen-taxonomical resolution within herbaceous plant genera, which reduces our ability to distinguish pollen assemblages produced by different species compositions [START_REF] Jackson | Modern analogs in Quaternary paleoecology: here Today, Gone Yesterday, Gone Tomorrow?[END_REF]). An alternative, or additional, explanation is that Europe went from a late-glacial and early-Holocene steppe-dominated continent with groves of trees to a widely deforested landscape with extensive pastures, fields, heaths, maquis, settlements and secondary forests [START_REF] Birks | Past forests of Europe. In: European Atlas of Forest Tree Species (eds San-Miguel-Ayanz[END_REF]. The steppe elements became abundant again with the clearance of the forest for agriculture and form today's ruderal flora with only minor additions of archaeophytes that came with the import of seeds from the Near East. As a result, Allerød and early-Holocene baselines have high analogy (low novelty) to past and modern remnants of the steppe and boreal forests, which persisted in Europe throughout the Holocene and were displaced at increasing distance from the source locations (Fig. 5c).

Under some scenarios, a backwards cycling might be expected to occur in the future. Although Europe is still considered the continent with the smallest fraction of its original forests remaining (Millennium Ecosystem Assessment 2005), forest cover in Europe has increased during the last century due to the abandonment of agropastoral activities in economically marginal areas and the establishment of nature reserves (European Environment Agency 2016). If the current reforestation trend will continue in spite of the growing predicted land-use pressure [START_REF] Montesino Pouzols | Global protected area expansion is compromised by projected land-use and parochialism[END_REF], reforested areas may be expected to buffer the rise of future novelty with respect to mid-Holocene baselines. These were characterized by highest forest cover [START_REF] Fyfe | From forest to farmland: pollen-inferred land cover change across Europe using the pseudobiomization approach[END_REF] and are, among all Holocene baselines, the ones showing the highest proportion of between-vegetation-type turnover relative to their closest counterparts in modern cultural landscapes (see Appendix S1).

We found a complex relationship between the post-glacial trajectories of novelty and RoC. Whereas RoC increased at times of rapid climate change and during historical times, the rate of novelty emergence in historical times exceeded the longer term background variability (Figs 2d and5b). The results support the notion that the search for static conservation targets in dynamic environments is likely to be elusive [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF], since landscapes are inherently transitory and the emergence of novelty is inevitable [START_REF] Williams | Novel climates, no-analog communities, and ecological surprises[END_REF]) on longer term timescales. In addition, they show that unintentional and intentional human action has contributed to a faster rise of novelty earlier than was previously assumed [START_REF] Radeloff | The rise of novelty in ecosystems[END_REF].

Our approach presents an explicitly future-driven perspective of vegetation composition changes through time that provides a valuable long-term perspective on the dynamics and legacies of past ecological systems, which may help bridging the gap between palaeoecology and ecology [START_REF] Willis | What is natural? The need for a longterm perspective in biodiversity conservation[END_REF]. Further evaluation of our results should be done through comparison with vegetation and climate models.

Figure 2 Figure 3 Figure 4

 234 Figure 2 Comparison between (a) Greenland oxygen-isotope (d 18 O) record (NGRIP Members 2004) as a template of climate change over Europe [plotted on the GICC05 age scale (Rasmussen et al. 2014)], (b) difference between average of binned d 18 O values among consecutive age bins as a template of rate of climate change, (c) median rate of vegetation change(RoC) within sites between consecutive age bins (note that y-axis was cropped between 0.375 and 0.47 CD), (d) median degree of novelty across sites between consecutive age bins, (e) geographical distance to the closest analogue in time slice +500 years relative to the baseline conditions, (f) number of records included in each time slice. The blue-shaded areas: range of values between the first and third quartiles within each age bin, and the vertical grey-shaded area marks the Younger Dryas (YD). Bø/Al: Bølling/Allerød.

Figure 5

 5 Figure5Summary heat maps showing, for each past 'baseline dataset' (y-axis), (a) the median degree of novelty, (b) the change in median novelty per 500 years step (to highlight negligible changes, values around the zero (+5% and À5% of the total range) were grouped together), (c) the median displacement distance (km), and (d) the median displacement velocity (as km year À1 ) to the closest counterpart in the 'target dataset' (x-axis). Grey-shaded area marks the Younger Dryas (YD).

(c) S 02 -S 03 S 03 -S 04 S 04 - -S 031

  Figure1Schematic representation of the theoretical approach used in this study: (a) Spatial distribution of EPD pollen records (red circles) used in this study. (b) A data set (S 0n ) comprizing pollen assemblages that characterize vegetation for a 500-year long snapshot is considered as representing 'average baseline conditions' at time t 0n . Rate of vegetation change within sites was calculated as chord distance (CD) between datapoints of the same site in consecutive time slices (i.e. for all S 0n -S 0n+1 couplets). To reconstruct the long-term dynamics of novelty emergence, the system S 0n is iteratively compared to each of the 500-year wide 'target systems' (S T = {S 0n+1 ,. . .,S 0n+k }) in its contingent futures (where S 0n+k describes near-to modern conditions, i.e. 0 cal BP). (c) The degree of novelty is quantified as the minimum CD distance (CD ij,min ) between entity i of the baseline set and the closest counterpart j in the target set in a multivariate space. In the example in (c), samples are plotted in a reduced space (axes 1 and 2), black dots indicate entities of S 0n , blue dots indicate entities belonging to a target set S 0n+k , and red arrows indicate the minimum distance (CD ij,min ) between entities of the two sets. Entities 1-3 experienced increasing degrees of novelty (modified from[START_REF] Radeloff | The rise of novelty in ecosystems[END_REF].

	(a)
	(b)	Rate of	change	S 01 -S 02		...	...
					t	1	t 2	t 3	t	4	....	t
	Novelty	Baseline age (cal yrs BP)	.... t t t 1 2 3 30 t	S 01	S S 02 01+1	S S S 03 02+1 01+2	S S S 0... 03+1 02+2 S 01+3	S ...... 030 ...... ...... ......	S S S S S 030+1 0...+k 03+k 02+k 01+k
					t	1	t 2	t 3	t	4	....	t
										Recent
										S 0+k
	Dimension 2		S 0	3			1	2
								Dimension 1

31 Age (cal yrs BP) 31 Past Target age (cal yrs BP)

© 2017 John Wiley & Sons Ltd/CNRS 344 W. Finsinger et al.Letter

ACKNOWLEDGEMENTS

We thank Gavin Simpson and two anonymous reviewers for their thoughtful comments. Pollen data were extracted from the European Pollen Database (EPD; http://www.europeanpol lendatabase.net/), and the work of the data contributors and the EPD community is gratefully acknowledged.

AUTHORSHIP

WF, TG and SB designed the experiments; ML compiled the data, WF developed and performed the RoC and novelty analyses, and the gridded maps; SB developed and performed the linear mixed-effect models. All authors analysed the results and contributed to writing the manuscript.

DATA ACCESSIBILITY STATEMENT

Data and R scripts to replicate all the calculations for results presented in the paper are available from the Dryad Digital Repository: https://doi.org/10.5061/dryad.cg250.

SUPPORTING INFORMATION

Additional Supporting Information may be found online in the supporting information tab for this article.