Yves Mocquard

Bruno Sericola

Emmanuelle Anceaume

Balanced allocations and global clock in population protocols: An accurate analysis (Full version)

The context of this paper is the two-choice paradigm which is deeply used in balanced online resource allocation, priority scheduling, load balancing and more recently in population protocols. The model governing the evolution of these systems consists in throwing balls one by one and independently of each others into n bins, which represent the number of agents in the system. At each discrete instant, a ball is placed in the least filled bin among two bins randomly chosen among the n ones. A natural question is the evaluation of the difference between the number of balls in the most loaded and the one in the least loaded bin. At time t, this difference is denoted by Gap(t). A lot of work has been devoted to the derivation of asymptotic approximations of this gap for large values of n. In this paper we go a step further by showing that for all t ≥ 0, n ≥ 2 and σ > 0, the variable Gap(t) is less than a(1 + σ) ln(n) + b with probability greater than 1 -1/n σ , where the constants a and b, which are independent of t, σ and n, are optimized and given explicitly, which to the best of our knowledge has never been done before.

Introduction

In this paper we address the important issue of the two-choice paradigm analysis [START_REF] Mitzenmacher | The power of two random choices: A survey of techniques and results[END_REF]. To illustrate the multi-choice paradigm, suppose that we have a set of m balls which are sequentially throws into n bins, where each ball is placed in the least filled bin among d ≥ 1 ones randomly chosen among the n bins. Azar et al. [START_REF] Azar | Balanced allocations (extended abstract)[END_REF] have characterized this problem by those three values (m, n, d). A natural question is the analysis of the maximum load in any of the bins, or the maximal gap that may exist between the least loaded bin and the most loaded one. It has been proven that in the simplest case where d = 1 (see for example [START_REF] Raab | Balls into bins" -a simple and tight analysis[END_REF]), the maximum load is equal to m/n + Θ ( √ (m/n) ln n

) , leading to a gap that increases with the square root of m. Now, instead of choosing a single bin at random, d ≥ 2 bins are independently and randomly chosen, and the least loaded bin one among those d ones receives a ball. Then Azar et al. [START_REF] Azar | Balanced allocations (extended abstract)[END_REF] have shown that when m = n the maximum load is ln(ln(n))/ ln(2) + O [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF], and the largest gap is also equal to ln(ln(n))/ ln(2) + O [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF]. These results show that by simply introducing a small choice we get a drastically improved balanced load among all the urns. Citing Mitzenmacher et al [START_REF] Mitzenmacher | The power of two random choices: A survey of techniques and results[END_REF], "having just two random choices (i.e., d = 2) yields a large reduction in the maximum load over having one choice, while each additional choice beyond two decreases the maximum load by just a constant factor". Hence the name of the two-choice paradigm. Later Berenbrink et al. [START_REF] Berenbrink | Balanced allocations: The heavily loaded case[END_REF] have studied the case (m, n, d) for d ≥ 2 and m ≫ n, and proved that the maximum load is equal to m/n + O(ln(ln(n))). Note that a simpler proof of this result has been recently found by Talwar and Wieder [START_REF] Talwar | Balanced allocations: A simple proof for the heavily loaded case[END_REF]. Very recently, Peres et al. [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF][START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF], using a measurement based on the hyperbolic cosine, have generalized the problem in the (1 + β)-choice problem. The (1 + β)-choice consists, with probability 1 -β, in choosing one bin uniformly at random and to throw a ball in it, and with probability β, in choosing two bins uniformly at random and to throw a ball in the least loaded one. The name comes from the fact that E{d} = 1 + β. We can note that in their model, each ball is assigned with a random weight. They found a logarithmic bound for both the gap between the maximum loaded bin and the average one [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF], and for the gap between the maximum loaded bin and the minimum one [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF]. In both cases the gap is O (log(n)/β).

The two-choice paradigm can be used in a multitude of applications, including balanced online resource allocation (where jobs need to be dynamically allocated to the least loaded processor) [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF][START_REF] Berenbrink | Infinite parallel job allocation (extended abstract)[END_REF][START_REF] Berenbrink | Allocating weighted jobs in parallel[END_REF], priority scheduling [START_REF] Alistarh | The power of choice in priority scheduling[END_REF], load balancing [START_REF] Adler | Parallel randomized load balancing[END_REF][START_REF] Berenbrink | Balanced allocations: The heavily loaded case[END_REF][START_REF] Mitzenmacher | Load balancing and density dependent jump Markov processes[END_REF], and very recently, population protocols [START_REF] Alistarh | Space-optimal majority in population protocols[END_REF]. In the later case, the model governing the evolution of these systems consists in throwing balls one by one and independently of each others into n bins, which represents the number of agents in the system. At each discrete instant, a ball is placed in the least filled bin among two bins randomly chosen among the n ones. A natural question is the evaluation of the difference between the number of balls in the most loaded and the one in the least loaded bin. At time t, this difference is denoted by Gap(t). A lot of work has been devoted to the derivation of asymptotic approximations of this gap for large values of n. In this paper we go a step further by showing that for all t ≥ 0, n ≥ 2 and σ > 0,

P {Gap(t) ≥ a(1 + σ) ln(n) + b} ≤ 1 n σ , ( 1
)
where the constants a and b, which are independent of t, σ and n, are optimized and given explicitly, which to the best of our knowledge has never been done before.

The remaining of the paper is structured as follows. In Section 2 we present the addressed problem and a simple algorithm to solve it. Section 3 is the main contribution of our work which consists in providing an accurate bound of the distribution of the gap between any two nodes. Section 4 evaluates constants a and b obtained by our analysis and compares it to constants that we derived from the work of [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]. The gain in accuracy we obtained by our analysis is significant. Finally Section 5 provides a summary of simulations results.

Problem description

We consider a very large set of n nodes (also called agents), interconnected by a complete graph, that asynchronously start their execution in a given state. Agents do not maintain nor use identifiers (agents are anonymous and cannot determine whether any two interactions have occurred with the same agents or not). However, for ease of presentation the agents are numbered 1, 2, . . . , n. Each agent keeps a local counter, initialized at 0. Agents communicate through random pairwise interactions. On each interaction, the two interacting agents compare their counters, and the one with the lower counter value increments its local counter. The objective of this simple algorithm is the construction of a global clock by guaranteeing that the values of all agent counters are concentrated according to Relation [START_REF] Adler | Analyzing an infinite parallel job allocation process[END_REF]. As interactions are uniformly random, this can be related to the classic two choices load balancing process [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF]. The goal of the paper is to evaluate the gap between any two agents, that is the maximal difference that may exist at any time t between any two local counters, by accurately evaluating constants a and b. By accurately estimating the maximal gap between any two counter nodes, other population protocols can use it as a global clock to perform actions in a probabilistic synchronized way.

We denote by C (i) t the state of agent i at time t. The stochastic process C = {C t , t ≥ 0}, where

C t = (C (1) t , . . . , C (n)
t ), represents the vector state of the system at time t. The choice of the two agents which interact is made using a uniform distribution. Given the pair (i, j) 2 of agents which interact at time t, we consider the following evolution of the agents states

( C (i) t+1 , C (j) t+1 ) =        ( C (i) t + 1, C (j) t ) if C (i) t ≤ C (j) t ( C (i) t , C (j) t + 1 ) if C (i) t ≥ C (j) t .
Note that in the case where agents i and j interact at time t with

C (i) t = C (j) t
then either of two agents can be chosen to have its value increased by 1 at time t + 1. A particular choice is made below.

The state space of process C is thus N n and a state of this process is also called a protocol configuration. At time 0, we set C (i) t = 0, for every i = 1, . . . , n. At each instant the value of only one agent is increased by 1 which means that we have, for every t ≥ 0,

n ∑ i=1 C (i) t = t.
For every i = 1, . . . , n, we introduce the quantities x i (t) = C (i) t -t/n, which leads, for every t ≥ 0, to

n ∑ i=1 x i (t) = 0.
The value C (i) t maintained by agent i is its own view of the global clock t of the system divided by n. More precisely, the approximation of time t, provided by agent i, is nC

(i) t .
At each discrete time t ≥ 0, any two indices i and j are uniformly chosen to interact, independently of the vector state with probability 1/(n(n -1)).

In order to simplify the presentation, we suppose without any loss of generality that at each instant t, the values of x i (t) are reordered in a decreasing way, assigning an arbitrary order to agents with the same value. More precisely, at time t the reordering gives

x 1 (t) = max i=1,...,n (C (i) t -t/n) ≥ • • • ≥ x n (t) = min i=1,...,n (C (i) t -t/n).
We denote by X the rank of the agent whose value is incremented when interaction occurs between 2 agents. In the case where two agents interacting, say i and j, are such that

C (i) t = C (j)
t , we choose to increase by 1 the one with the highest rank. If X 1 and X 2 are the ranks of the successive agents which interact, then the probability p ℓ that agent of rank ℓ is incremented is given, for ℓ = 1, . . . , n, by

p ℓ = P{X = ℓ} = P{X 1 = ℓ, X 2 < ℓ} + P{X 1 < ℓ, X 2 = ℓ} = 1 n ( ℓ -1 n -1 ) + ( ℓ -1 n ) 1 n -1 = 2(ℓ -1) n(n -1) (2
) As mentioned in the introduction, the goal of the paper is the evaluation of the distribution of difference between the maximum and the minimum of the entries of vector C t . This difference is denoted by Gap(t) and is given, for t ∈ N, by

Gap(t) = max 1≤i≤n C (i) t -min 1≤i≤n C (i) t = x 1 (t) -x n (t).
In order to bound the complementary distribution of Gap(t), we introduce the following potential functions defined, for α ∈ R, by

Φ(t) = n ∑ i=1 e αx i (t) , Ψ(t) = n ∑ i=1 e -αx i (t) and Γ(t) = Φ(t) + Ψ(t).
The use of these two functions has been proposed in a very clever way by Y. Peres et al. in [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF]. The potential function Γ(t) is then related to function Gap(t) by the following lemma.

Lemma 2.1 For every t ≥ 0, we have

Γ(t) ≥ 2e αGap(t)/2 .
(3)

Proof. The exponential function being convex, we have, for every a, b ∈ R, 2e (a+b)/2 ≤ e a + e b . Recalling that Gap(t) = x 1 (t) -x n (t), we obtain

Γ(t) = n ∑ i=1 e αx i (t) + n ∑ i=1
e -αx i (t) ≥ e αx 1 (t) + e -αxn(t) ≥ 2e α(x 1 (t)-xn(t))/2 = 2e αGap(t)/2 , which completes the proof. This result will be used at the end of the paper for the evaluation of the distribution of Gap(t) which is based on the evaluation of the one of Γ(t), which forms the main part of the paper.

Analysis

We first need the two following technical lemmas which are proved in the Appendix.

Lemma 3.1 For all x ∈ R, we have 1 + x ≤ e x . For all x ∈ (-∞, c], we have e x ≤ 1 + x + x 2 ,
m n = 1 n n ∑ k=1 v k .
If the sequences u and v are both non-decreasing or both non-increasing then we have

n ∑ k=1 u k v k ≥ m n n ∑ k=1 u k .
If one of these two sequences is non-increasing and the other is non-decreasing then we have

n ∑ k=1 u k v k ≤ m n n ∑ k=1 u k .
For every t ≥ 0, we introduce the notation x(t) = (x 1 (t), . . . , x n (t)).

Lemma 3.3

For all α ∈ (-1, 1), we have

E{Φ(t + 1) -Φ(t) | x(t)} ≤ ( α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e αx i - ( α n - α 2 n 2 ) Φ(t). ( 4
)
Proof. Since the x i (t)'s are ordered, they may change value at each time. We can thus define a permutation on {1, 2, . . . , n} named σ t such that, for every u = 1, . . . , n, if

x i (t) = C (u) t -t/n then x σt(i) (t + 1) = C (u)
t+1 -(t + 1)/n. Suppose that the rank of the agent (say agent u), whose value is incremented at time t, is equal to i. In this case, we have

x σt(i) (t + 1) = C (u) t+1 - t + 1 n = C (u) t + 1 - t + 1 n = C (u) t - t n + 1 + t n - t + 1 n = x i (t) + 1 - 1 n .
This leads, for every i = 1, . . . , n, to

x σt(i) (t + 1) = x i (t) + 1 {X=i} -1 n
, where 1 A is the indicator function of event A. We then get

Φ(t + 1) -Φ(t) = n ∑ i=1 ( e αx i (t+1) -e αx i (t) ) = n ∑ i=1 ( e αx σ t (i) (t+1) -e αx i (t) ) = n ∑ i=1 ( e α(1 {X=i} -1/n) -1 ) e αx i (t) .
Using the fact that e x ≤ 1 + x + x 2 for x ≤ 1, see Lemma 3.1, we obtain, since α(

1 {X=i} -1/n) ≤ 1, e α(1 {X=i} -1/n) -1 ≤ α(1 {X=i} -1/n) + α 2 (1 {X=i} -1/n) 2 = α(1 {X=i} -1/n) + α 2 ( 1 {X=i} (1 - 2 n ) + 1 n 2 ) = ( α + α 2 ( 1 - 2 n
))

1 {X=i} - ( α n - α 2 n 2
) .

Taking the expectation of Φ(t + 1) -Φ(t), given x(t), we obtain since

E{1 {X=i} } = p i , E{Φ(t + 1) -Φ(t) | x(t)} ≤ n ∑ i=1 [ p i ( α + α 2 ( 1 - 2 n )) - ( α n - α 2 n 2
)]

e αx i = ( α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e αx i - ( α n - α 2 n 2 ) Φ(t),
which completes the proof.

The following relations will be frequently used in the sequel. Since, for i = 1, . . . , n, p i = 2(i -1)/(n(n -1)), we have for all λ ∈ (0, 1) with λn ∈ N,

1 n n ∑ i=1 p i = 1 n (5) 1 λn λn ∑ i=1 p i = λn -1 n(n -1) ≤ λ n (6) 1 (1 -λ)n n ∑ i=λn+1 p i = (1 + λ)n -1 n(n -1) ≥ 1 + λ n ( 7
)
Corollary 3.4 For all α ∈ (0, 1), we have

E{Φ(t + 1) -Φ(t) | x(t)} ≤ α 2 n ( 1 - 1 n ) Φ(t).
Proof. To prove this result, observe that sequence (e αx i ) i is a non-increasing sequence and (p i ) i is an non-decreasing sequence, so using Relation (5) and applying Lemma 3.2 we obtain

n ∑ i=1 p i e αx i (t) ≤ 1 n ( n ∑ i=1 p i ) ( n ∑ i=1 e αx i (t) ) = Φ(t) n .
Putting this result in inequality (4), we get

E{Φ(t + 1) -Φ(t) | x(t)} ≤ ( α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e αx i - ( α n - α 2 n 2 ) Φ(t) ≤ [ α n + α 2 n ( 1 - 2 n ) - ( α n - α 2 n 2 )] Φ(t) = α 2 n ( 1 - 1 n ) Φ(t),
which completes the proof.

Lemma 3.5 For all α ∈ (-1, 1), we have

E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ ( -α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e -αx i + ( α n + α 2 n 2 ) Ψ(t). (8)
Proof. It suffices to replace α by -α in the proof of Lemma 3.3.

Corollary 3.6

For all α ∈ (0, 1), we have

E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ α 2 n ( 1 - 1 n ) Ψ(t) Proof. Observe that for α ∈ [0, 1], we have -α + α 2 (1 -2/n) ≤ 0. It follows that the sequence ( (-α + α 2 (1 -2/n))e -αx i )
i is a non-increasing sequence. Sequence (p i ) i is an non-decreasing sequence, so using Relation (5) and applying Lemma 3.2 we obtain

( -α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e -αx i (t) ≤ ( - α n + α 2 n ( 1 - 2 n )) n ∑ i=1 e -αx i (t) = ( - α n + α 2 n ( 1 - 2 n )) Ψ(t).
Putting this result in the inequality (8), we get

E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ ( -α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e -αx i + ( α n + α 2 n 2 ) Ψ(t) ≤ [ - α n + α 2 n ( 1 - 2 n ) + ( α n + α 2 n 2 )] Ψ(t) = α 2 n ( 1 - 1 n ) Ψ(t),
which completes the proof.

The two previous lemmas, which give a bound of the increase of functions Φ(t) and Ψ(t), will be used to prove Theorem 3.11. The proof of the results follow the clever ideas of the seminal paper [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF] in which the authors prove that Gap(t) is less than O(ln(n)) with high probability. In [START_REF] Alistarh | The power of choice in priority scheduling[END_REF], Alistarh et al. provide a more rigorous proof from which we have extracted constants associated with this asymptotic behavior. Those constants are given at the end of Section 4.

The main original idea of our paper is to parametrize as much as possible the proofs in order to obtain the smallest values of constants a and b used in Relation (1) which is proved in Theorem 3.13. The numerical evaluation of these constants, obtained in Section 4, shows that they are remarkably small with respect to the ones of [START_REF] Alistarh | The power of choice in priority scheduling[END_REF].

In the following, we introduce two variable parameters µ, ρ ∈ (0, 1/2) (which are fixed to 1/4 in [START_REF] Peres | Graphical balanced allocations and the (1 + β)-choice process[END_REF] and [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]). Since x i 's are non-increasing we have x ρn ≥ x (1-µ)n . Lemmas 3.7 and 3.8 deal with the balanced conditions case that is x ρn ≥ 0 ≥ x (1-µ)n . The unbalanced conditions that are the complementary cases x ρn ≥ x (1-µ)n > 0 and 0 > x ρn ≥ x (1-µ)n are considered respectively in Lemmas 3.9 and 3.10. Theorem 3.11 examines systematically each case which lead to recurrence relation for E{Γ(t)}. Theorem 3.12 uses this recurrence relation to bound E{Γ(t)}. Finally, Theorem 3.13 gives a precise lower bound of Γ(t) with high probability.

Lemma 3.7 Let α, µ ∈ (0, 1) with µn ∈ N and µ > α/(1 + α). If x (1-µ)n (t) ≤ 0 then we have E{Φ(t + 1) | x(t)} ≤ ( 1 - α n [ µ -α(1 -µ) + α(1 -2µ) n ]) Φ(t) + α + α 2 ( 1 - 2 n ) ≤ ( 1 - α n [µ -α(1 -µ)] ) Φ(t) + α + α 2 . ( 9
)
Proof. If x (1-µ)n ≤ 0 we have e αx i (t) ≤ 1 for every i > (1 -µ)n, so n ∑ i=1 p i e αx i (t) ≤ (1-µ)n ∑ i=1 p i e αx i (t) + n ∑ i=(1-µ)n+1 p i ≤ (1-µ)n ∑ i=1
p i e αx i (t) + 1.

We now use Lemma 3.3. Sequence ( e αx i (t) ) i is a non-increasing sequence and (p i ) i is an non-decreasing sequence. Using Relation (6) and applying Lemma 3.2 we obtain

(1-µ)n ∑ i=1 p i e αx i (t) ≤ (1 -µ)n -1 n(n -1)   (1-µ)n ∑ i=1 e αx i (t)   ≤ (1 -µ)Φ(t) n and so n ∑ i=1 p i e αx i (t) ≤ (1 -µ)Φ(t) n + 1.
Plugging this bound in inequality of Lemma 3.3 leads to

E{Φ(t + 1) -Φ(t) | x(t)} ≤ ( α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e αx i - ( α n - α 2 n 2 ) Φ(t) ≤ ( α + α 2 ( 1 - 2 n )) ( (1 -µ)Φ(t) n + 1
) -

( α n - α 2 n 2 ) Φ(t) ≤ [( α + α 2 ( 1 - 2 n )) ( 1 -µ n ) - α n + α 2 n 2 ] Φ(t) + α + α 2 ( 1 - 2 n ) = - α n [ µ -α(1 -µ) + α(1 -2µ) n ] Φ(t) + α + α 2 ( 1 - 2 n
) .

We complete the proof observing that E{Φ(t) | x(t)} = Φ(t). The second inequality is immediate.

An analogous result is obtained for Ψ(t) in the following lemma.

Lemma 3.8 Let α, ρ ∈ (0, 1) with ρn ∈ N and ρ > α/(1 -α). If x ρn (t) ≥ 0 then we have

E {Ψ(t + 1) | x(t)} ≤ ( 1 - α n [ ρ -α(1 + ρ) + α(1 + 2ρ) n ]) Ψ(t) + αρ(1 + ρ) ≤ ( 1 - α n [ρ -α(1 + ρ)] ) Ψ(t) + αρ(1 + ρ). ( 10
)
Proof. For α ∈ (0, 1), we have

-α + α 2 (1 -2/n) ≤ 0. We thus have ( -α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e -αx i (t) ≤ ( -α + α 2 ( 1 - 2 n )) n ∑ i=ρn+1 p i e -αx i (t) .
The sequence

( (-α + α 2 (1 -2/n))e -αx i (t) )
i is a non-increasing sequence and the sequence (p i ) i is an non-decreasing sequence, so using Relation [START_REF] Berenbrink | Balanced allocations: The heavily loaded case[END_REF] and applying Lemma 3.2 we obtain, since

x ρn ≥ 0 ( -α + α 2 ( 1 - 2 n )) n ∑ i=ρn+1 p i e -αx i (t) ≤ ( -α + α 2 ( 1 - 2 n )) (1 + ρ)n -1 n(n -1) n ∑ i=ρn+1 e -αx i (t) ≤ ( -α + α 2 ( 1 - 2 n )) 1 + ρ n ( Ψ(t) - ρn ∑ i=1 e -αx i (t) ) ≤ ( -α + α 2 ( 1 - 2 n )) (1 + ρ)(Ψ(t) -ρn) n .
Plugging this bound in inequality of Lemma 3.5, leads to

E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ ( -α + α 2 ( 1 - 2 n )) n ∑ i=1 p i e αx i + ( α n + α 2 n 2 ) Ψ(t) ≤ ( -α + α 2 ( 1 - 2 n )) (1 + ρ)(Ψ(t) -ρn) n + ( α n + α 2 n 2 ) Ψ(t) ≤ - α n [ ρ -α(1 + ρ) + α(1 + 2ρ) n ] Ψ(t) + ρα(1 + ρ) ( 1 -α ( 1 - 2 n )) ≤ - α n [ ρ -α(1 + ρ) + α(1 + 2ρ) n ] Ψ(t) + ρα(1 + ρ).
We complete the proof observing that E{Ψ(t) | x(t)} = Ψ(t). The second inequality is immediate.

Lemma 3.9 Let α, µ ∈ (0, 1/2) with µn ∈ N and µ ∈ (α/(1 + α), (1 -2α)/(1 -α)), let µ ′ ∈ (0, 1) with µ ′ n ∈ N and µ ′ ∈ (µ/(1 -µ), 1/(1 + α)) and let γ 1 ∈ (0, 1). If x (1-µ)n > 0 and E{Φ(t + 1) -Φ(t) | x(t)} ≥ - ( 1 -µ ′ (α + 1) ) αγ 1 n Φ(t) and Φ(t) ≥ λ 1 Ψ(t) then we have Γ(t) ≤ c 1 n,
where

c 1 = ( 1 + 1 λ 1 ) C 1 ( C 1 µλ 1 ) µ/((1-µ)µ ′ -µ) , C 1 = (1 -µ ′ ) (2 + α) (1 -γ 1 ) (1 -µ ′ (1 + α))
, and

λ 1 = 1 -µ -α(2 -µ) 2α .
The condition µ < (1 -2α)/(1 -α) is needed ta assure that constant λ 1 > 0. The value of λ 1 will be used in Theorem 3.11. The condition µ ′ > µ/(1 -µ) is needed to assure that the power involved in constant c 1 is positive.

Proof. See Appendix

Lemma 3.10 Let α, ρ ∈ (0, 1/2) with ρn ∈ N and ρ ∈ (α/(1 -α), 1/(1 + α)), let ρ ′ ∈ (ρ/(1 -ρ), (1 -2α)/(1 -α)) with ρ ′ n ∈ N and let γ 2 ∈ (0, 1).

If x ρn < 0 and E{Ψ(t

+ 1) -Ψ(t) | x(t)} ≥ - [ 1 -2α -ρ ′ (1 -α) ] αγ 2 n Ψ(t) and Ψ(t) ≥ λ 2 Φ(t) then
we have Γ(t) ≤ c 2 n, where

c 2 = ( 1 + 1 λ 2 ) C 2 ( C 2 ρλ 2 ) ρ/((1-ρ)ρ ′ -ρ) , C 2 = (1 -ρ ′ ) (2 -2α -ρ ′ (1 -α)) (1 -γ 2 ) (1 -2α -ρ ′ (1 -α))
, and

λ 2 = 1 -ρ(1 + α) 2α .
The condition ρ < 1/(1 + α) is needed ta assure that constant λ 2 > 0. The value of λ 2 will be used in Theorem 3.11. The condition ρ ′ > ρ/(1 -ρ) is needed to assure that the power involved in constant c 2 is positive.

Proof. See Appendix.

Theorem 3.11 Let α, µ, ρ ∈ (0, 1/2) with µn, ρn ∈ N, µ ∈ (α/(1 + α), (1 -2α)/(1 -α)) and ρ ∈ (α/(1-α), 1/(1+α)). Let µ ′ ∈ (µ/(1-µ), 1/(1+α)) with µ ′ n ∈ N and let ρ ′ ∈ (ρ/(1-ρ), (1-2α)/(1-α)) with ρ ′ n ∈ N. Let γ 1 , γ 2 ∈ (0, 1). We then have E{Γ(t + 1) | x(t)} ≤ ( 1 -c 4 α n ) Γ(t) + c 3 ,
where

c 4 = min { µ -α(1 -µ), ρ -α(1 + ρ), γ 1 ( 1 -µ ′ (α + 1) ) , α (1 -µ -α(2 -µ)) 1 -µ(1 -α) , γ 2 ( 1 -2α -ρ ′ (1 -α) ) , α (1 -ρ(1 + α)) 1 -ρ(1 -α) + 2α } and c 3 = max { α (1 + α + ρ(1 + ρ)) , α(1 -µ)(2 -µ), (α + c 4 )αc 1 , α + α 2 , (α + c 4 )αc 2 } ,
in which

c 1 = ( 1 + 1 λ 1 ) C 1 ( C 1 µλ 1 ) µ/((1-µ)µ ′ -µ) , C 1 = (1 -µ ′ ) (2 + α) (1 -γ 1 ) (1 -µ ′ (1 + α)) , λ 1 = 1 -µ -α(2 -µ) 2α
and

c 2 = ( 1 + 1 λ 2 ) C 2 ( C 2 ρλ 2 ) ρ/((1-ρ)ρ ′ -ρ) , C 2 = (1 -ρ ′ ) (2 -2α -ρ ′ (1 -α)) (1 -γ 2 ) (1 -2α -ρ ′ (1 -α)) , λ 2 = 1 -ρ(1 + α) 2α .
Proof. See Appendix.

We are now able to give a upper bound of the expected value of Γ(t).

Theorem 3.12 For all t ≥ 0, under the hypothesis of Theorem 3.11, we have E{Γ(t)} ≤ c 3 n/(αc 4 ).

Proof. We prove this result by induction. For t = 0, we have Γ(0) = 2n. Moreover, we have

c 3 ≥ α (1 + α + ρ(1 + ρ)) ≥ α and c 4 ≤ µ -α(1 -µ) ≤ µ ≤ 1/2,
which implies that c 3 /(αc 4 ) ≥ 2. We thus have E{Γ(0)} = 2n ≤ c 3 n/(αc 4 ). Suppose that the result is true for a fixed t ≥ 0. From Theorem 3.11, we have

E{Γ(t + 1)} = E {E{Γ(t + 1) | x(t)}} ≤ E {( 1 -c 4 α n ) Γ(t) + c 3 } ≤ ( 1 -c 4 α n ) c 3 αc 4 n + c 3 = c 3 αc 4 n.
which completes the proof.

Theorem 3.13 For all t ≥ 0 and σ > 0, under the hypothesis of Theorem 3.11, we have

P { Gap(t) ≥ 2(1 + σ) α ln (n) + 2 α ln ( c 3 2αc 4 )} ≤ 1 n σ
Proof. From Lemma 2.1 and Theorem 3.12, we have

Γ(t) ≥ 2e αGap(t)/2 and c 3 n αc 4 ≥ E{Γ(t)}. It follows that 2e αGap(t)/2 ≥ n σ c 3 n αc 4 =⇒ Γ(t) ≥ n σ c 3 n αc 4 =⇒ Γ(t) ≥ n σ E{Γ(t)}.
Using Markov inequality, we obtain

P { Gap(t) ≥ 2(σ + 1) α ln (n) + 2 α ln ( c 3 2αc 4 )} = P { 2e αGap(t)/2 ≥ n σ c 3 n αc 4 } ≤ P {Γ(t) ≥ n σ E{Γ(t)}} ≤ 1 n σ ,
which completes the proof.

The following corollary shows that at any time, and for any agent, its local counter approximates the global clock with high probability.

Corollary 3.14 For all t ≥ 0 and σ > 0, under the hypothesis of Theorem 3.11, we have

P { C (i) t - t n < 2(1 + σ) α ln (n) + 2 α ln ( c 3 2αc 4 ) , ∀i = 1, . . . , n } ≥ 1 - 1 n σ
Proof. By definition, we have

x i = C (i)
t -t/n, and since

x n ≤ 0 ≤ x 1 , we have |x i | ≤ x 1 -x n = Gap(t). It follows, from Theorem 3.13, that P { C (i) t - t n ≥ 2(1 + σ) α ln (n) + 2 α ln ( c 3 2αc 4 ) , ∀i = 1, . . . , n } ≤ P { Gap(t) ≥ 2(1 + σ) α ln (n) + 2 α ln ( c 3 2αc 4 )} ≤ 1 n σ
which completes the proof.

Evaluation of the constants

This section is devoted to the evaluation of constants a and b of Relation ( 1) and, to compare them with the ones that we can derive from the analysis of Alistarh et al. [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]. From Theorem 3.13, we have

a = 2 α and b = 2 α ln ( c 3 2αc 4
)

,

where c 3 and c 4 are given by Theorem 3.11. First of all, note that constraints given in Theorem 3.11 imply the following inequality: ρ/(1 -ρ) < (1 -2α)/(1 -α), that is, ρ ≤ (1 -2α)/(2 -3α), which combined with ρ ≥ α/(1 -α), leads to α ≤ (5 -√ 5)/10 ≈ 0.276. For a fixed value of α, we have to determine the values of parameters µ, ρ, µ ′ , ρ ′ , γ 1 , γ 2 that minimize constant b. This is achieved by applying a simple Monte-Carlo algorithm. Figure 1 shows several optimal values of the constants a and b, used in Theorem 3. [START_REF] Raab | Balls into bins" -a simple and tight analysis[END_REF] Let us now evaluate constants a and b obtained in the paper of Alistarh et al. [START_REF] Alistarh | The power of choice in priority scheduling[END_REF]. Note that the goal of their work was not necessarily focused on the optimization of a and b constants. Nevertheless, as we will see, the evaluation of a and b constants is an important motivation of our work. From Relations (1) and ( 2) of [START_REF] Alistarh | The power of choice in priority scheduling[END_REF] and as β = 1, we get 0 < δ ≤ ε = 1/16 and thus we obtain, for γ > 0 and c ≥ 2,

1 + γ + cα(1 + γ) 2 1 -γ -cα(1 + γ) 2 ≤ 17 16 , which gives, α ≤ 1 33c(1 + γ) 2 - 1 c(1 + γ) 2 ≤ 1 33c(1 + γ) 2 ≤ 1 66
.

Considering the difference between the lower bound and the upper bound of the inequality following [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF], we obtain exp

( αB n ( 3 - 1 1 -λ )) ≤ 16λC(ε) ε ,
which can also be written as exp

( αB (1 -λ)n ) ≤ ( 16λC(ε) ε ) 1/(2-3λ) .
Using the last inequality obtained in the proof of Lemma 4.8, we get

Γ(t) ≤ 4 + ε ε λnC(ε) exp ( αB (1 -λ)n ) ≤ 4 + ε ε λnC(ε) ( 16λC(ε) ε ) 1/(2-3λ) .
Using this result, we obtain from Lemma 4.11, E{Γ(t)} ≤ 4Cn/(αε), where

C = 4 + ε ε λC(ε) ( 16λC(ε) ε ) 1/(2-3λ) , C(ε) = (1 + δ)/λ -1 + 3ε 3ε -ε/3 and α = α(1 -γ -cα(1 + γ) 2 ).
Following the same ideas we used to prove Theorem 3.13, we get

a = 2 α and b = 2 α ln ( 2C αε
) .

Since α ≤ 1/66, we have a ≥ 132. Moreover, since 0 ≤ δ ≤ ε = 1/16, λ = 2/3 -1/54 = 35/54, γ > 0 and c ≥ 2, we obtain

C(ε) = (1 + δ)/λ -1 + 3ε 3ε -ε/3 ≥ 1/λ -1 + 3ε 3ε -ε/3 = 1227 280
which leads to

C = 4 + ε ε λC(ε) ( 16λC(ε) ε ) 1/(2-3λ) ≥ 26585 144 ( 6544 9
) 18 .

Regarding α, we have

α = α(1 -γ -cα(1 + γ) 2 ) ≤ α ≤ 1/66. Therefore, we have b = 2 α ln ( 2C αε
) ≥ 132 ln ( 1169740 3 ( 6544 9
) 18 )

≥ 17354.

It follows that constants a and b obtained from [START_REF] Alistarh | The power of choice in priority scheduling[END_REF] satisfy a ≥ 132 and b ≥ 17354, which are at least two orders of magnitude larger than the ones we derived (see Figure 1).

Simulations

We complete this paper by giving a summary of the experiments we have carried out to illustrate the performances of our protocol. Recall that n is the number of nodes in the system, and T = t/n is the total number of interactions divided by n, which is often called the parallel time. We have conducted two types of experiments, the first one illustrates the expected proportion of nodes Y T (n, k) whose counter is equal to T + k at time nT , for different values of n and k. More precisely, Y T (n, k) is defined by

Y T (n, k) = 1 n n ∑ i=1 1 {C (i) nT =T +k} .
We show in Figure 2 the expected value of Y T (n, k), for n = 1000 and k = -2, -1, 0, 1, as a function of the parallel time T . These results have been obtained after running 10, 000 independent experiments. Figure 2 shows that the expected value of Y T (n, k) seems to converge when T goes to infinity, and this convergence is reached very quickly. Note that for other values of k, proportions of nodes are too close to 0 to be depicted, as shown in Table 1. Table 1 shows the expected proportion of nodes Y T (n, k) 11 The second experiment illustrates the gaps (i.e., the maximal, average, and minimal) for different values of the size n of the system. Let B = 2 × 10 9 be the total number of interactions considered. The maximal gap is computed as max 100n≤t≤B Gap(t), the minimal one is given by min 100n≤t≤B Gap(t), and the average gap is given by 1 B -100n

k = 1 k = 0 k = -1 k = -2
B-1 ∑ t=100n Gap(t).
Figure 3 shows respectively the minimal, average and maximal gap in a system of size n over the interval [100n, B] of interactions. As one may expect, the logarithmic progression of the Gap is clearly shown.

Conclusion

In this article we have gone a step further in the study of the two-choice paradigm by providing an accurate analysis of the gap problem. An important application of this study would be the improvement of leaderless population protocols. Indeed, we have shown in this paper that agents can construct a global clock by guaranteeing that the values of all agent counters are concentrated according to Relation (1), and thus can locally use this global clock to determine the instants at which some specific actions need to be triggered, or the instants from which all the agents of the system have converged to a given state. In the former case, this would allow agents to solve more complex problems by triggering a series of population protocols, whereas in the latter case this would allow agents to determine the instant from which all the agents have successfully computed a given feature of the population. The construction of efficient leaderless population protocols inspired from this orchestration is left for future work. Lemma 3.2 Let u = (u k ) k≥1 and v = (v k ) k≥1 be two monotonic sequences of real numbers and let m n be the sequence of mean values of sequence v defined, for n ≥ 1, by

m n = 1 n n ∑ k=1 v k .
If the sequences u and v are both non-decreasing or both non-increasing then we have

n ∑ k=1 u k v k ≥ m n n ∑ k=1 u k .
If one of these two sequences is non-increasing and the other is non-decreasing then we have

n ∑ k=1 u k v k ≤ m n n ∑ k=1 u k .
Proof of Lemma 3.2. Suppose that the two sequences are non-decreasing. Let h be the index such

that v h ≤ m n ≤ v h+1 . Since ∑ n k=1 (v k -m n ) = 0, we have - h ∑ k=1 (v k -m n ) = n ∑ k=h+1 (v k -m n ) ≥ 0 and thus n ∑ k=1 u k v k -m n n ∑ k=1 u k = n ∑ k=1 u k (v k -m n ) = h ∑ k=1 u k (v k -m n ) + n ∑ k=h+1 u k (v k -m n ) ≥ u h h ∑ k=1 (v k -m n ) + u h+1 n ∑ k=h+1 (v k -m n ) = (u h+1 -u h ) n ∑ k=h+1 (v k -m n ) ≥ 0
By multiplying both sequences by -1, we get the case where both sequences are non-increasing case. The last case is obtained by multiplying only one sequence by -1.

The following technical lemma is needed in the proofs of Lemmas 3.9 and 3.10.

Lemma A.1 Let a, b, c, d > 0. If ad -bc ≥ 0 then a + b c + d ≤ a c . If ad -bc ≤ 0 and c -d > 0 then a -b c -d ≤ a c . Proof. If ad -bc ≥ 0 then a + b c + d - a c = ac + bc -ac -ad (c + d)c = bc -ad (c + d)c ≤ 0. If ad -bc ≤ 0 and c -d > 0 then a -b c -d - a c = ac -bc -ac + ad (c -d)c = ad -bc (c -d)c ≤ 0,
which completes the proof.

This leads to

Φ(t) ≤ 2 + α + 1 -α(2 + µ ′ ) n -1 - 1 -µ ′ -2α n(n -1) (1 -γ 1 ) ( 1 -µ ′ (α + 1) + 1 -µ ′ n ) Φ >µ ′ n ≤ (1 -µ ′ ) ( 2 + α + 1 -α(2 + µ ′ ) n -1 - 1 -µ ′ -2α n(n -1) ) (1 -γ 1 ) ( 1 -µ ′ (α + 1) - 1 -µ ′ n ) ne αB(t)/(µ ′ n) .
We now make use of Lemma A1. Let us define

a = 2 + α, b = 1 -α(2 + µ ′ ) n -1 - 1 -µ ′ -2α n(n -1) , c = 1 -µ ′ (α + 1) and d = 1 -µ ′ n . We have a, c, d > 0. If b ≤ 0 then we clearly have a + b c + d ≤ a c
. If b > 0 we obtain, after some algebra,

(ad -bc)n(n -1) = [(n -1)(1 + 3α) -µ ′ ](1 -µ ′ ) + (n -1)αµ ′ (2 -µ ′ -2α -αµ ′ ) + µ ′ α(1 -αµ ′ ). Since α < 1/2, the condition µ ′ < 1/(1 + α) implies that µ ′ < 2(1 -α)/(1 + α) which in turn implies that 2 -µ ′ -2α -αµ ′ > 0.
We deduce that ad -bc > 0 and using Lemma A1, we obtain

a + b c + d ≤ a c . This leads to Φ(t) ≤ n(1 -µ ′ ) (2 + α) (1 -γ 1 ) (1 -µ ′ (α + 1)) e αB(t)/(µ ′ n) . Introducing the notation C 1 = (1 -µ ′ ) (2 + α) (1 -γ 1 ) ( 1 -µ ′ (α + 1) ) , we can write Φ ≤ C 1 ne αB(t)/(µ ′ n) .
The exponential function being convex, the Jensen's inequality gives

Ψ(t) ≥ Ψ >(1-µ)n (t) = n ∑ i=(1-µ)n+1 e -αx i (t) ≥ µn exp ( - α ∑ n i=(1-µ)n+1 x i (t) µn ) .
Consider the sum ∑ n i=(1-µ)n+1 x i (t) and recall that the sequence (x i (t)) i is non increasing. Since x (1-µ)n (t) > 0, this sum contains all the negative x i (t) whose sum is equal to -B(t). Let r be the number of positive x i (t) in this sum. Noting that r ∈ {0, . . . , µn -1}, we have, using [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF],

n ∑ i=(1-µ)n+1 x i (t) = -B(t) + (1-µ)n+r ∑ i=(1-µ)n+1 x i (t) ≤ -B(t) + B(t) (1-µ)n+r ∑ i=(1-µ)n+1 1 i ≤ -B(t) + rB(t) (1 -µ)n + r .
The function f defined, for r ∈ [0, µn], by f (r) = rB/((1 -µ)n + r) being non decreasing, we have

rB(t) (1 -µ)n + r = f (r) ≤ f (µn) = µB(t), which leads to n ∑ i=(1-µ)n+1 x i (t) ≤ -B(t) + µB(t) = -(1 -µ)B(t)
and applying Lemma 3.2 we obtain

E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ m n ( -α + α 2 ( 1 - 2 n )) Ψ >(1-ρ ′ )n (t) + ( 1 + α n ) α n Ψ >(1-ρ ′ )n (t) + ( 1 + α n ) α n Ψ ≤(1-ρ ′ )n (t) ≤ [ (2 -ρ ′ ) ( -1 + α ( 1 - 2 n )) + 1 + α n ] α n Ψ >(1-ρ ′ )n (t) + ( 1 + α n ) α n Ψ ≤(1-ρ ′ )n (t) = - [ 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ] α n Ψ >(1-ρ ′ )n (t) + ( 1 + α n ) α n Ψ ≤(1-ρ ′ )n (t).
Using the fact that Ψ >(1-ρ ′ )n (t) = Ψ(t) -Ψ ≤(1-ρ ′ )n (t), we get

E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ - [ 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ] α n Ψ(t) + [ 2 -2α -ρ ′ (1 -α) + α(4 -2ρ ′ ) n ] α n Ψ ≤(1-ρ ′ )n (t).
Using the second hypothesis, we have

E{Ψ(t + 1) -Ψ(t) | x(t)} ≥ - [ 1 -2α -ρ ′ (1 -α) ] αγ 2 n Ψ(t) ≥ - [ 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ] αγ 2 n Ψ(t)
and thus, we obtain

[ 2 -2α -ρ ′ (1 -α) + α(4 -2ρ ′ ) n ] α n Ψ ≤(1-ρ ′ )n (t) ≥ (1 -γ 2 ) [ 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ] α n Ψ(t).
Note that the condition ρ ′ < (1 -2α)/(1 -α) and α < 1/2 implies that 1 -2α -ρ ′ (1 -α) > 0.

Let us introduce the notation B(t) = ∑ n i=1 max(0, x i (t)). The sequence (x i (t)) i being non-increasing, we have, for every ℓ = 1, . . . , n,

-B(t) ≤ n ∑ i=ℓ+1 x i (t) ≤ (n -ℓ)x ℓ (t). (11)
It follows in particular that we have x (1-ρ ′ )n (t) ≥ -B(t)/(ρ ′ n) and so

Ψ ≤(1-ρ ′ )n (t) = (1-ρ ′ )n ∑ i=1 e -αx i (t) ≤ (1 -ρ ′ )ne -αx (1-ρ ′ )n (t) ≤ (1 -ρ ′ )ne αB(t)/(ρ ′ n) .
This leads to

Ψ(t) ≤ [ 2 -2α -ρ ′ (1 -α) + α(4 -2ρ ′ ) n ] (1 -γ 2 ) [ 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ] Ψ ≤(1-ρ ′ )n ≤ (1 -ρ ′ ) [ 2 -2α -ρ ′ (1 -α) + α(4 -2ρ ′ ) n ] (1 -γ 2 ) [ 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ] ne αB/(ρ ′ n) .
We now make use of Lemma A1. Let us define a = 1, b = α/n, c = 1 -2α -ρ ′ (1 -α) and d = α(3 -2ρ ′ )/n. We have a, b, c, d > 0 and ad -bc = α(2 -ρ ′ )(1 + α)/n ≥ 0, so using Lemma A1, we

obtain a + b c + d ≤ a c , that is 2 -2α -ρ ′ (1 -α) + α(4 -2ρ ′ ) n 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n = 1 + 1 + α n 1 -2α -ρ ′ (1 -α) + α(3 -2ρ ′ ) n ≤ 1 + 1 1 -2α -ρ ′ (1 -α) = 2 -2α -ρ ′ (1 -α) 1 -2α -ρ ′ (1 -α) .
This leads to

Ψ(t) ≤ (1 -ρ ′ ) (2 -2α -ρ ′ (1 -α)) (1 -γ 2 ) (1 -2α -ρ ′ (1 -α)) ne αB(t)/(µ ′ n) .
Introducing the notation ) .

C 2 = (1 -ρ ′ ) ( 2 -2α -ρ ′ (1 -α) ) (1 -γ 2 ) ( 1 -2α -ρ ′ (1 -α) ) ,
Consider the sum ∑ ρn i=1 x i (t) and recall that the sequence (x i (t)) i is non increasing. Since x ρn (t) < 0, this sum contains all the positive x i (t) whose sum is equal to B(t) and at least one negative x i (t). Let r be the number of negative x i (t) in this sum, Noting that r ∈ {1, . . . , ρn -1}, we have, using [START_REF] Peres | The (1+β)-choice process and weighted balls into bins[END_REF] )) = exp

( αB(t) ρ ′ n ( (1 -ρ)ρ ′ -ρ ρ
)) ,

Lemma 3 . 2

 32 where c is the unique positive solution to equation e c -1 -c -c 2 = 0. The value of c satisfies 1.79 < c < 1.8. Let u = (u k ) k≥1 and v = (v k ) k≥1 be two monotonic sequences of real numbers and let m n be the sequence of mean values of sequence v defined, for n ≥ 1, by

Figure 1 :

 1 Figure 1: Optimal values of a and b in function of α

Figure 2 :

 2 Figure 2: Expected proportion Y T (n, k) of nodes as a function of parallel time T , for n = 1000, and k = -2, -1, 0, 1, from bottom to the top.

Figure 3 :

 3 Figure 3: Minimum, average and maximun gap as a function of n.

  , and computed for several values of α.

	α	0.17	0.18	0.19 0.20 0.21 0.22 0.23 0.24 0.25 0.26 0.27
	a = 2/α	11.77 11.12 10.53 10 9.53 9.10 8.70 8.34	8	7.70 7.41
	b = (2/α) log(c3/(2αc 4 ))	59	63	68	74	82	93	109 134 179 281 739

Table 1 :

 1 Expectation of Y 50 (n, k) from number of nodes n and shift k

	k H H H H H H n -13	10 3 0.0	10 4 0.0	10 5 0.0	10 6 1.4E-9	10 7 1.42E-9
	-12	0.0	2.0E-8	8.0E-9	9.0E-9	6.14E-9
	-11	2.0E-7	4.0E-8	2.2E-8	2.8E-8	3.048E-8
	-10	2.0E-7	8.0E-8	1.88E-7	1.436E-7	1.4814E-7
	-9	4.0E-7	8.0E-7	7.7E-7	7.438E-7	7.2784E-7
	-8	3.0E-6	3.6E-6	3.586E-6	3.48E-6	3.6029E-6
	-7	1.42E-5	1.8E-5	1.8222E-5 1.7767E-5	1.7758E-5
	-6	8.98E-5	8.602E-5 8.7176E-5 8.7372E-5 8.72753E-5
	-5	4.372E-4 4.2706E-4 4.2957E-4 4.2901E-4 4.29349E-4
	-4	0.0021144 0.0021023 0.0021071 0.0021092	0.0021086
	-3	0.0102474 0.0102890 0.0102777 0.0102800	0.0102810
	-2	0.0481626 0.0483366 0.0483382 0.0483465	0.0483437
	-1	0.1930704 0.1932864 0.1933165 0.1933143	0.1933182
	0	0.4389352 0.4380932 0.4380715 0.4380374	0.4380346
	1	0.2824746 0.2827344 0.2826797 0.2827057	0.2827070
	2	0.0243744 0.0245499 0.0245973 0.0245953	0.0245949
	3	7.6E-5	7.224E-5 7.2248E-5 7.27752E-5 7.27974E-5
	4	0.0	0.0	0.0	4.0E-10	3.6E-10

* This work was partially funded by the French ANR project SocioPlug (ANR-13-INFR-0003), and by the DeSceNt project granted by the Labex CominLabs excellence laboratory (ANR-10-LABX-07-01)

Appendix

This appendix is devoted to the proofs of the Lemmas of the previous sections. These proofs need the following technical results. Lemma 3.1 For all x ∈ R, we have 1 + x ≤ e x . For all x ∈ (-∞, c], we have e x ≤ 1 + x + x 2 , where c is the unique positive solution to equation e c -1 -c -c 2 = 0. The value of c satisfies 1.79 < c < 1.8.

Proof of Lemma 3.1. The first inequality follows from the study of function e x -1 -x. The second inequality can be proved in the same way by studying the function e x -1 -x -x 2 and its derivative e x -1 -2x. It is easily checked that c ∈ (1.79, 1.8).

We suppose in the following lemma that the main hypothesis of Lemma 3.7 is not satisfied, i.e. we suppose that we have x (1-µ)n > 0. In order to simplify the writing, we introduce the following notation, for all λ ∈ (0, 1) such that λn ∈ N, (t) , and Ψ >λn (t) = n ∑ i=λn+1 e -αx i (t) . Lemma 3.9 Let α, µ ∈ (0, 1/2) with µn ∈ N and µ ∈ (α/(1 + α), (1 -2α)/(1 -α)), let µ ′ ∈ (0, 1) with µ ′ n ∈ N and µ ′ ∈ (µ/(1 -µ), 1/(1 + α)) and let γ 1 ∈ (0, 1).

If

where

, and

The condition µ < (1 -2α)/(1 -α) is needed ta assure that constant λ 1 > 0. The value of λ 1 will be used in Theorem 3.11. The condition µ ′ > µ/(1 -µ) is needed to assure that the power involved in constant c 1 is positive.

Proof.

Since -(α/n -α 2 /n 2 ) ≤ 0, we have, using Lemma 3.3

The sequence ( e αx i (t) ) i is a non-increasing sequence and the sequence (p i ) i is an non-decreasing sequence, so setting successively

Using the fact that Φ ≤µ ′ n (t) = Φ(t) -Φ >µ ′ n (t), we get

Using now the second hypothesis which satisfies

we get

It follows in particular that we have

and so, we get

The hypothesis Φ(t) ≥ λ 1 Ψ(t) gives

which in turn gives

that is

We finally arrive to

We suppose in the following lemma that the main hypothesis of Lemma 3.8 is not satisfied, i.e. we suppose that we have x ρn < 0.

we have Γ(t) ≤ c 2 n, where

, and

The condition ρ < 1/(1 + α) is needed ta assure that constant λ 2 > 0. The value of λ 2 will be used in Theorem 3.11. The condition ρ ′ > ρ/(1 -ρ) is needed to assure that the power involved in constant c 2 is positive.

Proof. Using lemma 3.5 and since -α

The sequence ((

i is a non-increasing sequence and the sequence (p i ) i is an non-decreasing sequence, so setting

We finally arrive to

where

in which

and

Proof of Theorem 3.11. The proof proceeds by the analysis of the three following cases.

• Case 1 :

Case 1 : Suppose that x ρn ≥ 0 and x (1-µ)n ≤ 0. We can then use Lemmas 3.7 and 3.8. By adding inequalities ( 9) and ( 10), we obtain

Case 2 : Suppose that x (1-µ)n > 0. We then consider the three following subcases. 22

Case 2.1 : Suppose that

We can then apply Lemma 3.9, which gives Γ(t) ≤ c 1 n. By adding the inequalities obtained in Corollaries 3.4 et 3.6, we get

and thus, using the fact that c 1 ≥ Γ(t)/n,

Since µ, ρ ∈ (0, 1/2), we have ρ < 1 -µ. The sequence (x i (t)) i being non increasing, we have x ρn (t) ≥ x (1-µ)n (t) > 0. We can thus apply Lemma 3.8. Adding the previous inequality with the one in Lemma 3.8 leads to

which gives

. We use here Corollary 3.4 and Lemma 3.8 in which we set ρ = 1 -µ. We obtain, after some algebra,

that is

Case 3 : Suppose that x ρn < 0. We then consider the three following subcases.

• Case 3.1 :

• Case 3.3 : Ψ(t) < λ 2 Φ(t).

Case 3.1 : Suppose that

We can then apply Lemma 3.10, which gives Γ(t) ≤ c 2 n. By adding the inequalities obtained in Corollaries 3.4 et 3.6, we get

and thus, using the fact that c 2 ≥ Γ(t)/n,

Since µ, ρ ∈ (0, 1/2), we have ρ < 1 -µ. The sequence (x i (t)) i being non increasing, we have x (1-µ)n (t) ≤ x ρn (t) < 0. We can thus apply Lemma 3.7. Adding the previous inequality with the one in Lemma 3.7 leads to

which gives

. We use here Corollary 3.4 and Lemma 3.7 in which we set µ = 1 -ρ. We obtain, after some algebra, E{Γ(t + 1) -Γ(t) | x(t)} = E{Φ(t + 1) -Φ(t) | x(t)} + E{Ψ(t + 1) -Ψ(t) | x(t)} ≤ -

Note that for ρ ∈ (0, 1/2), we have (1 -ρ)/(3 -2ρ) > 1/2 which implies that α < (1 -ρ)/(3 -2ρ) which is equivalent to 1 -ρ(1 -3α) -2α > 0. This gives

that is

which completes the proof.


Lyudmila S Shumilovskikh

Astrid Ferrer

Frank Schlütz

Non-pollen palynomorphs notes: 2. Holocene record of Megalohypha aqua-dulces, its relation to the fossil form genus Fusiformisporites and association with lignicolous freshwater fungi

Keywords:

The first Holocene record of the freshwater ascomycete Megalohypha aqua-dulces from the sediment core Kongor (NE Iran) is presented here. Based on the similarity of the spore morphology with the fossil form genus Fusiformisporites, we establish a link between extant and fossil taxa. Comparative analysis of morphological characteristics of fossil spores of Fusiformisporites indicates that several different fungal groups might be included in this form genus. At least five species of Fusiformisporites share similar morphology with spores of Megalohypha aqua-dulces: Fusiformisporites annafrancescae, Fusiformisporites crabbii, Fusiformisporites keralensis, Fusiformisporites paucistriatus, and Fusiformisporites pseudocrabbii. Based on Fusiformisporites, the evolution of Megalohypha aqua-dulces can be traced to the late Cretaceous, corresponding with diversification of the flowering plants and pointing to a co-evolution of both groups. Megalohypha aqua-dulces has a tropical to subtropical distribution but also occurs in the semi-arid steppe environments of Kongor together with other freshwater fungal genera such as Xylomyces, Dictyosporium, and Sporoschisma, which spores we describe here. The ecological requirements of Megalohypha indicate that its spores can be used for the palaeoecological sign of dead submerged wood as well as of tropical to subtropical conditions.

Introduction

Morphologically distinctive fungal spores present in the geological record provide valuable information about a wide variety of environmental conditions, including climate, hydrological conditions, fire and erosion history, vegetation type, and organismal interactions (e.g. [START_REF] Elsik | Microscopic fungal remains and cenozoic palynostratigraphy[END_REF][START_REF] Sherwood-Pike | Freshwater fungi: fossil record and paleoecological potential[END_REF][START_REF] Pirozynski | Methods in Quaternary ecology #9[END_REF][START_REF] Van Geel | Fossil ascomycetes in Quaternary deposits[END_REF][START_REF] Taylor | Fossil fungi[END_REF]. The description of fossil fungal spores is usually carried out based on fossil material, which rarely provides identification to extant taxa [START_REF] Elsik | Microscopic fungal remains and cenozoic palynostratigraphy[END_REF][START_REF] Jansonius | Redescription of some fossil fungal spores[END_REF]. Studies on the relationship between extant and fossil taxa however deliver important information for geological and mycological research by combining geological records with known fungal ecology. For example, investigation of the monotypic genus Potamomyces indicate that it likely contains several species [START_REF] Schlütz | On the relation of Potamomyces armatisporus to the fossil form-type Mediaverrunites and its taxonomical and ecological implications[END_REF][START_REF] Nuñez Otaño | The occurrence of Potamomyces palmarensis sp. nov. in the Late Holocene of El Palmar National Park (Colón, Entre Ríos, Argentina) and transfer of fossil species of Mediaverrunites to Potamomyces[END_REF], or in the case of Caryospora callicarpa led to the discovery of species thought to be extinct [START_REF] Hawksworth | Caryospora callicarpa: found in archaeological and modern preparationsbut not collected since 1865[END_REF]. Further connections of fossil fungal spores to recent species are required for a deeper understanding of the history, evolution, ecology and (palaeo)geography of fungal taxa.

During palynological investigations of a sediment core from Kongor (NE Iran), covering the last 6000 years [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF], fungal spores of Megalohypha aqua-dulces Ferrer et Shearer were documented (Plate I) and identified using mycological literature [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF]. These spores share similar characteristics to additional fossilised spores from geological records described as Fusiformisporites [START_REF] Rouse | Plant microfossils from Burrard Formation of Western British Columbia[END_REF] Continuing our series of "non-pollen palynomorphs notes" [START_REF] Schlütz | Non-pollen palynomorphs notes: 1. Type HdV-368 (Podospora-type), description of associated species, and the first key to related spore types[END_REF], in this paper we provide the first Holocene record of the extant species Megalohypha aqua-dulces and discuss its relation to the fossil form genus Fusiformisporites.

Material and methods

The Kongor core was obtained from the temporary lake Kongor, located in the Artemisia-steppe of the eastern Gorgan Plain, NE Iran. Samples from the core were treated with standard palynological laboratory procedures and studied for pollen and non-pollen palynomorphs including microscopic plant, animal and fungal remains (details in [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF]. For the purpose of this paper we present an abbreviated version of the palynological diagram with freshwater fungi, arboreal pollen and tree and shrub macroremains (Fig. 1). The description of the Megalohypha aqua-dulces spores (Plate I) and of the spores of other freshwater fungi (Plate III) from the sediment core Kongor follows the scheme of [START_REF] Elsik | Annotated glossary of fungal palynomorphs[END_REF] with an abbreviation KNG (Kongor) for the first described types. Spore measurements were carried out on 1000× magnification.

The samples from Panama were collected from freshwater habitats at the Soberania National Park, which support lowland tropical forest. Samples of submerged partially decomposed wood were incubated in the laboratory in plastic boxes containing moistened paper towels at room temperature and examined with a dissecting microscope periodically over 12 months. Fungi were removed from the substrate and placed in a drop of distilled water on a glass slide. Measurements and photographs of the spores and fruiting bodies were made in material mounted in distilled water (Plate II; [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF].

Results

Spore morphology of Megalohypha aqua-dulces

Spores of Megalohypha aqua-dulces from the sediment core Kongor (KNG 62; Plate I): spores are fusiform, dark reddish-brown, dicellate, 47-60 × 21-27 μm (average = 54.4 × 23.4 μm, SD = 4.5 × 1.7 μm, n = 10), inaperturate, slightly constricted at the septum, wall thickness 1-1.5 μm, up to 3 μm at apices. The axis is straight, 2 symmetrical cells are separated by a septum 2-3 μm thick. The sculpture is longitudinally striate with 5-7 ridges exposed on each flattened sector. The striate pattern merges to a coarse reticulum at the apices.

The morphology corresponds to the original description of spores of the extant fungus Megalohypha aqua-dulces [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF]: ascospores 40-55 × 19-22 μm (mean = 48.3 × 18.8 μm, SD = 2.8 × 0.91 μm, n = 30), ellipsoidal, acutely tapered at apices, brown to dark brown, 1-septate, septum appearing as a dark band, both cells of equal shape and size, rough walled with longitudinal sulcate striations lacking appendages or a gelatinous sheath (Plate II).

In addition, the spores from Kongor resemble spores of the fossil form genus Fusiformisporites Rouse, 1962 with holotype Fusiformisporites crabbii Rouse, 1962 (Kalgutkar andJansonius, 2000): spores are distinctly fusiform in outline. The unit is split into two equal halves by an equatorial wall that appears to be continuous, thus completely dividing the unit. Longitudinal grooves spread out along the wall from either pole like a spindle; some reach the equator, others stop short of it. Only occasionally is a groove continuous across the dividing wall. The wall is moderately thick, about 3 μm. Ornamentation levigate. Size range 20-100 μm. Size of Fusiformisporites crabbii is 45-52 μm [START_REF] Rouse | Plant microfossils from Burrard Formation of Western British Columbia[END_REF].

According to [START_REF] Kalgutkar | Synopsis of fossil fungal spores, mycelia and fructifications[END_REF], Fusiformisporites includes forms with less obvious parallel ornamentation elements (striations) (Table 1). The authors place it taxonomically into Fungi Imperfecti, Didimosporae.

Records of freshwater fungi in Kongor

In the Kongor sediment core, Megalohypha aqua-dulces occurs together with freshwater lignicolous fungi such as Sporoschisma saccardoi-type, Dictyosporium heptasporum, Dictyosporium digitatum, Zopfiella cf. submersa, and Xylomyces chlamydosporus-type (Fig. 1). Arboreal pollen varies between 5 and 20% throughout the record. Macroremains of trees and shrubs, including seeds, epidermis and wood, occur in the upper metre of the core.

Below we provide a description of the spores of freshwater fungi from the Kongor site.

Dictyosporium digitatum (KNG 27b; Plate III: 4-6) Conidia are 58-62 × 28-32 μm in size, reddish-brown, multiseptate, composed of 6-7 parallel arms, closely branched from the terminal cell, flattened in one plane. The wall is smooth, about 1 μm thick. The spore morphology resembles Dictyosporium digitatum Chen, Hwang, Tzean, which is commonly found on submerged dead wood in Australia, Brunei Darussalam, Hong Kong, Seychelles, Taiwan, and Thailand [START_REF] Goh | A revision of the genus Dictyosporium, with descriptions of three new species[END_REF]. In Kongor, five spores were found from the Middle and Late Holocene (Fig. 1; [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF].

Dictyosporium heptasporum (HdV 1053 by [START_REF] Van Geel | Diversity and ecology of tropical African fungal spores from a 25,000-year palaeoenvironmental record in southeastern Kenya[END_REF]; Plate III: 1-3) Conidia are 62-68 × 22-26 μm in size, with 7 parallel arms, branched from the terminal cell in form of a cylinder, apices of arms are incurved. The spore morphology resembles Dictyosporium heptasporum with conidia broad ellipsoidal, 42-71 × 21-25 μm, branched, composed of ca. 7 rows of cells [START_REF] Damon | Type studies in Dyctiosporium, Speira, and Cattanea[END_REF]. [START_REF] Van Geel | Diversity and ecology of tropical African fungal spores from a 25,000-year palaeoenvironmental record in southeastern Kenya[END_REF] described type HdV 1053 from Lake Challa in Africa and identified them as Dictyosporium cf. heptasporum (Garov.) Damon. Two species of Dictyosporium have similar size and cylindrical morphology of conidia: D. heptasporum and Dictyosporium cocophilum [START_REF] Goh | A revision of the genus Dictyosporium, with descriptions of three new species[END_REF]. However, the apex of the arms is straight by the latter species. Therefore, we identified our specimen as D. heptasporum. Dictyosporium heptasporum has been observed on dead wood and submerged wood in Australia, Belize, Brunei Darussalam, Cuba, Europe, Hong Kong, India, Ecuador, Mexico, Peru, Taiwan, Tanzania, Thailand, USA [START_REF] Goh | A revision of the genus Dictyosporium, with descriptions of three new species[END_REF]. Subfossil finds are known from the Late Holocene from Lake Challa (Africa, [START_REF] Van Geel | Diversity and ecology of tropical African fungal spores from a 25,000-year palaeoenvironmental record in southeastern Kenya[END_REF] and the Middle and Late Holocene from Kongor (NE Iran, [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF]. Spores of another Plate II. Megalohypha aqua-dulces (1-2) grown in culture (Holotype AF005-2) and (3-6) collected from wood (Holotype AF005-1): 1-2: stalked ascomata, 3: longitudinal section through ascoma, 4: surface of ascospores with coarse reticulum at apices, 5: longitude section through ascospores, 6: surface of ascospores with sulcate striations. Further details in [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF]. species, Dictyosporium australiense, have been documented from Holocene peat sediments from Germany [START_REF] Shumilovskikh | The development of the raised bog "Borsteler Moor" (Lower Saxony, Germany) based on non-pollen palynomorph data[END_REF].

Sporoschisma saccardoi-type (UG 1002 by [START_REF] Gelorini | Modern non-pollen palynomorphs from East African lake sediments[END_REF]Plate III: 13-15) Conidia are 45-50 × 15-17 μm in size, composed of 4 to 6 cells with dark central and hyaline short apical cells, subtruncate at both ends; the spore is slightly constricted at septa, with a smooth wall 1-2 μm thick. Inner dark septa 3-4 μm thick, distal septa 1-1.5 μm. Central cells are normally equal but sometimes unequal (compare Plate III: 13 and 14). Some spores were found within the conidiophore, showing production of 5 and 3-septate spores by the same fungus specimen (Plate III: 15). [START_REF] Gelorini | Modern non-pollen palynomorphs from East African lake sediments[END_REF] associated the type UG 1002 with Sporoschisma spp. possibly with Sporoschisma saccardoi. In addition, at least Sporoschisma nigroseptatum has similar morphology (Goh et al., 1997b) and may be another Sporoschisma species, therefore here the Sporoschisma saccardoi-type is erected. Both species have been observed on submerged dead wood from Australia, Brunei Darussalam, Ecuador, Europe, Hong Kong, Indonesia, Malaysia, Peru, South Africa, Taiwan (Goh et al., 1997b). Subfossil spore finds are known from African modern lake sediments [START_REF] Gelorini | Modern non-pollen palynomorphs from East African lake sediments[END_REF], Holocene sediments from NE Iran [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF] and terrestrial surface samples from Nepal (Shumilovskikh, unpubl.). [START_REF] Prager | Non-pollen palynomorphs from modern Alder carrs and their potential for interpreting microfossil data from peat[END_REF] affiliated EMA 12 to Sporoschisma or Chalara or hyphae. Morphologically EMA 12 differs from conidia of Sporoschisma saccardoi-type, and it might be a part of hyphae.

Xylomyces chlamydosporus-type (KNG 7; Plate III: 16-17) Conidia are 145-255 × 35-40 μm in size, fusiform, straight or slightly curved, dark-brown with pale end cells. Spores have 6-14 septa, 2-5 μm thick. Spores are constricted at septa. The wall is 2-4 μm thick with scarce irregular longitudinal ornamentation (rugulate to coarse striate). Based on similar morphology, the type KNG 7 is assigned to hyphomycete genus Xylomyces. According to mycobank database (www. mycobank.org), the genus Xylomyces consists of nine species but only four, Xylomyces chlamydosporus Goos, Brooks & Lamore, Xylomyces giganteus Goh, Ho, Hyde & Tsui, Xylomyces rhizophorae Kohlm. & Volkm.-Kohlm. and Xylomyces acerosisporus Oliveira, Malosso & Castañeda, produce large spores over 140 μm long with 6-14, 6-26, 11-43(-64) and 7-15 septa, respectively [START_REF] Goos | An undiscribed hyphomycete from wood submerged in a Rhode Island stream[END_REF]Goh et al., 1997a;[START_REF] Kohlmeyer | A new marine Xylomyces on Rhizophora from the Caribbean and Hawaii[END_REF][START_REF] Oliveira | Xylomyces acerosisporus sp. nov. from submerged leaves from Brazil[END_REF]. Morphologically, the type KNG 7 is the most close to X. chlamydosporus and X. giganteus. For this two and possibly upcoming species with same spore morphology the X. chlamydosporus-type is erected here.

Xylomyces chlamydosporus is the type species of Xylomyces and it was first described from dead, decaying wood submerged in freshwater in southern Rhode Island and Alabama [START_REF] Goos | An undiscribed hyphomycete from wood submerged in a Rhode Island stream[END_REF]. The fungus was found during all seasons at water temperature ranging from 1.7 to 23.8 °C; it grows well on laboratory media within temperature range 15 to 30 °C and at salinities of up to 22.15 ‰ [START_REF] Goos | An undiscribed hyphomycete from wood submerged in a Rhode Island stream[END_REF]. Its known distribution is from Brunei Darussalam, Hong Kong, Seychelles, and the United States (Goh et al., 1997a). Xylomyces giganteus was described from submerged wood in Australia and is also found in South Africa and United Kingdom (Goh et al., 1997a). Our findings reveal the presence of X. chlamydosporus-type during the Late Holocene in NE Iran. [START_REF] Campbell | Phylogenetic relationships among taxa in the Jahnulales inferred from 18S and 28S nuclear ribosomal DNA sequences[END_REF] refer Xylomyces to the order Jahnulales based on the wide mycelium and molecular evidence, while Sivichai et al. ( 2011) made a connection between X. chlamydosporus (anamorph) and Jahnula aquatica (teleomorph). [START_REF] Goos | An undiscribed hyphomycete from wood submerged in a Rhode Island stream[END_REF] assigned Xylomyces chlamydosporus to the fossil fungus Pluricellaesporites psilatus Clarke known from late Cretaceous [START_REF] Clarke | Fungal spores from Vermejo Formation coal beds (Upper Cretaceous) of central Colorado[END_REF]. Recently, spores of Xylomyces giganteus are reported from the early Eocene formation Princeton Chert [START_REF] Klymiuk | Paleomycology of the Princeton Chert I. Fossil hyphomycetes associated with the early Eocene aquatic angiosperm, Eorhiza arnoldii[END_REF].

Zopfiella cf. submersa (KNG 60; Plate III: 7-12) Spores are 28-30 × 18-20 μm in size, limoniform, truncate at the base, dark-brown, with a subapical germ pore of 0.5-1 μm diameter, umbonate at the apex. The wall is 2-3 μm thick with a coarse scabrate surface. The spores resemble Zopfiella submersa Guarro, Al-Saadon, Gené et Abdullah, however its upper melanized cell is smaller (13.0-20.5 × 10-14 μm). It is possible to assume a change of the spore size due to fossilisation processes or laboratory preparations or appearance of other Zopfiella species. For example, Zopfiella inermis has the largest spores in the genus (28-32 × 18-21 μm) [START_REF] Malloch | New cleistothecial Sordariaceae and a new family, Coniochaetaceae[END_REF], corresponding well to the size of KNG 60. Unfortunately, we could not access the original publication for comparison of all morphological characteristics. Therefore, KNG 60 is named Zopfiella cf. submersa. Although different Zopfiella species grow on a wide range of substrates such as herbaceous debris, rotten wood, dung, and soil in terrestrial and marine environments, Z. submersa was first described from the Euphrates River in Iran, on submerged dead culms of Phragmites and Arundo donax [START_REF] Guarro | Two new cleistothecial ascomycetes from Iraq[END_REF].

Discussion

Taxonomic relationship between Fusiformisporites and Megalohypha aqua-dulces

Fusiformisporites has a long identification history. The fossil form genus Fusiformisporites was first described by [START_REF] Rouse | Plant microfossils from Burrard Formation of Western British Columbia[END_REF] from the Tertiary sediments of the Burrard Formation of western British Columbia. In describing the genus Fusiformisporites and F. crabbii as the holotype, [START_REF] Rouse | Plant microfossils from Burrard Formation of Western British Columbia[END_REF] suggested a relationship to algae such as Desmatractum bipyramidatum (Chodat) Pascher or oospores of Oedogonium, both are representatives of the Chlorococcaceae, or representatives of the Class Desmocontae (Division Pyrrophyta). However, this view was not supported.

Later [START_REF] Elsik | Palynology of a Paleocene Rockdale lignite, Milam county, Texas. I. Morphology and taxonomy[END_REF] recognised the fungal nature of Fusiformisporites and affiliated the genus to the extant fungus Cookeina, as illustrated by [START_REF] Wolf | Fungus spores in east African lake sediments[END_REF]. Indeed, describing fungal spores from East African lake sediments, [START_REF] Wolf | Fungus spores in east African lake sediments[END_REF] drew a 2-celled fungal spore with striation and erroneously named it Cookeina, a wood inhabiting pantropical genus from the Pezizales. In fact, ascospores of Cookeina can bear striations but consist of only one-cell [START_REF] Iturriaga | A monograph of the genus Cookeina (Ascomata, Pezizales, Sarcoscyphaceae)[END_REF][START_REF] Weinstein | A phylogenetic study of the genus Cookeina[END_REF], contradicting [START_REF] Wolf | Fungus spores in east African lake sediments[END_REF] drawings and the morphology of Fusiformisporites spores. Nevertheless, Fusiformisporites affinity to Cookeina was used in further geological studies [START_REF] Germeraad | Fossil remains of fungi, algae and other organisms from Jamaica[END_REF][START_REF] Kalgutkar | Synopsis of fossil fungal spores, mycelia and fructifications[END_REF][START_REF] Singh | Fungal remains from the Neogene sediments of Mahuadanr valley, Latehar district, Jharkhand, India and their palaeoclimatic significance[END_REF][START_REF] Massini | The effects of volcanism on Oligocene-age plant communities from the Ethiopian Plateau, and implications for vegetational resilience in a heterogeneous landscape[END_REF][START_REF] Taylor | Fossil fungi[END_REF]. While referring to a personal communication of Elsik in 1996, Rull and[START_REF] Rull | Surface palynology of a small coastal basin from Venezuela and potential paleoecological applications[END_REF] suggested that Fusiformisporites might be a dung fungus, indicating foraging and grazing animals. However, they did not affiliate it to any species. [START_REF] Carrión | Fine-resolution Upper Weichselian and Holocene palynological record from Navarrés (Valencia, Spain) and a discussion about factors of Mediterranean forest succession[END_REF] and [START_REF] Carrión | Cryptogam spores and other non-pollen microfossils as sources of palaeoecological information: case-studies from Spain[END_REF] note an absence of published connections to extant fungal taxa and suggest a possible affinity of Fusiformisporites to ascospores of Nectria peziza, Herpotrichia lignicola, Parodiella perisporioides or Ceriophora palustris. However, all these species have different spore morphology.

Studying Holocene sediments from salt marshes, [START_REF] Marsh | Identifying high-level salt marshes using a palynomorphic fingerprint with potential implications for tracking sea level change[END_REF] suggested correspondence of Fusiformisporites duenasii to Atrotorquata lineata (Cainiaceae, Xylariales), which was described from standing culms of Juncus roemerianus. Similar spore morphology of both species supports this connection.

The morphology of spores from the Kongor sediment core is comparable to the morphology of Megalohypha aqua-dulces. The larger size of the spores from the Kongor core (Table 1) can be explained by fossilisation processes or laboratory treatment or storing in glycerine. Influence of these processes on size is well-known for pollen, but similar studies have not been done for fungal spores. The spores share similar characteristics to some species of the fossil form genus Fusiformisporites. From 15 described fossil species of Fusiformisporites (Table 1), seven species have a similar size as Megalohypha aqua-dulces: Fusiformisporites annafrancescae, Fusiformisporites crabbii, Fusiformisporites keralensis, Fusiformisporites paucistriatus, Fusiformisporites pseudocrabbii, Fusiformisporites rugosus, and Fusiformisporites striatus. Apical thickness is described and seen on the drawings of four species: F. crabbii, F. keralensis, F. paucistriatus, and F. pseudocrabbii. Only F. annafrancescae has distinct facetted sectors in the description. The spore diversity of Megalohypha aqua-dulces from the Kongor core shows that facetted sectors are not easy to see in decomposed spores (Plate I: 4). Combining all morphological features, we suggest that F. crabbii, F. keralensis, F. paucistriatus, F. pseudocrabbii and F. annafrancescae can all be affiliated to Megalohypha aqua-dulces. Most likely other representatives of Fusiformisporites belong to different fungal taxa.

Ecology and palaeoecology

The fungus Megalohypha aqua-dulces A. Ferrer et Shearer is described from submerged wood in tropical forest streams in Panama and Thailand [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF]. Studies on 18S and 28S nuclear ribosomal DNA sequences supported its position in the order Jahnulales [START_REF] Campbell | Phylogenetic relationships among taxa in the Jahnulales inferred from 18S and 28S nuclear ribosomal DNA sequences[END_REF]. Molecular phylogeny places Megalohypha aqua-dulces within the Jahnula sensu stricto clade in the polyphyletic genus Jahnula [START_REF] Suetrong | A taxonomic revision and phylogenetic reconstruction of the Jahnulales (Dothideomycetes), and the new family Manglicolaceae[END_REF]. Similar to other freshwater ascomycetes, Megalohypha aqua-dulces is an important degrader of wood in fresh water, playing a key role in the process of carbon mineralization. It produces a wide spectrum of enzymes such as general cellulases, endoglucanase, β-glucosidase, xylanase, laccase, amylase, pectic lyase, and polygalacturonase, making the degradation of cellobiose, hemicellulose, lignin, starch and pectin possible [START_REF] Simonis | Extracellular enzymes and soft rot decay: are ascomycetes important degraders in fresh water?[END_REF]. [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF] suggested that the occurrence of soft rot cavities was caused by Megalohypha aqua-dulces, however further experimental studies did not support this conclusion [START_REF] Simonis | Extracellular enzymes and soft rot decay: are ascomycetes important degraders in fresh water?[END_REF].

In general, freshwater ascomycetes grow in freshwater habitats and complete part or the whole of their lifecycle in water [START_REF] Cai | Genera of freshwater fungi[END_REF]. They can be recorded in terrestrial and marine habitats and therefore are divided in four major groups according to their occurrence: 1) exclusively freshwater; 2) freshwater and terrestrial; 3) freshwater and marine; 4) freshwater, marine and terrestrial [START_REF] Vijaykrishna | Molecular taxonomy, origins and evolution of freshwater ascomycetes[END_REF]. Since Megalohypha aqua-dulces was described from freshwater habitats, and the known Holocene occurrences are from freshwater environments, the species likely belongs to the first group. However, spores of F. pseudocrabbii were described from the Tertiary coastal to marginal marine environment in the Eastern Niger Delta in Nigeria [START_REF] Ajaegwu | Late Miocene to early Pliocene palynostratigraphy and palaeoenvironments of ANE-1 Wall, Eastern Niger Delta, Nigeria[END_REF], possibly suggesting the ability of Megalohypha aqua-dulces to occupy marine habitats.

While the entire group of freshwater fungi was highlighted for its importance in the palaeoecological studies [START_REF] Sherwood-Pike | Freshwater fungi: fossil record and paleoecological potential[END_REF], Megalohypha aqua-dulces has a potential to be used as palaeoecological indicator for presence of wood. In the Kongor sediment core, Megalohypha aqua-dulces represents a part of the freshwater fungal spore assemblage (Fig. 1). Being described from submerged wood, Megalohypha aqua-dulces indicates presence of decaying wood and therefore trees or shrubs growing on, or near the sampling site. This interpretation is supported by the presence of other wood decomposers such as conidia of Xylomyces chlamydosporus-type, Dictyosporium digitatum and Dictyosporium heptasporum [START_REF] Cai | Genera of freshwater fungi[END_REF]. In addition, Zopfiella cf. submersa grows on herbaceous debris or wood while Sporoschisma saccardoi-type is saprobic on decaying wood and bamboo culms [START_REF] Cai | Genera of freshwater fungi[END_REF]. Interestingly, the continuous presence of woody vegetation on the Kongor site is neither indicated by pollen nor by macroremains (Fig. 1), but by insects, strongly suggesting the presence of riverine forests with Alnus or Salix close to the site [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF]. In fact, pollen of woody vegetation is present in the pollen diagram (4-20%), but due to possible long-distance transport it is not possible to infer local vegetation (Fig. 1). Macroremains of trees and shrubs provide a very local signal but can rapidly become decomposed. Remains of Rubus, Sambucus, Morus, and Viscum occur in the upper 60 cm of the core, but are almost completely absent in the lower part (Fig. 1), possibly due to decomposition. Considering the biology of Megalohypha aqua-dulces, it is possible that wood of the abovementioned trees and shrubs as well as of shrubby Artemisia or Chenopodiaceae might be the possible substrates for the development of freshwater lignicolous fungi at the Kongor site.

The presence of spores of freshwater fungi in sediments provides opportunities to infer the presence of woody vegetation development at a site. This can be used, for example, for testing of the gallery forest theory in South America. Our preliminary results on the sediment core São Francisco de Assis from southern Brazil [START_REF] Behling | Late Quaternary grassland (Campos), gallery forest, fire and climate dynamics, studied by pollen, charcoal and multivariate analysis of the São Francisco de Assis core in western Rio Grande do Sul (southern Brazil)[END_REF] provides evidence for the first occurrence of Megalohypha aqua-dulces in association with Potamomyces spp. [START_REF] Schlütz | On the relation of Potamomyces armatisporus to the fossil form-type Mediaverrunites and its taxonomical and ecological implications[END_REF][START_REF] Nuñez Otaño | The occurrence of Potamomyces palmarensis sp. nov. in the Late Holocene of El Palmar National Park (Colón, Entre Ríos, Argentina) and transfer of fossil species of Mediaverrunites to Potamomyces[END_REF] in the mid-Holocene while it is absent from the sediment during the late glacial and early Holocene. In contrast, a core from Aguas Claras near Porte Alegre (SE Brasil) shows the presence of Megalohypha aqua-dulces during the late glacial [START_REF] Medeanic | Indicative value of non-pollen palynomorphs (NPPs) and palynofacies for paleoreconstructions: Holocene peat, Brazil[END_REF].

Freshwater ascomycetes have pan-tropical or pan-temperate distributions and may overlap in warm temperate or subtropical regions. The optimum temperature for tropical and temperate freshwater ascomycetes is 20-25 °C [START_REF] Vijaykrishna | Molecular taxonomy, origins and evolution of freshwater ascomycetes[END_REF]. Recent documentation of Megalohypha aqua-dulces spores in Holocene peat cores from Indonesia (Fig. 2) confirms its pantropical distribution. Occurrence of the fungus in the peatland of Northern Iran and southern Brazil expands the known distribution of Megalohypha aqua-dulces to more arid subtropics, highlighting its ecological plasticity.

The modern distribution of Megalohypha aqua-dulces in the tropics, and its Holocene occurrence in the subtropics suggest that it is a good indicator of warm humid conditions in the Tertiary, as proposed from geological records for Fusiformisporites [START_REF] Elsik | Palynology of a Paleocene Rockdale lignite, Milam county, Texas. I. Morphology and taxonomy[END_REF][START_REF] Kumar | Fungal remains from the Miocene Quilon Beds of Kerala State, South India[END_REF][START_REF] Oboh | Multivariate statistical analyses of palynodebris from the Middle Miocene of the Niger Delta and their environmental significance[END_REF][START_REF] Kalgutkar | Fossil fungi from the lower Tertiary Iceberg Bay Formation, Eukeka Sound Group, Axel Heiberg Island, Northwest Territories, Canada[END_REF]. [START_REF] Carrión | Fine-resolution Upper Weichselian and Holocene palynological record from Navarrés (Valencia, Spain) and a discussion about factors of Mediterranean forest succession[END_REF] and [START_REF] Carrión | Cryptogam spores and other non-pollen microfossils as sources of palaeoecological information: case-studies from Spain[END_REF] use Fusiformisporites sp. as indicators of organic matter decomposition and peaty layer formation in deposits of the Canal de Navarrés (Spain), whereas the presence of Megalohypha aquadulces provides evidence of decaying wood in the peat.

Geological evidence for the evolution of aquatic ascomycetes

Freshwater fungi colonise streams around the world, and thus they are not restricted by geographical barriers [START_REF] Wood-Eggenschwiler | Geographical distribution of Ingoldian fungi[END_REF][START_REF] Vijaykrishna | Molecular taxonomy, origins and evolution of freshwater ascomycetes[END_REF]. [START_REF] Hyde | Adaptation for dispersal in filamentous freshwater fungi[END_REF] suggest that fungi 1) might have evolved before the split of the continents, or 2) have been carried between continents on plant substrates, or 3) fungal spores may have dispersed by animals or wind. Ecological and molecular data suggest that freshwater ascomycetes should have evolved from their terrestrial ancestors [START_REF] Vijaykrishna | Molecular taxonomy, origins and evolution of freshwater ascomycetes[END_REF] and may have multiple origins [START_REF] Belliveau | Molecular evidence confirms multiple origins of aquatic hyphomycetes[END_REF]. Molecular studies propose that the earliest divergence of freshwater species in Jahnulales occurred at 380 ± 100 MYA (Paleozoic period), however most of the freshwater lineages appear to have diverged during the Mesozoic period (66-245 MYA) [START_REF] Vijaykrishna | Molecular taxonomy, origins and evolution of freshwater ascomycetes[END_REF]. In contrast, palaeontological studies reveal that fungal diversity increased after the Cretaceous-Tertiary boundary and that fungi underwent rapid specialisation during the Tertiary, connected with the evolution of angiosperms [START_REF] Graham | The role of fungal spores in palynology[END_REF][START_REF] Kalgutkar | Paleogene fungal palynomorphs from Bonnet Plume Formation, Yukon Territory[END_REF][START_REF] Kalgutkar | Fossil fungi from the lower Tertiary Iceberg Bay Formation, Eukeka Sound Group, Axel Heiberg Island, Northwest Territories, Canada[END_REF].

In the absence of the molecular data for the evolution of Megalohypha aqua-dulces, palaeontological data reveal the occurrence of Fusiformisporites since the Upper Cretaceous (Fig. 2), corresponding well with the diversification of flowering plants and pointing to a coevolution of both groups. The first description of Fusiformisporites, F. crabbii, was made from Upper Cretaceous to the Middle Eocene sediments of the Burrard Formation of western British Columbia [START_REF] Rouse | Plant microfossils from Burrard Formation of Western British Columbia[END_REF]. Further Upper Cretaceous finds of Fusiformisporites are known from NW Bolivia (Vajda-Santivanez, 1999), NW Ellesmere Island in Canada [START_REF] Falcon-Lang | Palaeoecology of Late Cretaceous polar vegetation preserved in the Hansen Point Volcanics, NW Ellesmere Island, Canada[END_REF] and the north-western desert in Egypt [START_REF] El Beialy | Palynological, palynofacies, paleoenvironmental and organic geochemical studies on the Upper Cretaceous succession of the GPTSW-7 well, North Western Desert, Egypt[END_REF]. During the Tertiary, Fusiformisporites evolves further and becomes more diverse and abundant (Fig. 2, [START_REF] Elsik | Microscopic fungal remains and cenozoic palynostratigraphy[END_REF]). In the Paleogene, Fusiformisporites pseudocrabbii, Fusiformisporites crabbii, Fusiformisporites lineolatus, Fusiformisporites lineatus, Fusiformisporites annafrancescae, Fusiformisporites microstriatus, Fusiformisporites paucistriatus, Fusiformisporites rugosus and other Fusiformisporites species are documented in the USA [START_REF] Elsik | Palynology of a Paleocene Rockdale lignite, Milam county, Texas. I. Morphology and taxonomy[END_REF][START_REF] Sheffy | Morphology and taxonomy of fungal spores[END_REF], Canada [START_REF] Kalgutkar | Fossil fungi from the lower Tertiary Iceberg Bay Formation, Eukeka Sound Group, Axel Heiberg Island, Northwest Territories, Canada[END_REF][START_REF] Norris | Paleocene-Pliocene deltaic to inner shelf palynostratigraphic zonation, depositional environments and paleoclimates in the Imperial ADGO F-28 Well, Beaufort-Mackenzie basin[END_REF], coasts of North America [START_REF] Mustard | Stratigraphy and evolution of Tertiary Georgia Basin and subjacent Upper Cretaceous sedimentary rocks, southwestern British Columbia and northwestern Washington State[END_REF][START_REF] Jansonius | Redescription of some fossil fungal spores[END_REF], Jamaica [START_REF] Germeraad | Fossil remains of fungi, algae and other organisms from Jamaica[END_REF], central Ecuador [START_REF] Jaillard | Stratigraphy of the late Cretaceouspaleogene deposits of the Cordillera Occidental of central Ecuador: geodynamic implications[END_REF], India [START_REF] Saxena | A Catalogue of Tertiary Fungi from India[END_REF][START_REF] Singh | Refinement of paleobathymentric curves of paleoceneearly eocene sequences in selected wells of Cambay Basin[END_REF], Northern Trace basin (Turkey) [START_REF] Ediger | Tertiary fungal and algal palynomorph biostratigraphy on the Northern Thrace Basin, Turkey[END_REF]Alişan, 1989), Cameroon (Salard-Cheboldaeff, 1979) and the Ethiopian Plateau [START_REF] Massini | The effects of volcanism on Oligocene-age plant communities from the Ethiopian Plateau, and implications for vegetational resilience in a heterogeneous landscape[END_REF]. Neogene finds of Fusiformisporites are less diverse. Fusiformisporites pseudocrabbii was found in the Eastern Niger Delta in Nigeria [START_REF] Ajaegwu | Late Miocene to early Pliocene palynostratigraphy and palaeoenvironments of ANE-1 Wall, Eastern Niger Delta, Nigeria[END_REF] and in the Parana Formation of Argentina [START_REF] Garralla | Palinomorfos (fungi) de la formacion Parana (Mioceno superior) del Pozo Josefina, provincia de Santa Fe, Argentina[END_REF]. Fusiformisporites crabbii is known from the Niger Delta [START_REF] Bankole | Palynostratigraphy, palaeoclimates and palaeodepositional environments of the Miocene aged Agbada Formation in the Niger Delta, Nigeria[END_REF] and in Mizoram of NE India [START_REF] Nandi | Validation of the Miocene fungal spore Mediaverrunites from Mizoram, India[END_REF][START_REF] Kar | Fungal taxa from the Miocene sediments of Mizoram, northeast India[END_REF]. Fusiformisporites acutus is described from the Miocene Quilon Beds of Kerala State in India [START_REF] Kumar | Fungal remains from the Miocene Quilon Beds of Kerala State, South India[END_REF]. Other unidentified Fusiformisporites are documented in the Niger Delta [START_REF] Oboh | Multivariate statistical analyses of palynodebris from the Middle Miocene of the Niger Delta and their environmental significance[END_REF], Cameroon [START_REF] Tchouatcha | Existence of "late continental" deposits in the Mbere and Djerem sedimentary basins (North Cameroon): palynologic and stratigraphic evidence[END_REF], the Gulf of Suez in Egypt [START_REF] El Beialy | Insights on the age, climate and depositional environments of the Rudeis and Kareem formations, GS-78-1 well, Gulf of Suez, Egypt: a palynological approach[END_REF], the Gulf of California [START_REF] Helenes | Middle to late Miocene chronostratigraphy and development of the northern Gulf of California[END_REF], and India [START_REF] Singh | Fungal remains from the Neogene sediments of Mahuadanr valley, Latehar district, Jharkhand, India and their palaeoclimatic significance[END_REF].

During the Quaternary, Fusiformisporites was found in the late glacial sediments in southern Brazil [START_REF] Medeanic | Indicative value of non-pollen palynomorphs (NPPs) and palynofacies for paleoreconstructions: Holocene peat, Brazil[END_REF] as well as in the Holocene sediments of the Changuinola peat deposit in Panama [START_REF] Phillips | Holocene Evolution of the Changuinola Peat Deposit, Panama: Sedimentology of a Marine-influenced Tropical Peat Deposit on a Tectonically Active Coast[END_REF], at Holland bay and Bowden in Jamaica [START_REF] Germeraad | Fossil remains of fungi, algae and other organisms from Jamaica[END_REF], SW Pacific islands [START_REF] Macphail | Fungal Spores in Archaeological Contexts: Part 1: Background Evidence[END_REF] and in the late Quaternary -Holocene sediments of Spain [START_REF] Carrión | Fine-resolution Upper Weichselian and Holocene palynological record from Navarrés (Valencia, Spain) and a discussion about factors of Mediterranean forest succession[END_REF][START_REF] Carrión | Cryptogam spores and other non-pollen microfossils as sources of palaeoecological information: case-studies from Spain[END_REF]. [START_REF] Rull | Surface palynology of a small coastal basin from Venezuela and potential paleoecological applications[END_REF] found Fusiformisporites in surface samples from a coastal basin in Venezuela. Al-Ameri and Jassim (2011) indicated the presence of Fusiformisporites in the late Quaternary sediments of southern Iraq, but a photo of the hyaline spore does not correspond to Fusiformisporites. In addition, Holocene finds of Fusiformisporites, new records of Megalohypha aqua-dulces are documented for north-eastern Iran, southern Brazil and Indonesia (Fig. 2).

Based on Fusiformisporites, the evolution of Megalohypha aqua-dulces can be traced to the late Cretaceous, defining its divergence within Jahnulales [START_REF] Vijaykrishna | Molecular taxonomy, origins and evolution of freshwater ascomycetes[END_REF].

Conclusions

Several species of the form genus Fusiformisporites have been described from Cretaceous to Holocene times [START_REF] Kalgutkar | Synopsis of fossil fungal spores, mycelia and fructifications[END_REF]. Not all of them seem to fulfil the morphological criteria of the genus Fusiformisporites as erected by [START_REF] Rouse | Plant microfossils from Burrard Formation of Western British Columbia[END_REF]. The type species Fusiformisporites crabbii and the later erected Fusiformisporites annafrancescae, Fusiformisporites keralensis, Fusiformisporites paucistriatus, and Fusiformisporites pseudocrabbii are in close morphological accordance to the extant fungi Megalohypha aqua-dulces [START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF]. Megalohypha aqua-dulces is a lignicolous freshwater fungus from the tropics belonging to order Jahnulales. Its substrate and habitat preference is underlined by the co-occurrence of spores from additional lignicolous freshwater taxa as Sporoschisma saccardoi-type, Dictyosporium heptasporum, Dictyosporium digitatum, Zopfiella cf. submersa, Xylomyces chlamydosporus-type in the Holocene record from NE Iran [START_REF] Shumilovskikh | Landscape evolution and agro-sylvo-pastoral activities on the Gorgan Plain (NE Iran) in the last 6000 years[END_REF]. Until now known recent and Holocene finds of Megalohypha aqua-dulces indicate that it can be expected in appropriate habitats of the tropics and subtropics including semi-arid regions. Its evolutionary history reaches back into the late Cretaceous and is most probably associated with the diversification of angiosperms. In the fossil context, Megalohypha aqua-dulces is a good indicator for decaying wood, even if macroremains of trees and shrubs do not appear in the sediment.

Fig. 1 .

 1 Fig. 1. Freshwater fungi in the palynological record of the Kongor sediment core. Grey lines show exaggeration line ×10. Circle indicates presence of Morus alba wood.

FusiformF

  III. Spores of freshwater fungi from the sediment Kongor, NE Iran: 1-3: Dictyosporium heptasporum (HdV 1053; core depth 56 cm); 4-6: Dictyosporium digitatum (KNG 27b; core depth 272 cm); 7-12: Zopfiella cf. submersa (KNG 60; core depth 7-9 -0 cm, 10-12 -32 cm); 13-15: single conidiospores (13-14) and conidiophore bearing spores (15) of Sporoschisma saccardoi-type (UG 1002; core depth 13 -0 cm, 14 -32 cm, 15 -184 cm); 16-17: conidiospores of Xylomyces chlamydosporus-type (KNG 7; core depth 16 -160 cm, 17 -184 cm).

Fig. 2 .

 2 Fig. 2. Recent distribution and geological records of Megalohypha aqua-dulces and Fusiformisporites.

Table 1

 1 Morphological characteristics of Megalohypha aqua-dulces and Fusiformisporites species (based on[START_REF] Kalgutkar | Synopsis of fossil fungal spores, mycelia and fructifications[END_REF][START_REF] Ferrer | Megalohypha, a new genus in the Jahnulales from aquatic habitats in the tropics[END_REF]).

	Species	Length	Width	Wall	Septum	Striation	Apical ends	Form
		(μm)	(μm)
	Megalohypha aqua-dulces	40-55	19-22	-	Dark band	Sulcate striations	Acutely tapered	Fusiform
	Ferrer & Shearer 2007
	Subfossil M. aqua-dulces	47-60	21-27	1-1.5 μm	2 -3 μm	5 -7 grooves with broader ridges	Facetted sectors	Fusiform
	(present study)
	Fusiformisporites	44-55	19-24	0.25-0.5 μm (1 μm	1-2 μm	0.25-0.5 μm wide, spaced 0.5-1 μm	Facetted sectors	Fusiform
	annafrancescae Norris			at apices)
	1997
	F. crabbii Rouse 1962	45-52	-		3 μm	5 grooves exposed on each flattened	-	Fusiform
						sector
	F. duenasii Kalgutkar	28-32	8-10	-	-	-	-	-
	and Jansonius 2000
	F. elongatus Ramanujam	35-38.5	8-12	1 μm	2.5 μm	Fine striate with ridges as thick as grooves Blunt ends	-
	& Rao 1978
	F. foedus Salujha, Kindra	43.2-46.4 24.5-27.2 1.2 μm	2 -2.5 μm	10 ridges about 1.5 μm wide	Pointed ends	-
	& Rehman 1974
	F. keralensis Ramanujam	51-56	32-36	1.5 μm, much	4 μm	Striae numerous, ridges slightly broader	Ends truncate to broadly	Fusiform to
	& Rao 1978			thicker at each end		than grooves	arched	rhomboidal
	F. lineatus Rouse &	58-62	23-29	0.75-1.0 μm	-	3-5 in each cell with a uniform width of	Polar cap readily detaches or	Fusiform
	Mustard 1997			uniform		0.3-0.9 μm	hinges open
	F. lineolatus Sheffy and	33.8	18.4	-	1 μm	6 -7 ribs	-	Fusiform
	Dilcher 1971
	F. mackenziei Parsons &	31-41	15.5-24 Thicker at apices	Incompl.	15 to 20 ribs	Rounded apices, slight apical	Fusiform
	Norris 1999				septate		nub
	F. marii Elsik 1968	21	12	1 μm	Thicker than	Two ridges in one hemisphere rotated 90°f -Capsular to
					wall	rom two ridges in the opposite		ovoid
						hemisphere
	F. microstriatus Hopkins	42-49	-	Thick, granular	-	Fine longitudinal ribs	-	Oval
	1969
	F. paucistriatus Rouse &	39-42	15-22	0.25-0.5 μm	-	3-10 striae, very thin, irregular	1.5-2 μm thick at apices	-
	Mustard 1997
	F. pseudocrabbii Elsik	40-45	25	Inner layer 0.5 μm,	2 μm; two	Broad longitudinal ribs or folds	1.5-2 μm thick at apices	Fusiform
	1968			outer 0.5-1.5 μm	layers
	F. rugosus Sheffy and	43.5	19.3	-	2-3 μm	Folds and tears, 1 μm thick	Rounded at one apex, with
	Dilcher 1971						flat basal attachment at other
							end

Plate I. Spores of Megalohypha aqua-dulces (KNG 62) from the sediment core Kongor, NE Iran, showing variation in spore morphology and different preservation grade (1-2: 176 cm core depth, 3: 224 cm, 4: 64 cm, 5-6: 48 cm, 7-8: 96 cm, 9: 72 cm, 10: 80 cm). Photos at 500× magnification with oil immersion.

Acknowledgements

We thank James Dalling and Bas van Geel for helpful comments on the manuscript. The study is conducted within the European Research Council project PERSIA (grant 295375) and partly supported by the Russian Foundation for Basic and the Tomsk State University competitiveness improvement programme (grant 8.1.19.2017).