Brice Goglin
email: brice.goglin@labri.fr

On the Efficient Usage of High-Speed Networks for Distributed Storage in Clusters

Keywords: Distributed storage, remote file access, cluster, high-speed network, zero-copy, unexpected messages, event notification

Parallel applications running on clusters require both high-performance communications between nodes and efficient access to the storage system. We propose to improve the performance of distributed storage systems in clusters by efficiently using the underlying high-performance network to access remote storage systems. Storage and parallel computation have very different requirements. We show that it is required to modify the network programming interfaces and detail several proposals to make these interfaces interact more smoothly with distributed storage. Performance evaluations show that the integration of these ideas makes highspeed networks easy to use and very efficient in the context of storage.

Introduction

The increasing demand of performance in scientific computing, either for numerical simulation, particle physics, genomics, or virtual reality, requires a continuous improvement of the hardware. Massive super-computers have been replaced within the last decade by clusters of workstations which are less expensive, more generic and extensible. However, obtaining highperformance on such machines implies that the cost of communication between nodes is as low as possible.

A large amount of work has been put on first improving communication performance and secondly offloading its processing into the hardware. Nowadays, high-speed networks provide ultra-low latency (a cou-ple micro-seconds) with a very high bandwidth (gigabytes per second). Since most usual protocols have troubles making the most out of this hardware [START_REF] Barak | Performance of the Communication Layers of TCP/IP with the Myrinet Gigabit LAN[END_REF], several dedicated programming interfaces have been designed, for instance BIP or MX on MYRINET, or VERBS on INFINIBAND. Message passing is nowadays the most often used programming model for parallel applications [START_REF] Brightwell | Scalability limitations of VIA-based technologies in supporting MPI[END_REF], especially through the MPI [START_REF] Forum | MPI: A message-passing interface standard[END_REF] interface. Since these softwares were implemented to efficiently support these specialized networks, communications between multiple instances of a single parallel application may easily benefit from very high performance.

Besides, high performance computing also requires an efficient access to storage. There have been multiple research projects to improve distributed file systems. First, they tried to make the client independent from the server by implementing complex caching et coherency maintenance strategies [START_REF] Nelson | Caching in the Sprite Network File System[END_REF]. The emergence of large clusters then required the server to support a much more important workload, leading to specific research in this area [START_REF] School | File Systems for Clusters from a Protocol Perspective[END_REF]. Shared storage systems without server but with global synchronization were developed such as GFS [START_REF] Soltis | The Global File System[END_REF] or XFS [START_REF] Anderson | Serverless network file systems[END_REF]. Then, client-server models as PVFS [START_REF] Ligon | An Overview of the Parallel Virtual File System[END_REF] or LUSTRE [START_REF] Schwan | Lustre: Building a File System for 1,000 Node Clusters[END_REF] were designed to support the workload of clusters by parallelizing the server and the storage system and distributing the work. However, communications in this case remain simple and do not benefit from the underlying high-speed network, even if the required bandwidth might be as high as for communications between processes in a parallel application.

Specializing network stacks to achieve best performance in parallel applications made them hard to use in other contexts where requirements are different. Therefore, it is necessary to study how to adapt these technologies to distributed storage, especially the integration of the programming model of high-speed networks in various implementations of storage. It first requires to look at data transfers between nodes, in particular a client and a server, and secondly communication control and management of the events they generate.

This article presents a study of an efficient usage of high-speed networks for distributed storage. The idea is to propose new optimizations that should be used together with existing caching and parallelizing strategies in order to improve performance by maximizing the usage of clusters' networks. We first present in Section 2 a modeling of remote storage access and locate possible optimizations. We then study in Section 3 the implementation of remote storage access within the LINUX kernel. We look both at data, where constraints on memory management are important, and control, where notifications of events and flow control matter. We propose several solutions to adapt existing programming interfaces of high-speed networks for distributed storage and evaluate their performance in Section 4.

Analysis of Interactions between Storage and Networking

To exhibit possible optimizations within remote storage access, we first present a model of these accesses and detail the various costs. Fig. 1. Interactions involved when accessing remote files, numbered from 1 to 5. Black arrows are the regular data path while the grey arrow is an optional path that the application may choose to bypass the cache.

Figure 1 shows the steps during remote storage access. The whole access time T Total has to be described as the sum of the cost of 4 steps involving the client, the network, the server, and the storage disks (Equation ( 1)).

T Total = T Client + T Network + T Server + T Disk [START_REF] Barak | Performance of the Communication Layers of TCP/IP with the Myrinet Gigabit LAN[END_REF] To analyze these times more precisely, we introduce the following notations:

T Storage Time for the software to access to the local storage.

T Data Time spent in software to transfer data on the network.

T Control Time to manage and control network communications.

Times T Disk and T Network to access disks and the network are hardware specific (latency and bandwidth), but are fortunately well known nowadays. The time spent in the client or server, however, are software specific and depend on the implementation. On the client side, it corresponds to an access from the application to the client module managing storage (interaction #1 with cost T Storage1 ), followed by initiating a network communication (interaction #2, which implies constraints regarding both control T Control2 and data transfer T Data2 ). On the server side, network communications have to be managed too (T Control4 and T Data4 ) before an access to the local storage subsystem is done (interaction #5 with cost T Storage5 ).

T Client = T Storage1 + T Control2 + T Data2 (2)
T Server = T Control4 + T Data4 + T Storage5 (3)
While hardware related times are fixed, software layers might allow some optimizations. Interaction #1 between the application and the client module accessing remote files has been the topic of lots of research. Some improvements have been proposed in the programming interface to suit the needs of parallel applications, especially regarding parallel, collective, vectorial or asynchronous access within MPI-IO [START_REF] Bordawekar | Design and Evaluation of primitives for Parallel I/O[END_REF]. Some specific features were added to improve the usage of the high-speed network in DAFS [START_REF] Magoutis | Design and Implementation of a Direct Access File system (DAFS) Kernel Server for FreeBSD[END_REF].

Time T Storage1 in the client remains low in case of a user-level implementation. In the kernel implementation, it might be much higher since several software layers have to be involved together with a copy of data in the cache. The overhead may be evaluated to about 15 µs for kilobytes accesses on a 2.6 GHz PENTIUM 4 XEON host. However, the actual cost may be reduced by the fact that the above cache generally avoids multiple accesses to the distant server.

On the server side, interaction #5 between the server process and its local storage subsystem has been studied a lot in the general context of highperformance storage. The corresponding time T Storage5 may thus vary a lot with the implementation.

In the meantime, the cost of using the network has been the target of multiple research projects in the context of distributed storage. We now describe how specific high-speed networks are and then emphasize the constraints they put on distributed storage within T Control et T Data .

High-speed networks specificities

The design of high-speed networks for clusters is based on both highperformance (few microseconds latency and gigabytes per second bandwidth) and highly specific innovations in the hardware and in the software stack. The need to achieve optimal performance for user-level communications between multiple instances of an MPI application led to the emergence of specificities and optimizations for this area: operating system bypass, memory copy avoidance, asynchronous communications and flow control designed for homogeneous traffic.

OS-Bypass communications

Strongly coupled parallel applications often exchange lots of small messages between their processes. The overall performance is thus limited by the latency of the network. The critical path between the application and the network interface has to be as short as possible. It is achieved by avoiding the traversal of multiple software layers in the operating system (OS-Bypass) when posting requests and receiving events.

This optimization is very efficient. It enables latencies as low as a few microseconds. However, the design of the programming interface for this kind of user-level communications makes it hard to use in other contexts, especially distributed storage which is most of the time implemented at kernellevel. It will lead to high overhead T Control to manage communications.

Zero-copy communications

DMA DMA

Data

Receiver

Data

Link

Network Interface Network Interface

Sender

Userspace

Hardware

Kernel

Fig. 2. Zero-copy OS-Bypass data transfer on high-speed networks.

To achieve maximum computation, it is necessary to keep the computing power available, even during communications. Copying data should thus be avoided since it consumes many CPU cycles. Nowadays, most highspeed networks are able to perform zero-copy communication between the network and user-space application buffers by using DMA (Direct Memory Access) initiated by the network interface (see Figure 2).

Combined with OS-bypass, zero-copy communication enabled high bandwidth and low latency communications with low CPU usage. It also raises the problem of translating the virtual addresses of the application buffers into physical addresses that the hardware may manipulate for DMA. Such a translation is usually performed by the operating system, but it is not possible in the case of OS-Bypass. High-speed network programming interfaces therefore rely on a strategy called Memory Registration which con-sists in pinning memory zones and storing their physical addresses before communications [START_REF] Welsh | Incorporating Memory Management into User-Level Network Interfaces[END_REF]. However, memory registration implies an expensive advanced memory management in the application and proper preparation of memory zones during the initialization, which is not usually done in distributed storage systems. It will thus add a high overhead T Data on data processing.

Asynchronous programming interface

Since the processor has to be as much available as possible for computation, parallel applications should not be blocked during communications. Processing of communications on high-speed networks is therefore offloaded into the network interface so that the host processor may still compute. The application submits asynchronous communication requests to the interface which takes care of processing them in the background. Computation may thus overlap communication until the application checks the completion of requests later. This programming based on events is very different from the usual blocking model of the SOCKET interface. It is very important to deal with it cleverly so that communications are well overlapped. Managing this model may thus also be a large part of the communication control cost T Control .

Homogeneous traffic

The network usage in parallel applications is specific to the explicitly regular distribution of the workload across the machines. Communications are most of time deterministic since the receive often knows in advance that it will receive a message before it actually receives it. Moreover, communications are distributed in a homogeneous manner across the network so that bottlenecks are avoided on the wires as in the processors. The network core is well enough dimensioned to prevent congestion in such a traffic. Control flow protocols in high-speed networks were designed for this usage, with strategies such as stop-and-go or back-pressure, without any notion of equity or fairness. This kind of protocol may not suit other models such as client-server in distributed storage, where the traffic is centralized near the servers. It will be a third part of communication control cost T Control .

Analysis of remote file access cost

We now explain the impact of high-speed network specificities on various remote storage access implementations. User-level, kernel-level and block-level accesses are presented.

User-level access

In the case of a user-level library providing access to remote files, the cost T Storage1 to access the client module of the distributed storage system is almost null (a function call). On the server side, most software layers will have to be traversed from the server process to the local storage, leading to a high T Storage5 .

Network Client

Specific Interface Standard Interface

Application

Network

File Server

Application

Local Files

Standard

Library Library Standard Fig. 3. User-level remote file access through a specific programming interface.

Regarding network access times T Control and T Data , they would be similar to the communication cost in a parallel application since the implementation is at user-level. (Figure 3). The time T Data1 to manage data transfer may be reduced by modifying the standard programming interface between the application and the client. Earlier work in DAFS [START_REF] Rangarajan | Building a User-level Direct Access File System over Infiniband[END_REF] indeed shows that asking the application to provide information on its memory usage to help the network layer is a good idea. The application developer knows how he uses the memory and may thus organize and optimize it to make the network communications easier. Upto 25 % throughput improvement has been observed for database applications on DAFS during this study. Similar results were obtained with MPI-IO on DAFS [START_REF] Wu | MPI-IO over DAFS over VIA: Implementation and Performance Evaluation[END_REF]. In the same way, the application may be made responsible of managing communication control to reduce T Control .

A specific programming interface allows remote file access optimization, but it requires to rewrite applications to respect the new interface. Such a re-development cost, especially if the interface is not portable, may be very high and could slow down software diffusion or standardization. This is the reason why several projects would rather overload standard library interfaces and manage memory registration and communication control transparently in the client module. We studied this model by developing a prototype named ORFA (Section 4.1).

Besides, some systems implement a cache in the client to reduce the need to contact the distant server every time the application accesses a file. The data transfer then involves the cache instead of the application memory. In this case, the storage client access time T Storage1 contains a memory copy between the application and the cache. However, the client may organize and optimize its memory layout with respect to network constraints in order to reduce T Data .

Kernel server

On the server side, accessing the storage may be optimized by moving the server process in the kernel so that several software layers are not traversed anymore and a memory copy is avoided (Figure 4).

Network

Client

Network

Virtual File System Server

Application

Local Files

Standard Library

Fig. 4. User-level access to a kernel-level storage server.

However, high-speed network usage in the kernel first requires a kernel interface, which is not very common. We will present the design and implementation of the MYRINET MX kernel interface later in this article. Moreover, this interface has to be compatible with the user-space interface if it has to communicate with user-level clients. It is for instance not the case with QUADRICS QSNET [START_REF] Petrini | Performance Evaluation of the Quadrics Interconnection Network[END_REF].

Besides, memory zones that are manipulated by a kernel server actually are operating system pages where files are cached. Such pages are very specific (for instance they often do not have any virtual address). It makes them hard to use in the usual programming interface of the network, increasing T Data4 a lot.

Kernel file-system client

The most common strategy to access remote file is actually to place the client module in the kernel-space instead of in user-space. The access time T Storage1 becomes high since system calls are involved. All accesses to this file system are made transparent by the operating system which provides a virtualization layer for all file systems, local ones as well as remote ones (the Virtual File System in LINUX).

This model, as shown on Figure 5, also provides advanced features such as asynchronous, direct (bypassing the cache) or vectorial file access. It suits parallel applications requirements without having to modify the programming interface with a specific library. This is the reason why the most pop- Communications in this model are initiated by the client module within the operating system. There are actually few high-speed network interfaces supporting this. Data transfer is as difficult as on the server side since the memory zones that are involved are those of the cache of the operating system.

Additionally, the application may ask the operating system to not cache any data on the client side (with the O_DIRECT parameter, as described by the grey arrow on Figure 1). Data then have to be transferred directly between the user-level application memory and the distant server. This kind of communication is conceptually very close to usual zero-copy communications on a high-speed network, but in our case they are initiated in the kernel instead of in the user application context. It is a very important requirement on the network programming interface to support such communications since this kind of memory usage is totally uncommon.

The usual programming model of high-speed networks is difficult to apply these two access schemes (with cache or without). The time T Data1 to transfer data may thus become very high.

Block access

The last kind of distant storage access (Network Block Device) consists in placing the client module at the block layer level and manipulating a remote partition or disk. Data are then exclusively transferred as blocks. This model is implemented in shared storage models for clusters such as GFS [START_REF] Soltis | The Global File System[END_REF] or GPFS [START_REF] Schmuck | GPFS: A Shared-Disk File System for Large Computing Clusters[END_REF].

Some work has been proposed on the server side, especially in OPIOM [START_REF] Geoffray | OPIOM: Off-Processor I/O with Myrinet[END_REF] and READ [START_REF] Cozette | READ 2 : Put disks at network level[END_REF], to optimize block transfers between the network and the disks by not going in the host anymore. However, very few similar work has been proposed on the client side.

These communications involve similar memory zones to the previous section. They have the same constraints on the network programming interface. It has to be able to manipulate special memory zones of the operating system. The costs are similar.

Summary of interactions between storage and networking

We explained in the previous section that remote storage access requirements may vary a lot with the actual implementation. The interaction between storage and network access software layers raises several difficulties.

We measured client module access times from the application (T Storage1 ) varying from almost 0 (user-level client) to 50 µs (block-level client). On the server side (T Storage5 ), similar timings may be observed depending on the implementation. Data transfer cost on the client side is high and might be reduced by changing the programming interface to move memory registration problems into the application. A cache also permits to work around expensive memory registration constraints. In a kernel implementation, either in the client or in the server, the memory zones that are involved cannot be managed as usual user-space segments. It implies a high data managing cost T Data , upto 100 µs for several kilobytes. The time T Control for using the asynchronous programming interface well however does not vary much with the implementation type. Most of time, several hundreds nano-seconds or a couple micro-seconds are spent. 1 Summary of software costs that are involved when accessing remote files, and possible improvements.

Table 1 summarizes various software times when accessing remote files. We showed that storage access time and some memory copies are determined by the design of the client or the server, especially if a cache is provided and whether in user or kernel-space. On the other hand, network access times, either regarding data (T Data , because of memory registration) or control (T Control , because of the asynchronous interface and the flow control) remain in all models, with possibly different values. We will study these problems.

This idea is motivated by the fact that the most popular distributed file systems suffer from high-speed network interfaces not suiting their requirements. For instance, LUSTRE was until recently available on only few networks. Its first implementation used MYRINET/GM with additional memory copies since the software interface does not provide a flexible enough memory management. In the same way, PVFS2 [START_REF] Ligon | Next Generaton Parallel Virtual File System[END_REF] developers decided to not access the network from within the kernel client. Their implementation goes back to user-space where a dedicated process takes care of communications. This choice is justified in the documentation by the possible absence of support for network communications from within the kernel [START_REF]Parallel Virtual File System[END_REF]. Our goal is to reduce T Data and T Control by providing a network programming interface that suits the needs of distributed storage.

We tried not to restrict our work to one of distributed storage systems described earlier. Choosing between a user, kernel, or block-level implementation, with or without cache, should remain the administrator or user decision depending on its needs and eventually on the machine architecture. Indeed, depending on how the target application has been programmed and behaves, the requirements regarding performance, caching or coherency might be different. Fortunately, our optimization should apply since we focus our work on the software interface between the distributed storage and network stacks.

Implementation of Remote File Access on Myrinet Networks

We now present a study of the problems that one may face while implementing a distributed storage system on a high-speed network. The overall goal is to reduce T Data and T Control by proposing modifications of existing systems, either network stacks or operating systems, to suit the requirements of distributed storage in clusters.

Hypotheses

We explained in Section 2.3.1 that the cost of using a high-speed network might be reduced by having the application taking care of the issues that are related to data transfer and communication control. This idea, which has been studied in DAFS, implies the modification of the file access programming interface that the application uses. However, such a requirement leads to a complete rewrite of the application to deal with the constraints of the network. We chose to restrict ourself to the standard file access interface. It permits to apply our work to most existing legacy applications.

The distributed file systems we are interested in are client-server models, especially PVFS and LUSTRE, which are the most famous in the high performance computing world nowadays. These systems respect the standard file access interface and may be implemented in the kernel. Studying them will make us work the main types of implementations that we detailed in Section 2.3.

We use MYRICOM MYRINET network [START_REF] Boden | Myrinet: A Gigabit-per-Second Local Area Network[END_REF] which has been the mostly used high-speed network in high performance computing for a decade. Its software drivers are easily reprogrammable, making the implementation of our optimization possible. We first worked on the GM driver, whose programming interface behaves as specificly as explained in Section 2.2 and which represents well what old high-speed network interfaces are. We then proposed several solutions and applied them to the new MX driver of MYRINET networks, which was under development during our study.

Data transfer

As explained in Section 2.2.2, OS-bypass zero-copy communications provide high-performance communications for parallel applications. However, the memory zones that are involved in these communications have to be prepared using an expensive mechanism called memory registration. It is necessary to use this strategy in a clever way. Figure 6 presents a comparison of the cost of memory registration and memory copy. It shows that it might be a good idea to replace memory registration with a copy in a statically pre-registered zone. However, this strategy consumes many CPU cycles and is thus not satisfying for parallel applications since the CPU has to be available as much as possible. A more interesting optimization named Pin-down Cache has been proposed in [START_REF] Tezuka | Pin-down cache: A Virtual Memory Management Technique for Zero-copy Communication[END_REF] to avoid the expensive cost of memory registration. It creates a registration cache by delaying memory de-registration as long as possible.

Memory registration

This strategy is known to be easy to implement and efficient in user-space parallel applications. It applies in the same way for distributed storage in user-space since the requirements are very similar as we explained in [START_REF] Goglin | Optimizations of Client's side communications in a Distributed File System within a Myrinet Cluster[END_REF].

We now study the case of kernel-implemented file-systems, especially LUS-TRE. We focus on the client side since it has the strongest requirements and constraints. Indeed, our decision to comply with the standard file access interface restricts our possibilities since we cannot forward the constraints of the high-speed network interface upto the application. We will detail in the next sections the different types of remote file access that an application may request: through the cache or directly.

Access through the operating system cache

Any regular file access goes through the cache in the operating system. It means that the application actually only deals with this cache, while the system takes care of maintaining the cache up-to-date by contacting the server in the background (Figure 7). The actual communications then involve memory zones of the operating system instead of user-level application buffers.

Application Application Application

Standard Library

Virtual File System

Page Cache

Server Client GM Fig. 7. Remote file access through a kernel client and the operating system cache.

There has been some research to formalize sharing and copying of memory pages between a file-system cache and a network software stack to define a clear semantics [START_REF] Pai | IO-Lite: a unified I/O buffering and caching system[END_REF]. It led to some proposals towards a merge of the operating system file-system cache and the temporary buffers that are involved during network communications. It may help transferring data between the network and the file-system cache [START_REF] Wu | Unifier: Unifying Cache Management and Communication Buffer Management for PVFS over InfiniBand[END_REF]. However, these systems remain based on memory registration and it looks too complicated because of the execution within the kernel and the characteristics of the pages that are involved. Indeed, the pages of the operating system cache are very different from those of user-space application buffers. We showed in [START_REF] Goglin | Optimizations of Client's side communications in a Distributed File System within a Myrinet Cluster[END_REF] that memory registration does not suit these pages at all. Instead of adapting memory registration to these special pages, we proposed to modify the network programming interface in order to directly use the physical addresses of the cache memory. Such a strategy is actually very simple to use since no memory zone preparation is required anymore before communications: these pages are already locked and their physical address is known. We implemented this proposal in the GM interface of MYRINET networks. It required to modify the micro-program that runs in the hardware.

Direct access from the operating system

Accessing remote files through the operating system cache has the drawback of implying a memory copy between the application and the cache, which consumes many CPU cycles. Moreover, parallel applications often want to know that a write has actually been forwarded to the server instead of being kept in the local cache for an unknown delay. Recent operating systems therefore propose direct accesses bypassing the file-system cache. After studying the cached accessed, we worked on these direct accesses.

While memory registration does not suit cached accesses requirements, direct access looks similar to user-level communications in parallel applications since user-space memory zones are involved. The major difference is that communications are initiated from within the operating system. The network interface thus has to be able to manipulate simultaneously virtual addresses of various user-space processes from the kernel. It is a strong requirements since high-speed networks are used to associate any single communication channel to a single task. We had to modify the MYRINET board microprogram again so that the virtual addresses it manipulates also contain an identifier of the target address space [START_REF] Goglin | Optimizations of Client's side communications in a Distributed File System within a Myrinet Cluster[END_REF].

Then, memory registration has to be efficiently used so that its observable cost appears to be low. The registration cache strategy that we described in Section 3.2.1 should suit direct file access needs. However, it requires the cache to be kept up-to-date with respect to modifications of the application address space. Indeed, since the application does not know that some of its pages have been registered on the fly by the underlying software layers, it could modify its address space without making the cache manager aware of it. If the cache is not invalidated when a memory zone becomes invalid, the network hardware could be using invalid address translations, possibly causing serious problems to the system.

Virtual File System

Client

Registration Cache Server

Cache Update

Management Memory

Fig. 8. Management of direct accesses within the operating system with a registration cache that the VMA SPY subsystem keeps up-to-date.

Keeping the cache up-to-date in a user-space implementation is a wellknown problem. However, we showed that it is impossible in a kernellevel implementation because of missing software support. We proposed some modifications to the LINUX kernel to solve this problem. This patch, called VMA SPY, permitted the implementation of a safe registration cache between the GM driver and the remote file access client [START_REF] Goglin | Optimizations of Client's side communications in a Distributed File System within a Myrinet Cluster[END_REF] (Figure 8).

Flexible memory addressing

We focussed on the client side and insisted on memory registration problems since this is the commonly used mechanism to implement zero-copy communications. We implemented various modifications in the GM driver of MYRINET networks and showed how distributed storage requirements may be hard to support with existing network interfaces. Indeed, making these interfaces that were designed for user-space communications in parallel application interact with the distributed storage software layers is hard. We will present an evaluation of our implementation in Section 4.

Apart from modifications in the operating system to maintain the registration cache up-to-date with respect to address space modifications, we identified three features that are required in the network interface:

• Manipulate user-space memory with communications that are initiated in the kernel;

• Share a single communication channel between several address spaces of several processes accessing remote files;

• Manipulate memory zones without having to register them when they have special characteristics such as those of a file-system cache.

We proposed in [START_REF] Goglin | An Efficient Network API for in-Kernel Applications in Clusters[END_REF] a programming interface that provides all these key features. It is based on extended communication primitives that ask the user to describe the memory addressing type of the buffers that are involved. Then, it is possible to manipulate with a uniform interface any buffer in user-space processes or in the file-system cache of the operating system.

We implemented this interface in the new generation driver of MYRINET networks, MX [?]. We tried to keep the core of MX generic so that userspace communications would not be favored and our extended primitives handicapped. We will present a performance evaluation of this work in Section 4.

Flow control

After presenting our study of data transfer related issues regarding distributed storage on high-speed networks, we now proceed with control issues, starting with flow control.

Generic networks and protocols were designed to enable communications between any machines in the world, without any requirements on the network topology and reliability. While it permits a high flexibility, it also implies a large overhead since we have to make multiple machines work together and react to various problems such as congestion or failure. Highperformance computing clusters are based on a regular and static topology, with a well-dimensioned network backbone so that any regular traffic between end nodes does not suffer of any congestion. Transport protocols in lower network layers relies on the fact that the communication channel is reliable. Error recovery is however a rare and non-optimized case.

Parallel applications generally generate a uniform traffic across the cluster. Indeed, a good parallelization requires to distribute the workload across the machines with equity, but also to distribute the network traffic. This way, bottlenecks are avoided, regarding either the actual computing power or link capacity.

Distributed storage does not however generate such a traffic. Indeed, clientserver models explicitly imply a centralized traffic around the server, creating a bottleneck. Parallel file systems have been designed to distribute the workload across multiple servers, distributing the network traffic across various links too. Even so, the system has to be dimensioned correctly since multiple clients may easily saturate any server link.

Figure 9 presents the throughput that our experimental file server may process when multiple clients simultaneously send 64 kB write requests on the GM interface of MYRINET networks. With 92 clients, 233 out of the 250 MB/s supported by the link are used. However, with 184 clients, only 163 MB/s appear to be processed by the server.

What causes this behavior is a large waste of link bandwidth due to re-send of non-received messages. In the Rendezvous model, the one offered by the GM interface and very often used in high-speed networks, the server has to prepare receive buffers. The number of buffers is limited by the available memory in the network interface (125 buffers in this case). If there are too many clients, some requests will not be received due to receive buffer starvation. They will have consumed some bandwidth without their data ever being used. The observable throughput of the server thus decreases with large numbers of clients, as shown on Figure 9.

Unexpected messages is a well-known problem in parallel application programming. For instance, it has been shown that the offloading features of network boards cannot always be enough to efficiently manage unexpected messages in MPI [START_REF] Brightwell | An Analysis of NIC Resource Usage for Offloading MPI[END_REF]. Solving this bandwidth wasting problem may be achieved by having the client wait for the server agreement before sending its data. No message would then be unexpected anymore. Regarding small messages, it is also possible to store them in a temporary buffer in receiver host memory until the application provides the corresponding actual receive buffer. This kind of protocol is nowadays often implemented in MPI layers, but not in most native low-level network interfaces.

Since implementing such a feature in the GM interface would require too many changes, we decided to adapt the application. We designed on top of the restricted low-level network interface a high-level application protocol to manage unexpected messages [START_REF] Goglin | Réseaux rapides et stockage distribué dans les grappes de calculateurs : propositions pour une interaction efficace[END_REF] in a client-server distributed storage model.

We proposed the combined use of Rendezvous and Remote Direct Memory Access (RDMA) models. By deporting data transfer decisions onto the server, it controls the incoming traffic to avoid any bottleneck. The server actually takes care of reading or writing data in the clients' memory when the required resources are available. Figure 10 Client Server Time Fig. 10. Client-server protocol to access remote files when flow control is managed by the server. The client only sends a request while the server takes care of reading or writing in the client memory.

protocol to access remote files. This model is however restricted to network programming interfaces that provides both RDMA and Rendezvous communications, which is for instance not the case of INFINIBAND VERBS.

It is worth citing interesting results that were obtained by having the client initiate RDMA to the server in DAFS [START_REF] Magoutis | The Optimistic Direct Access File System: Design and Network Interface Support[END_REF]. Assuming the server is exporting part of its file-system cache, there are chances that a client successfully writes or reads directly in the cache through RDMA. In case of a cache hit, the client does not require any server intervention anymore. In case of cache miss, a remote exception is sent to client, which reverts to a basic protocol with the server being the master.

Asynchronous programming interface

We explained in Section 2.2.3 that high-speed network programming is based on a very specific model. While the usual SOCKET interface offers blocking communications, high-speed network interface primitives are non-blocking and asynchronous. The application submits communication requests that the hardware processes in background while the application computes. Later, the request status may be checked and the application may block until some requests complete.

Using such a programming model makes it hard to interact between networking and storage because the needs of the storage subsystems may vary a lot. Indeed, we showed in [START_REF] Goglin | Réseaux rapides et stockage distribué dans les grappes de calculateurs : propositions pour une interaction efficace[END_REF] that the server generally waits for the completion on any pending request, while the client may want to wait on a single request. Both these completion strategies are often used in MPI. However, most low-level network programming interfaces do not implement both. When only the former is implemented, as in the GM driver of MYRINET networks or in INFINIBAND VERBS, the latter may be implemented on top of it. To do so, a Dispatch thread takes care of receiving all completion events in a single queue and dispatching them to the corresponding task (Figure 11). Unfortunately, it increases the overall latency since there are much more context switches. We observed several microseconds of overhead in such an implementation.

When only the second strategy is available, as in the ELANLIB interface of QUADRICS networks, implementing the first strategy requires active polling on all pending requests since their completion order is often unknown. It consumes lots of CPU cycles.

Getting the distributed storage subsystem and the high-speed network stack to interact well requires both strategies to be available and efficiently implemented. This requirement actually also appears in MPI middlewares or applications.

Moreover, exploiting multiprocessor machines requires to distribute the workload across multiple processors. It is therefore common to share completion event notifications across several threads. One solution would be to distribute network events in multiple queues (Completion Group) and have one thread take care of each queue. This is a third kind of completion notification that is useful is distributed storage. While the first and second ones were already available in the MX driver of MYRINET networks, we had to implement the third one. It is available as mx_test_any and mx_wait_any in the recent released 1.2 version of MX and is now used in the recent port of LUSTRE and PVFS2 over MX.

Summary of requirements and solutions

We studied in this section various needs corresponding to times T Data et T Control involved when using high-speed networks for distributed storage. Regarding data transfer, memory management has a strong impact on performance and requires a very flexible network programming interface. We explained how to work around the limitations of existing interfaces and proposed an extension that we integrated in the MX driver of MYRINET networks.

Regarding communication control, we first presented an issue related to flow control in client-server implementations of distributed storage. We showed that unexpected messages have to be managed carefully, either in the network stack or in the application. Then, we described completion notification requirements in both storage clients and servers. We explained that it is interesting to have multiple strategies available natively in the network programming interface.

These needs for communication control are actually very similar to those of parallel applications running on MPI. It is thus a good idea to have the corresponding features in the low-level network interface so that both MPI and storage may rely on them. It is what the new MX driver of MYRINET networks now proposes. However, several other existing interfaces such as GM will still have to be used with a complex and less efficient high-level protocol at the application level.

Performance Evaluation

We now present an evaluation of the impact of our proposals on the highspeed network usage in distributed storage, especially regarding how easy and efficient it is to make them interact. We have implemented our ideas regarding both data transfer and communication control in the MX interface of MYRINET networks. This section will therefore compare the efficiency of MX in distributed storage to an old network programming interface, GM.

We actually had to first make MX programming interface available in the kernel so that in-kernel distributed storage modules may use MYRINET networks. Then, we had to extend its implementation to efficiently support various data transfer and memory addressing types as described earlier.

When comparing with GM, we had to heavily modify both the GM programming interface and the operating system as explained in Sections 3.2.3 and 3.2.2 so that distributed storage requirements were met.

Experimentation platform

Measuring the performance of the distributed storage system is very difficult due to various advanced features such as caching or parallelization. To isolate the problem that we have been working on, the efficient usage of the underlying high-speed network, we developed a minimal prototype providing remote file access without any advanced feature. All non-required steps on the path from the application buffer to the server were therefore removed so that only the critical path was observed.

This prototype has been implemented both at user-level (ORFA, Optimized Remote File-system Access [START_REF] Goglin | Performance Analysis of Remote File System Access over a High-Speed Local Network[END_REF]) and in the kernel (ORFS, Optimized Remote File System [START_REF] Goglin | Optimizations of Client's side communications in a Distributed File System within a Myrinet Cluster[END_REF]) so that various remote file access models may be evaluated.

ORFA is based on the dynamic shared library exposing the standard file access interface and converting application requests into remote requests to a distant server over a MYRINET network. We showed in [START_REF] Goglin | Optimizations of Client's side communications in a Distributed File System within a Myrinet Cluster[END_REF] that the registration cache gives good performance for this kind of remote file access. We now present a study of in-kernel performance with ORFS. It will allow the applying of our results in actual distributed storage systems such as PVFS or LINUX. ORFS is based on a kernel module that adds a new file-system type into LINUX.

All experimentations were run between dual 2.6 GHz PENTIUM 4 XEON hosts with 2 GB memory. They were interconnected with a MYRINET 2000 (PCIXD boards) using GM 2.0.13 and MX 0.8.8 drivers.

To illustrate remote file access over MX and GM, we published in [START_REF] Goglin | An Efficient Network API for in-Kernel Applications in Clusters[END_REF] a comparison of raw performance of these interfaces. While MX bandwidth is not much higher than GM's one, its latency is much lower (4 µs against 8 µs). We also noticed that our implementation of in-kernel communications in MX offers as good performance as the regular user-level communications. It is worth noticing it in our study since most network programming interfaces, such as GM or ELANLIB, were initially designed to optimize user-level, making the in-kernel communications harder to optimize. For instance, GM latency in the kernel is 30% higher than in user-space.

Direct access to remote files

Figure 12 presents a study of direct remote file access from within the kernel over ORFS and GM. It shows that our modifications in GM and our VMA SPY infrastructure in the LINUX kernel (see Section 3.2.3) provides very good performance with an in-kernel registration cache. Fortunately, it means that the huge amount of work that has been required to support di- rect access from within the kernel over GM has been useful. Performance is however still slightly lower than in user-space since the client has to traverse several software layers to reach the ORFS client in the operating system (T Storage1 is higher). Figure 13 then compares direct remote file access over GM and MX. Even if raw MX performance is slightly higher than GM, ORFS performance shows that MX may be used even better than GM since the relative throughput is often higher. It has to be noted that GM performance depends a lot on the same memory zones being reused by the application to maximize hits in the registration cache. MX performance does not have such a requirement since no explicit memory registration is needed.

Apart from the performance, MX is actually much easier to use than GM in these implementations. While MX may be immediately used by ORFS, GM requires an external registration cache, some modifications of the kernel (VMA SPY) to keep this cache up-to-date, and some modification in the network programming interface and microprogram (see Section 3.2.3). Figure 14 then presents the performance of remote file access through a file-system cache (Section 3.2.2). Having the cache on the path to the server leads to an explicit splitting of any request into page-sized accesses (4 kilobytes on our machines). Recent LINUX kernels enable multi-page access but it makes results harder to analyze from the network usage point of view.

Access to remote file through the cache

Remote file access through the cache over MX have a 40% higher throughput than over GM. It corresponds to a 54 µs processing time per page on MX and 76 on GM. Within the 22 µs difference, we measured that 13 are caused by MX raw performance being better than GM. This is related to the GM implementation of kernel communications suffering from the userspace design, while our implementation of kernel communications in MX is generic enough to keep performance as high as possible. The remaining 9 µs improvement is caused by the avoidance (thanks to our flexible MX interface) of the complex management of ORFS communications over GM, especially event notification strategies that required a dispatched thread (as described in Section 3.4).

Measuring the impact of the new features that MX proposed remains hard since they mostly have an influence on the latency that the application observes. However, having a file-system cache hides the latency behind request delaying and aggregating. Nevertheless, we showed in [START_REF] Goglin | An Efficient Network API for in-Kernel Applications in Clusters[END_REF] that our work led to a large improvement, especially in latency, in another application that has similar requirements than ORFS, a zero-copy SOCKET protocol.

Block access

Remote block access (Network Block Device, see Section 2.3.4) have very similar requirements to the file access through a cache that we presented above.

Thus, we expect this application to make the most out of our MX interface. We implemented a Network Block Device called MXBD using our MX programming interface in the LINUX kernel. Figure 15 presents a performance comparison between remote block access (MXBD) and file access through the cache (ORFS). The former model only transfers data blocks without any internal structure while the latter transfers file attributes and pages. The requirements over the network interface are very similar, but the block layer has been designed to deal with hardware storage controllers, which can handle asynchronous requests. Asynchronous communications are thus easier to implement efficiently and immediately pipelined. It leads to twice the throughput of file access through the cache. Moreover, when enabling vectorial communications with multiple non-contiguous segments, the whole link capacity may be used.

Combining such an implementation on the client side and a strategy such as OPIOM or READ on the server side should permit end-to-end optimized remote block access.

Conclusion

This article presents an analysis of the interaction between the operating system software layers managing the storage and high-speed networks in clusters. These networks and their application programming interfaces have been designed and optimized for user-space communications within parallel applications. While the performance that may be achieved for this kind of communication is very high, distributed storage performance in these computing systems cannot benefit from the network as well.

Previous works in distributed storage targeted caching and parallelizing strategies. In this paper, we propose an additional approach focussing on improvements of distributed storage system performance by efficiently using the underlying high-speed network. By being so specific to user-space applications, these networks became hard to use in another context.

We presented a detailed analysis of various remote file access models, and we identified the limitations of current high-speed network programming interfaces in this area. We implemented multiple modifications in the GM interface of MYRINET networks and in the LINUX kernel to permit an efficient interaction during data transfer. Moreover, we showed that communication control in distributed storage systems has several requirements that are actually not very different from those of MPI middlewares and applications.

Several ideas were then proposed to make the use of new network interfaces easier for distributed storage. First, the needs of both distributed storage and MPI applications have to be met by the network stack by proposing both multiple event notification strategies and a smart unexpected messages management. Secondly, the in-kernel network interface has to be flexible enough to manipulate various memory addressing types. We implemented these ideas in the new MX driver of MYRINET networks. This work is now available within the official MX distribution.

We finally exposed a performance evaluation of this implementation through an optimized remote file access protocol. We focussed on point-topoint communication between a client and a server since this is where our work matters. Nevertheless, we expect our optimizations to work as well in multiple-nodes systems since we took care of not decreasing the scaling capabilities of existing systems in our implementation.

Raw latency from within the Kernel:

-GM: 8 µs (6 in user-space). + MX: 4 µs (4 in user-space). Remote file access from the Kernel through the Cache:

-GM: Microprogram recompiling to use physical addresses; Dispatcher thread. + MX: 40 % bandwidth improvement over GM.

Direct remote file access from the Kernel:

-GM: Expensive memory registration; Kernel patch for registration cache; Microprogram modification to support multiple address spaces; Dispatcher thread. + MX: At least as good as GM; Easy to use. Figure 16 summarizes the results. Our work in MX is proved more efficient than traditional interfaces. Moreover, it has to be noted that its usage is much simpler. The huge amount of modifications that we had to implement in GM proves that it does not suit distributed storage requirements.

Our work is now used in large production centers within the LUSTRE distributed file system. LUSTRE is able to achieve more than 90% of the link capacity on MYRI-10G networks [START_REF]Lustre -MX-10G Performance Measurements[END_REF]. Moreover, our results also apply to zero-copy SOCKET protocols as well.

The LINUX kernel modifications that we proposed to keep the registration cache up-to-date over GM are not required anymore on MX. However, they could still improve the performance even more. Lots of interesting support for high-speed network specificities in the LINUX kernel is still missing. We discussed this issue with kernel developers and QUADRICS and INFINI-BAND software stack maintainers. While no consensus has been found yet, it seems clear that a support similar to VMA SPY (Section 3.2.3) should be included in the LINUX kernel in the future. Indeed, the emergence of 10 Gbit ETHERNET interfaces raises similar problems than those we faced in high-speed networks. We are planning to look at these issues in the near future.

Fig. 5 .

 5 Fig. 5. Kernel-level remote file access. ular distributed storage systems in clusters such as PVFS or LUSTRE are implemented in the kernel nowadays.

Fig. 6 .

 6 Fig. 6. Comparison between memory registration (with MYRINET-GM) and memory copy on a dual 2.6 GHz PENTIUM 4 XEON host.

Fig. 9 .

 9 Fig. 9. Impact of the amount of clients on the effective throughput of a storage server, with 64 kB write requests and the GM interface of MYRINET networks.

Fig. 11 .

 11 Fig. 11. Event dispatching with a thread.

Fig. 13 .

 13 Fig. 13. Performance comparison of direct access to remote files within the kernel with MX and GM.

Fig. 14 .

 14 Fig. 14. Performance comparison of remote file access through the kernel cache with ORFS over MX and GM.

Fig. 15 .

 15 Fig. 15. Performance of remote block access (with MXBD) and remote file access through the cache (with ORFS) over MX.

Fig. 16 .

 16 Fig. 16. Summary of GM problems and MX improvements for distributed storage from within the kernel.

  describe our new client-server

		Receive Posted
	Receive Posted
	Request Posted
	Request
	Send Completion	Receive Completion
		RDMA Read
	Data
		RDMA Completion
		Processing
	Data	RDMA Write
		Reply Posted
	Reply	RDMA Completion
	Receive Completion	Send Completion


Laurent Gardes

Stéphane Girard

Armelle Guillou

Weibull tail-distributions revisited: a new look at some tail estimators

Keywords: AMS Subject Classifications: 62G05, 62G20, 62G30 Weibull tail-distributions, extreme quantile, maximum domain of attraction, asymptotic normality

In this paper, we propose to include Weibull tail-distributions in a more general family of distributions. In particular, the considered model also encompasses the whole Fréchet maximum domain of attraction as well as log-Weibull tail-distributions. The asymptotic normality of some tail estimators based on the log-spacings between the largest order statistics is established in a unified way within the considered family. This result permits to understand the similarity between most estimators of the Weibull tail-coefficient and the Hill estimator. Some different asymptotic properties, in terms of bias, rate of convergence, are also highlighted.

Motivations

Weibull tail-distributions encompass a variety of light-tailed distributions, i.e. distributions in the Gumbel maximum domain of attraction, see [START_REF] Galambos | The Asymptotic theory of extreme order statistics[END_REF] for further details. Weibull tail-distributions include for instance Weibull, Gaussian, gamma and logistic distributions. Let us recall that a cumulative distribution function F has a Weibull tail if its associated survival function F = 1 -F satisfies the following property: There exists θ > 0 such that for all λ > 0,

lim t→∞ log F (λt) log F (t) = λ 1/θ . (1)
The parameter θ is called the Weibull tail-coefficient. We refer to [START_REF] Beirlant | Practical analysis of extreme values[END_REF] for a general account on Weibull tail-distributions and to [START_REF] Beirlant | Modeling large claims in non-life insurance[END_REF] for an application to the modeling of large claims in non-life insurance. Dedicated methods have been proposed to estimate the Weibull tail-coefficient since the relevant information is only contained in the extreme upper part of the sample denoted hereafter by X 1 , . . . , X n . A first direction was investigated in [START_REF] Berred | Record values and the estimation of the Weibull tail-coefficient[END_REF] where an estimator based on the record values is proposed. Another family of approaches [START_REF] Beirlant | Semiparametric lower bounds for tail index estimation[END_REF][START_REF] Beirlant | The mean residual life function at great age: Applications to tail estimation[END_REF][START_REF] Broniatowski | On the estimation of the Weibull tail coefficient[END_REF][START_REF] Dierckx | A new estimation method for Weibull-type tails based on the mean excess function[END_REF] consists of using the k n upper order statistics X n-kn+1,n ≤ . . . ≤ X n,n where (k n ) is an intermediate sequence of integers i.e. such that lim n→∞ k n = ∞ and lim n→∞ k n /n = 0.

(2)

More specifically, most recent estimators are based on the log-spacings between the k n upper order statistics [START_REF] Beirlant | Practical analysis of extreme values[END_REF][START_REF] Diebolt | Bias-reduced estimators of the Weibull tail-coefficient[END_REF][START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF][START_REF] Gardes | Estimation of the Weibull tail-coefficient with linear combination of upper order statistics[END_REF][START_REF] Girard | A Hill type estimate of the Weibull tail-coefficient[END_REF][START_REF] Goegebeur | Generalized kernel estimators for the Weibull-tail coefficient[END_REF][START_REF] Goegebeur | Goodness-of-fit testing for Weibull-type behavior[END_REF]. All these estimators are thus similar to the Hill statistics [START_REF] Hill | A simple general approach to inference about the tail of a distribution[END_REF] defined as

H n (k n ) = 1 k n -1 kn-1 i=1 log(X n-i+1,n ) -log(X n-kn+1,n ).
(3)

As an example, all three estimators proposed in [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF] are proportional to H n (k n ). This similarity may be surprising since H n (k n ) is dedicated to the estimation of the tail index γ for heavy-tailed distribution i.e. such that lim t→∞ F (λt) F (t) = λ -1/γ , for all λ > 0. This property characterizes distributions belonging to the Fréchet maximum domain of attraction and sometimes called Pareto-type distributions.

The main goal of this work is therefore to explain why statistics based on log-spacings could be efficient in estimating tail parameters of both Weibull-tail and Pareto-type distributions. To this end, we introduce a family of distributions, indexed by two parameters τ ∈ [0, 1] and θ > 0, which includes these two type of distributions. The first parameter τ allows to represent a large panel of distribution tails ranging from Weibull-type tails (τ = 0) to Pareto-type tails (τ = 1). The second parameter θ is the parameter to be estimated. It coincides with the Weibull tail-coefficient when τ = 0 and with the tail index when τ = 1.

An estimator θ n (k n ) of θ is then introduced for the new family of distributions and an estimator of extreme quantiles is derived. The asymptotic normality of these estimators is established in Section 3 in a unified way and illustrated on some simulated data in Section 4. Some concluding remarks are given in Section 5. Proofs are postponed to Section 6.

Model and estimators

Definition and first properties

Let us consider the family of survival distribution functions defined as

(A 1 (τ, θ)) F (x) = exp(-K ← τ (log H(x)
)) for x ≥ x * with x * > 0 and

• K τ (x) = x 1 u τ -1 du where τ ∈ [0, 1], • H an increasing function such that H ← (t) = inf{x, H(x) ≥ t} = t θ ℓ(t)
, where θ > 0 and ℓ is a slowly varying function i.e. ℓ(λx)/ℓ(x) → 1 as x → ∞ for all λ ≥ 1.

The function H ← is the so-called generalized inverse of H. Note that K ← τ coincides with the classical inverse since K τ is continuous. The expansion H ← (t) = t θ ℓ(t) is equivalent to supposing that H ← is regularly varying at infinity with index θ. This property is denoted by H ← ∈ R θ , see [START_REF] Bingham | Regular Variation[END_REF] for more details on regular variations theory. Let us first highlight that the tail heaviness of F is mainly driven by τ ∈ [0, 1] and secondarily by θ > 0: Proposition 1 Let Fτ1,θ1 and Fτ2,θ2 be two survival distribution functions satisfying respectively

(A 1 (τ 1 , θ 1 )) and (A 1 (τ 2 , θ 2 )). (i) If τ 1 < τ 2 then Fτ1,θ1 (x)/ Fτ2,θ2 (x) → 0 as x → ∞ for all (θ 1 , θ 2 ) ∈ (0, ∞) 2 . (ii) If τ 1 = τ 2 = τ and θ 1 < θ 2 then Fτ,θ1 (x)/ Fτ,θ2 (x) → 0 as x → ∞.
Thus, the larger is τ , the heavier is the tail. Let us consider the two extremal cases τ = 0 and τ = 1. Clearly, under (A 1 (0, θ)), F (x) = exp(-H(x)) is the survival function of a Weibull-tail distribution, see [START_REF] Arnold | A First course in order statistics[END_REF]. At the opposite, (A 1 (1, θ)) entails F (x) = e 1 /H(x) = x -1/θ l(x) where l is a slowly varying function. As a consequence, F belongs to the Fréchet maximum domain of attraction and θ coincides with the tail index. In view of the above remarks, intermediate values of τ ∈ (0, 1) correspond to distribution tails lighter than Pareto tails but heavier than Weibull tails. Indeed, we have F (x) = exp(-h(x)) with h(x) ∼ ((τ /θ) log x) 1/τ and thus h(x)/x β → 0 for all β > 0 while h(x)/ log(x) → ∞ as x → ∞, this property characterizing an "exponential type" distribution, see [START_REF] Harris | Gumbel re-visited -a new look at extreme value statistics applied to wind speeds[END_REF]. The next proposition provides a more precise characterization while examples are provided in Paragraph 2.2.

Proposition 2

(i) F verifies (A 1 (0, θ)) if and only if F is a Weibull-tail distribution function with Weibull tail-coefficient θ. (ii) If F verifies (A 1 (τ, θ)), τ ∈ [0,

Examples

In view of Proposition 2(i), Gaussian, gamma, Weibull, Benktander II, logistic and extreme-value distributions all verify (A 1 (0, θ)) since they are examples of Weibull tail-distributions (see [START_REF] Gardes | Estimation of the Weibull tail-coefficient with linear combination of upper order statistics[END_REF], Table 1). Examples of distributions verifying (A 1 (τ, θ)) with τ ∈ (0, 1) include some log-Weibull tail-distributions. Let us recall that a random variable Y is distributed from a log-Weibull taildistribution if log(Y ) follows a Weibull tail-distribution.

Proposition 3 Suppose that F verifies (A 1 (0, θ)) with θ ∈ (0, 1]. If, moreover, the slowly-varying function ℓ is differentiable and ℓ(t) → ℓ ∞ > 0 as t → ∞ then F (log .) verifies (A 1 (θ, θℓ ∞ )).

As an example, the standard log-normal distribution can be looked at as a log-Weibull taildistribution and thus verifies (A 1 (1/2, √ 2/2)). Similarly, the gamma distribution verifies (A 1 (0, 1)) and the log-gamma distribution belongs to the Fréchet maximum domain of attraction, see for instance [START_REF] Embrechts | Modelling extremal events[END_REF], Table 3

Definition of the estimators

Denoting by (k n ) an intermediate sequence of integers (see [START_REF] Asimit | Pitfalls in using Weibull tailed distributions[END_REF]), the following estimator of θ is considered:

θ n (k n ) = 1 µ 1,τ (log(n/k n )) 1 k n -1 kn-1 i=1 (log(X n-i+1,n ) -log(X n-kn+1,n )), (4)
with, for all t > 0 and q ∈ N \ {0},

µ q,τ (t) = ∞ 0 (K τ (x + t) -K τ (t)) q e -x dx.
A crucial point is that the estimator (4) essentially consists in averaging the log-spacings between the upper-order statistics. Even more strongly, θ n (k n ) only differs from the Hill statistics (3) by a non-random normalizing sequence:

θ n (k n ) = H n (k n )/µ 1,τ (log(n/k n ))
. This similarity can be intuitively understood by studying the log-spacing between two quantiles x u and x v of F , with 0 < u < v ≤ 1. Under (A 1 (τ, θ)) we have

log x u -log x v = θ (K τ (-log u) -K τ (-log v)) + log ℓ(exp K τ (-log u)) ℓ(exp K τ (-log v)) . (5)
Now, since ℓ is a slowly-varying function, if the orders u and v of the quantiles are small enough, the second term can be neglected in the right-hand side of (5) to obtain

log x u -log x v ≃ θ (K τ (-log u) -K τ (-log v)) , (6)
which shows that log-spacings are approximately proportional to θ. Since this key property holds for all τ ∈ [0, 1], it is thus shared by Pareto-type, Weibull tail and log-Weibull tail-distributions. Note that this property can be checked graphically on a sample by drawing a quantile-quantile plot. It consists in plotting the pairs (K τ (log(n/i)), log(X n-i+1,n )) for i = 1, . . . , k n . From ( 6), the graph should be approximately linear. Following the same ideas, an estimator of the extreme quantile x pn can be deduced from (4) by:

x pn = X n-kn+1,n exp θ n (k n ) (K τ (log(1/p n )) -K τ (log(n/k n ))) . (7)
Recall that an extreme quantile x pn of order p n is defined by

x pn = F ← (p n ) with p n → 0 as n → ∞.
For instance, if np n → 0 then x pn is larger than the maximum observation X n,n of the sample (with probability tending to one). This requires to extrapolate sample results to areas where no data are observed and occurs in reliability [START_REF] Ditlevsen | Distribution Arbitrariness in Structural Reliability, Structural Safety and Reliability[END_REF], hydrology [START_REF] Smith | Estimating the upper tail of flood frequency distributions[END_REF], finance [START_REF] Embrechts | Modelling extremal events[END_REF],...

Asymptotic properties

We show in the next paragraph that the asymptotic normality of θ n (k n ) and x pn can be established for all τ ∈ [0, 1] in a unified way. In this sense, the asymptotic behavior of these estimators is more a consequence of the log-spacings property than of a tail behavior (which can be exponential as well as polynomial). Paragraphs 3.2 and 3.3 illustrate our general result on the two extremal cases τ = 0 and τ = 1.

Main results

To establish the asymptotic normality of θ n (k n ), a second-order condition on ℓ is necessary:

(A 2 (ρ)) There exist ρ < 0 and b(x) → 0 such that uniformly locally on λ ≥ λ 0 > 0 log ℓ(λx) ℓ(x) ∼ b(x)K ρ (λ), when x → ∞.
It can be shown that necessarily |b| ∈ R ρ (see [START_REF] Geluk | Regular Variation, Extensions and Tauberian Theorems[END_REF]). The second order parameter ρ < 0 tunes the rate of convergence of ℓ(λx)/ℓ(x) to 1. The closer is ρ to 0, the slower is the convergence. Condition (A 2 (ρ)) is the cornerstone in all the proofs of asymptotic normality for extreme value estimators. It is used in [START_REF] Beirlant | Tail index estimation and an exponential regression model[END_REF][START_REF] Häusler | On asymptotic normality of Hill's estimator for the exponent of regular variation[END_REF][START_REF] Hill | A simple general approach to inference about the tail of a distribution[END_REF] to prove the asymptotic normality of several estimators of the extreme value index.

Theorem 1 Suppose that (A 1 (τ, θ)) and (A 2 (ρ)) hold. Let (k n ) be an intermediate sequence such that k n b(exp K τ (log(n/k n ))) → λ. (8)
Then, introducing a τ,ρ = 1 if τ ∈ [0, 1) and a 1,ρ = 1/(1ρ), we have

k n θ n (k n ) -θ -a τ,ρ b(exp K τ (log(n/k n ))) d -→ N (0, θ 2 ). ( 9
)
It appears that the asymptotic variance of θ n (k n ) given by AV = θ 2 /k n is independent of τ . In particular, it remains constant whatever the maximum domain of attraction of F . The asymptotic squared bias is given by ASB [START_REF] Arnold | A First course in order statistics[END_REF] with a jump at τ = 1. These remarks are illustrated on simulated data in Section 4. The next result allows us to establish the rate of convergence of θ n (k n ) to θ in [START_REF] Bingham | Regular Variation[END_REF].

(τ, ρ) = a 2 τ,ρ b 2 (exp K τ (log(n/k n ))). If b 2 is ultimately decreasing, then ASB is a decreasing function of τ ∈ [0,
Proposition 4 Condition (8) with λ = 0 implies log(k n ) = -2ρa τ,2ρ K τ (log n)(1 + o(1)).
The rate of convergence is thus of order exp(-ρa τ,2ρ K τ (log n)(1 + o(1))). A geometrical rate of convergence is obtained only in the Fréchet maximum domain of attraction, τ = 1 yields (1) which is consistent with the conclusions of [START_REF] De Haan | Comparison of tail index estimators[END_REF]. Weibull tail-distributions give rise to logarithmic rates of convergence, τ = 0 yields (1) which is consistent with the results of [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF]. More generally, the heavier is the tail, the better the rate of convergence is. The next result provides an extension of Statement 1 in [START_REF] Asimit | Pitfalls in using Weibull tailed distributions[END_REF], which was initially proved only for Weibull tail-distributions (τ = 0). Proposition 5 Suppose condition [START_REF] Berred | Record values and the estimation of the Weibull tail-coefficient[END_REF]

√ k n = n -ρ/(1-2ρ)+o
√ k n = (log n) -ρ+o
holds with λ = 0. If τ ∈ [0, 1/2] then ASB(τ, ρ) = c τ,ρ b 2 (exp K τ (log n))(1 + o(1)), where c τ,ρ = 1 if τ ∈ [0, 1/2) and c 1/2,ρ = exp(8ρ 2 ).
It follows that, when τ ∈ [0, 1/2], the first order of the asymptotic bias is asymptotically independent of k n . As a consequence, the asymptotic mean-squared error defined as ASB(τ, ρ) + AV is eventually decreasing with respect to k n . This remark, already made in [START_REF] Asimit | Pitfalls in using Weibull tailed distributions[END_REF] in the particular case τ = 0, is only of theoretical interest. Indeed, in finite sample situations, condition [START_REF] Berred | Record values and the estimation of the Weibull tail-coefficient[END_REF] does not hold and the empirical mean-squared error is a convex function of k n , see for instance [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF]. Now, the asymptotic normality of the extreme quantile estimator (7) can be deduced from Theorem 1: Theorem 2 Suppose the assumptions of Theorem 1 hold with λ = 0. If, moreover,

(log(n/k n )) 1-τ (K τ (log(1/p n )) -K τ (log(n/k n ))) → ∞ (10) then, √ k n K τ (log(1/p n )) -K τ (log(n/k n )) x pn x pn -1 d -→ N (0, θ 2 ).
Let us now focus on the two particular cases τ = 0 (Weibull tail-distributions) and τ = 1 (Fréchet maximum domain of attraction).

Application to Weibull tail-distributions

If τ = 0, the estimator (4) coincides with θ

(1) n introduced in [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF], and

x pn = X n-kn+1,n log(1/p n ) log(n/k n ) b θn(kn)
is the estimator proposed in [START_REF] Gardes | Estimating extreme quantiles of Weibull tail-distributions[END_REF]. As a consequence of Theorem 1 and Theorem 2, we obtain:

Corollary 1 Suppose that (A 1 (0, θ)) and (A 2 (ρ)) hold. Let (k n ) be an intermediate sequence such that √ k n b(log(n/k n )) → 0. Then, k n ( θ n (k n ) -θ) d -→ N (0, θ 2 ). If, moreover log(n/k n ) (log log(1/p n ) -log log(n/k n )) → ∞ (11) then, √ k n log log(1/p n ) -log log(n/k n ) x pn x pn -1 d -→ N (0, θ 2 ).
This result is very similar to Corollary 3.1 in [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF] except that condition [START_REF] Diebolt | Bias-reduced estimators of the Weibull tail-coefficient[END_REF] is weaker than the one used in the above mentioned paper. Let us also note that estimators θ

n and θ

n in [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF] can be respectively deduced from θ n by approximating µ 1,0 by a Riemann's sum or using the first order approximation µ 1,0 (t) ∼ 1/t as t → ∞ given in Lemma 2(i).

Application to the Fréchet maximum domain of attraction

Letting τ = 1 and remarking that µ q,1 (t) = q! for all t > 0 and q ∈ N \ {0}, the estimator (4) coincides with (3) which is the Hill estimator [START_REF] Hill | A simple general approach to inference about the tail of a distribution[END_REF] of the tail index. Besides,

x pn = X n-kn+1,n k n np n b θn(kn)
is the Weissman estimator [START_REF] Weissman | Estimation of parameters and large quantiles based on the k largest observations[END_REF]. A straightforward application of the above theorems gives back the classical results:

Corollary 2 Suppose that (A 1 (1, θ)) and (A 2 (ρ)) hold. Let (k n ) be an intermediate sequence such that √ k n b(n/k n ) → 0. Then, k n ( θ n (k n ) -θ) d -→ N (0, θ 2 ). If, moreover k n /(np n ) → ∞ then, √ k n log(k n /(np n )) x pn x pn -1 d -→ N (0, θ 2 ).

Illustration on simulations

The section is dedicated to the illustration of the conclusions drawn from Theorem 1 on simulated data. To this end, we consider a cumulative distribution function F θ,τ,ρ verifying (A 1 (τ, θ)) and (A 2 (ρ)) with θ = 1/2, τ ∈ {0, 1/2, 1} and ρ ∈ {-1/2, -1/4}. More specifically, the slowly-varying function is given by

ℓ(x) = 1 - θ ρ (1 + x) ρ 1 + 1 x θ .
Following Proposition 2(i), it appears that the case τ = 0 corresponds to a Weibull tail-distribution (with Weibull tail-coefficient 1/2) similar to a Gaussian distribution. When τ = 1/2, in view of Paragraph 2.1, F (x) = exp{-(log x) 2 (1 + o(1))}, the distribution has a tail behavior similar to the log-normal distribution. Finally, Proposition 2(iii) shows that, when τ = 1, the distribution belongs to the Fréchet maximum domain of attraction with tail-index 1/2.

For each considered combination of τ and ρ, N = 500 samples (X n,j ) j=1,...,N of size n = 500 were simulated from F 1/2,τ,ρ . On each sample (X n,j ), the estimate θn,j is computed for k = 2, . . . , 250, the associated empirical squared bias ESB and empirical variance EV plots are built by plotting the pairs k, ( θ( 1)

n (k) -θ) 2 and k, θ(2) n (k) -( θ(1) n (k)) 2 where for i ∈ {1, 2}, θ(i) n (k) = 1 N N j=1 ( θn,j (k)) i .
The empirical squared bias and the empirical variance are depicted on Figure 1 and Figure 2 respectively. Both graphs are represented on the same scale for the sake of comparison. As expected, the squared bias, for a fixed value of k, is an increasing function of ρ and a decreasing function of τ . At the opposite, the variance seems to be independent of ρ and is not much dependent of τ .

Concluding remarks

As illustrated in the previous sections, the model (A 1 (τ, θ)) provides a new tool for the analysis of tail estimators based on log-spacings. It allows us to encompass Weibull tail-distributions in a more general framework and thus to explain why their dedicated tail estimators are very similar to Hill or Weissman statistics. The next step would be to estimate the parameter τ . For instance, one can consider the following estimator based on the log-spacing between two Hill statistics

τ n = 1 + log H n (k ′ n ) -log H n (k n ) log log(n/k ′ n ) -log log(n/k n ) , where (k n ) and (k ′ n ) are two intermediate sequences such that lim inf n→∞ log(n/k ′ n ) log(n/k n ) > 1.
Let us note that

(log log(n/k ′ n ) -log log(n/k n ))( τ n -τ ) = log( θ n (k ′ n )/θ) -log( θ n (k n )/θ) + log µ 1,τ (log(n/k ′ n )) log τ -1 (n/k ′ n ) -log µ 1,τ (log(n/k n )) log τ -1 (n/k n ) .
This implies that the consistency of τ n is a simple consequence of Theorem 1 and Lemma 2(i) whereas the asymptotic distribution is much more difficult to handle as it requires the joint distribution of θ n (k ′ n ) and θ n (k n ). Also in practice, the choice of the parameters k n and k ′ n is an open question. These two points are currently under investigation. Other extensions are possible, among others bias correction based on the estimation of the secondorder parameter [START_REF] Gomes | A class of asymptotically unbiased semi-parametric estimators of the tail index[END_REF][START_REF] Gomes | Bias reduction of a tail index estimator through an external estimation of the second-order parameter[END_REF]. To this end, an exponential regression model for these tail distributions extending [START_REF] Beirlant | Tail index estimation and an exponential regression model[END_REF][START_REF] Diebolt | Bias-reduced estimators of the Weibull tail-coefficient[END_REF][START_REF] Diebolt | Bias-reduced extreme quantiles estimators of Weibull tail-distributions[END_REF][START_REF] Feuerverger | Estimating a tail exponent by modelling departure from a Pareto distribution[END_REF] would be of interest. We also plan to adapt our results to the case τ > 1 and to investigate the possible links with super-heavy tails [START_REF] Alves | A test procedure for detecting super heavy tails[END_REF]. Finally, this work could be further extended to random variables Y = ψ(X) where X has a parent distribution satisfying (A 1 (τ, θ)). For instance, choosing ψ(x) = x * -1/x would allow to consider distributions (with finite endpoint x * ) in the Weibull maximum domain of attraction. This may help for including the negative Hill estimator (see for instance [START_REF] Falk | Some best parameter estimates for distributions with finite endpoint[END_REF] or [START_REF] De Haan | Extreme Value Theory: An Introduction[END_REF], paragraph 3.6.2) in our framework.

Proofs

We first give some preliminary lemmas. Their proofs are postponed to the appendix.

Preliminary lemmas

The first lemma provides some uniform approximations based on (A 1 (τ, θ)) and (A 2 (ρ)).

Lemma 1 If (A 1 (τ, θ)) and (A 2 (ρ)) hold then sup λ≥1 ℓ(λx) ℓ(x) -1 -b(x)K ρ (λ) = o(b(x)), when x → ∞.
Let us define for all q ∈ N \ {0}, τ ∈ [0, 1] and t > 0, σ 2 q,τ (t) = µ 2q,τ (t)µ 2 q,τ (t). The following lemma is of analytical nature. It provides first-order expansions which will be useful in the sequel.

Lemma 2 For all q ∈ N \ {0} and τ ∈ [0, 1], when t → ∞:

(i) µ q,τ (t) ∼ q! t (τ -1)q , (ii) σ 2 q,τ (t)/µ 2 q,τ (t) → (2q)!/(q!) 2 -1, (iii) µ ′ 1,τ (t)/µ 1,τ (t) → 0.

The next lemma presents an expansion of θ n (k n ).

Lemma 3 Let (k n ) be an intermediate sequence. Then, under (A 1 (τ, θ)), the following expansions hold:

θ n (k n ) = 1 µ 1,τ (log(n/k n )) θθ (1) n,1 (E n-kn+1,n ) + θ n,2 (E n-kn+1,n ) ,
with, for all q ∈ N \ {0},

θ (q) n,1 (t) = 1 k n -1 kn-1 i=1 (K τ (F i + t) -K τ (t)) q , θ n,2 (t) = 1 k n -1 kn-1 i=1 log ℓ(exp K τ (F i + t)) ℓ(exp K τ (t)) ,
and where E n-kn+1,n is the (nk n + 1)th order statistic associated to n independent standard exponential variables and {F 1 , . . . , F kn-1 } are independent standard exponential variables and independent from E n-kn+1,n .

The asymptotic behavior of the (nk n + 1)th standard exponential order statistic is described in the following lemma.

Lemma 4 Let (k n ) be an intermediate sequence. Then, for all differentiable function g, we have

k n (g(E n-kn+1,n ) -g(log(n/k n ))) = O P (1)g ′ (log(n/k n )(1 + o P (1))).
The next two lemmas provide the key results for establishing the asymptotic distribution of θ n (k n ). They describe the asymptotic behavior of the random terms appearing in Lemma 3.

Lemma 5 Let (k n ) be an intermediate sequence. Then, for all q ∈ N \ {0}, √ k n σ q,τ (E n-kn+1,n ) θ (q) n,1 (E n-kn+1,n ) -µ q,τ (E n-kn+1,n ) d -→ N (0, 1).
Lemma 6 Suppose that (A 1 (τ, θ)) and (A 2 (ρ)) hold. Let (k n ) be an intermediate sequence. Then,

θ n,2 (E n-kn+1,n ) = b(exp K τ (E n-kn+1,n ))θ n,3 (E n-kn+1,n )(1 + o P (1)),
where

θ n,3 (E n-kn+1,n ) -θ (1) n,1 (E n-kn+1,n ) ≤ - ρ 2 θ (2) n,1 (E n-kn+1,n ). Moreover, if τ = 1, then θ n,3 (E n-kn+1,n ) P -→ 1/(1 -ρ).

Proofs of the main results

Proof of Proposition 1 -Assumptions (A 1 (τ 1 , θ 1 )) and

(A 1 (τ 2 , θ 2 )) entail Fτ1,θ1 (x) Fτ2,θ2 (x) = exp -K ← τ1 (log H 1 (x)) 1 - K ← τ2 (log H 2 (x)) K ← τ1 (log H 1 (x)) , (12)
where

H 1 ∈ R 1/θ1 and H 2 ∈ R 1/θ2
. As a consequence, for all q ∈ {1, 2}, log H q (x) ∼ log(x)/θ q when x → ∞, see [START_REF] Bingham | Regular Variation[END_REF], Proposition 1.3.6. Let us first prove (i): 0 < τ 1 < τ 2 implies

K ← τq (log H q (x)) ∼ (τ q /θ q ) 1/τq (log x) 1/τq → ∞, (13)
and thus

K ← τ2 (log H 2 (x)) K ← τ1 (log H 1 (x)) ∼ (τ 2 /θ 2 ) 1/τ2 (τ 1 /θ 1 ) 1/τ1 (log x) 1/τ2-1/τ1 → 0. ( 14
)
Collecting ( 12), ( 13) and ( 14) gives the result: Fτ1,θ1 (x)/ Fτ2,θ2 (x) → 0 as x → ∞. Similarly, if

τ 1 = 0, then K ← τ2 (log H 2 (x)) K ← 0 (log H 1 (x)) ∼ (τ 2 /θ 2 ) 1/τ2 H 1 (x) (log x) 1/τ2 → 0,
which concludes the first part of the proof. Let us now focus on (ii) and suppose

θ 1 < θ 2 . If τ > 0 then K ← τ (log H 2 (x)) K ← τ (log H 1 (x)) → θ 1 θ 2 1/τ < 1, as x → ∞, while, if τ = 0, K ← 0 (log H 2 (x)) K ← 0 (log H 1 (x)) = H 2 (x) H 1 (x) → 0,
as x → ∞. In both cases, for x large enough,

1 - K ← τ (log H 2 (x)) K ← τ (log H 1 (x)) > 0, ( 15
)
and collecting ( 12), ( 13) and ( 15) concludes the proof: Fτ,θ1 (x)/ Fτ,θ2 (x) → 0 as x → ∞.

Proof of Proposition 2 -Proofs of (i) and (iii) are straightforward consequences of Paragraph 2.1. Let us focus on (ii). In view of the characterization (3.35) in [START_REF] Embrechts | Modelling extremal events[END_REF] of the Gumbel maximum domain of attraction, it is sufficient to prove that there exists a positive function a, differentiable with a ′ (t) → 0 as t → ∞, such that

F (x) = exp - x x * dt a(t) , x ≥ x * . ( 16
)
Letting a = 1/(K ← τ (log H)) ′ , it thus remains to prove that a ′ (t) → 0 as t → ∞ for all τ ∈ [0, 1). To this end, let us remark that

a ′ (t) = 1 K ← τ (log H(t)) τ -1 + 1 - H ′′ (t)H(t) H ′ (t) 2 (1 + τ log H(t)) = 1 K ← τ (log H(t)) (τ -1 + (θ + o(1))(1 + τ log H(t))), since H ′ ∈ R 1/θ-1 implies H ′′ (t)H(t)/H ′ (t) 2 → 1 -θ as t → ∞.
Two cases arise:

• If τ ∈ (0, 1) then a ′ (t) ∼ θ(τ log H(t)) 1-1/τ → 0 as t → ∞.
• Otherwise, when τ = 0, we have a

′ (t) = (θ -1 + o(1))/H(t) → 0 as t → ∞.
In both situations, the conclusion follows.

Proof of Proposition 3 -Let us suppose that F verifies

(A 1 (0, θ)) with θ ∈ (0, 1]. Then, introducing W (x) = exp K θ (H(log x)), we have F (log x) = exp(-K ← θ (log W (x))). It thus remains to prove that W ← ∈ R θℓ∞ . Simple calculations show that W ← (t) = exp {H ← (K ← θ (log t))} = exp {(1 + θ log t)ℓ (K ← θ (log t))} = e ℓ∞ t θℓ∞ ϕ(t),
where we have defined ϕ(t) = ψ(log t) with ψ(x

) = exp{(1 + θx)[ℓ(K ← θ (x)) -ℓ ∞ ]}. As a conse- quence, t(log ϕ(t)) ′ = (log ψ) ′ (log t) = θ(ℓ(K ← θ (log t)) -ℓ ∞ ) + K ← θ (log t)ℓ ′ (K ← θ (log t)) = o(1),
since, from [START_REF] Bingham | Regular Variation[END_REF], p. 15, uℓ ′ (u)/ℓ(u) → 0 as u → ∞. Using again [START_REF] Bingham | Regular Variation[END_REF], p. 15, it follows that ϕ is a slowly varying function. Thus, W ← ∈ R θℓ∞ and F (log .) verifies (A 1 (θ, θℓ ∞ )).

Proof of Theorem 1 -Lemma 5 states that for q ∈ {1, 2},

√ k n σ q,τ (E n-kn+1,n ) θ (q) n,1 (E n-kn+1,n ) -µ q,τ (E n-kn+1,n ) = ξ (q) n where ξ (q) n d
-→ N (0, 1). Then, by Lemma 3,

k n ( θ n (k n ) -θ -a τ,ρ b(exp K τ (log(n/k n ))) = k n θ µ 1,τ (E n-kn+1,n ) µ 1,τ (log(n/k n )) -1 + θ σ 1,τ (E n-kn+1,n ) µ 1,τ (log(n/k n )) ξ (1) n + k n θ n,2 (E n-kn+1,n ) µ 1,τ (log(n/k n )) -a τ,ρ b(exp K τ (log(n/k n )) def = T (1) n + T (2) n + T (3) n ,
and the three terms are studied separately. First, applying Lemma 4 to g = µ 1,τ yields

T (1) n = O P (1) µ ′ 1,τ (log(n/k n )(1 + o P (1))) µ 1,τ (log(n/k n )) = o P (1), (17)
in view of Lemma 2(i, iii). Second,

T (2) n = σ 1,τ (E n-kn+1,n ) µ 1,τ (E n-kn+1,n ) 1 + T (1) n θ √ k n θξ (1) n = σ 1,τ (E n-kn+1,n ) µ 1,τ (E n-kn+1,n ) θξ (1) n (1 + o P (1)) and, from Lemma 2(ii), σ 1,τ (E n-kn+1,n )/µ 1,τ (E n-kn+1,n ) P -→ 1.
As a preliminary conclusion,

T (2) n = θξ (1) n (1 + o P (1)). (18)
From Lemma 6, T

can be expanded as

T (3) n = k n b(exp K τ (log(n/k n ))) b(exp K τ (E n-kn+1,n )) b(exp K τ (log(n/k n ))) θ n,3 (E n-kn+1,n ) µ 1,τ (log(n/k n )) (1 + o P (1)) -a τ,ρ = λ b(exp K τ (E n-kn+1,n )) b(exp K τ (log(n/k n ))) θ n,3 (E n-kn+1,n ) µ 1,τ (log(n/k n )) (1 + o P (1)) -a τ,ρ (1 + o(1)).
Introducing T as well, and consequently

= K τ (E n-kn+1,n ) -K τ (log(n/k n )) and applying Lemma 4 with g = K τ yield exp T (3,1) n = exp O P (1) (log(n/k n )) τ -1 √ k n P -→ 1, (3,1) n
T (3) n = λ θ n,3 (E n-kn+1,n ) µ 1,τ (log(n/k n )) (1 + o P (1)) -a τ,ρ (1 + o(1)) = λ θ n,3 (E n-kn+1,n ) µ 1,τ (E n-kn+1,n ) 1 + T (1) n θ √ k n (1 + o P (1)) -a τ,ρ (1 + o(1)) = λ θ n,3 (E n-kn+1,n ) µ 1,τ (E n-kn+1,n ) (1 + o P (1)) -a τ,ρ (1 + o(1)),
from [START_REF] Falk | Some best parameter estimates for distributions with finite endpoint[END_REF]. Two situations occur. If τ = 1, then, in view of Lemma 6, θ n,3 (E n-kn+1,n )

P -→ a 1,ρ = 1/(1 -ρ), µ 1,1 (E n-kn+1,n ) = 1 and thus T (3) n P -→ 0. If τ ∈ [0, 1), T (3)
n can be rewritten as

T (3) n = λ (T (3,2) n + T (3,3) n )(1 + o P (1)) -1 (1 + o(1)),
where

T (3,2) n def = θ (1) n,1 (E n-kn+1,n ) µ 1,τ (E n-kn+1,n ) = 1 + σ 1,τ (E n-kn+1,n ) µ 1,τ (E n-kn+1,n ) ξ (1) n √ k n = 1 + o P (1)
since K ′ τ is regularly-varying. As a consequence,

∆ n = exp{2ρK τ (log n)K ′ τ (log n)(1 + o(1))} and thus ∆ n → 1 if τ ∈ [0, 1/2) or ∆ n → exp(4ρ) if τ = 1/2. Since b 2 is regularly varying with index 2ρ it follows that ASB(τ, ρ) = b 2 (exp K τ (log n)) b 2 (∆ n exp K τ (log n)) b 2 (exp K τ (log n)) = c τ,ρ b 2 (exp K τ (log n))(1 + o(1)),
and the conclusion follows.

Proof of Theorem 2 -From ( 7), one can infer that

log x pn -log x pn = log(X n-kn+1,n ) -log F ← (k n /n) + ( θ n (k n ) -θ) (K τ (log(1/p n )) -K τ (log(n/k n ))) + log ℓ (exp K τ (log(n/k n ))) ℓ (exp K τ (log(1/p n ))) def = Q (1) n + Q (2) n + Q (3) n .
The three terms are studied separately. First, note that in view of (A 1 (τ, θ)) and (A 2 (ρ)), Q

n can be expanded as

Q (1) n = log H ← (exp K τ (E n-kn+1,n )) -log H ← (exp K τ (log(n/k n ))) = θ(K τ (E n-kn+1,n ) -K τ (log(n/k n ))) + log ℓ(exp K τ (E n-kn+1,n )) ℓ(exp K τ (log(n/k n ))) def = θT (3,1) n + Q (1,2) n ,
where T

(3,1) n is defined in the proof of Theorem 1 as

T (3,1) n = K τ (E n-kn+1,n ) -K τ (log(n/k n )) = O P (1) (log(n/k n )) τ -1 √ k n , (22)
in view of [START_REF] Alves | A test procedure for detecting super heavy tails[END_REF]. Moreover,

Q (1,2) n def = log ℓ(λ n x n ) -log ℓ(x n ), where x n = exp K τ (log(n/k n )) → ∞ and λ n = exp T (3,1) n P
-→ 1. Thus, from (A 2 (ρ)) we have

Q (1,2) n = b(exp K τ (log(n/k n )))K ρ (λ n )(1 + o P (1)) = b(exp K τ (log(n/k n ))) log(λ n )(1 + o P (1)) = O P (1)b(exp K τ (log(n/k n ))) (log(n/k n )) τ -1 √ k n ,
in view of [START_REF] Gardes | Comparison of Weibull tail-coefficient estimators[END_REF]. Since b(x) → 0 as x → ∞, it follows that

Q (1,2) n = o P (log(n/k n )) τ -1 √ k n , entailing √ k n K τ (log(1/p n )) -K τ (log(n/k n )) Q (1) n = O P (log(n/k n )) τ -1 K τ (log(1/p n )) -K τ (log(n/k n ))
= o P (1),

Appendix: Proof of auxiliary results

Proof of Lemma 1 -From (A 1 (τ, θ)) and (A 2 (ρ)), it is easy to infer that, for any constant C > 0, we have 1

Cb(x) H ← (λx) -H ← (x) θH ← (x)(1 + b(x)/θ) - λ θ -1 θ = λ θ Cθ K ρ (λ) - 1 Cθ λ θ -1 θ + o(1) = θ + ρ Cθ 1 ρ [K θ+ρ (λ) -K θ (λ)] + o(1).
Then, choosing C such that (θ + ρ)/( Cθ) = 1, a direct application of Lemma 5.2 in [START_REF] Draisma | A Bootstrap-based method to achieve optimality in estimating the extreme-value index[END_REF] yields, for any ε > 0 and λ ≥ 1,

min(1, λ -ρ-ε ) ℓ(λx) ℓ(x) -1 -b(x)K ρ (λ) - 1 θ b 2 (x) [K ρ (λ) -K -θ (λ)] ≤ ε Cθ|b(x)| |1 + b(x)/θ| min(1, λ -ρ-ε ) λ -θ + 1 + 2λ ρ+ε ≤ 4ε Cθ|b(x)| min(1, λ -ρ-ε ) 1 + λ ρ+ε ≤ 8ε Cθ|b(x)| for x large enough. Moreover, letting 0 < ε < -ρ yields sup λ≥1 ℓ(λx) ℓ(x) -1 -b(x)K ρ (λ) - 1 θ b 2 (x) [K ρ (λ) -K -θ (λ)] = o(b(x)). (23)
Besides, K ρ (λ) -K -θ (λ) is bounded when ρ < 0, and therefore ( 23) can be simplified as

sup λ≥1 ℓ(λx) ℓ(x) -1 -b(x)K ρ (λ) = o(b(x)), as x → ∞,
and the conclusion follows.

Proof of Lemma 2 -(i) Let us consider for t > 1 and q ∈ N \ {0},

Q q (t) = ∞ 0 K τ (x + t) -K τ (t) K ′ τ (t) q e -x dx.
There exists η ∈ (0, 1) such that

K τ (x + t) -K τ (t) xK ′ τ (t) = 1 + ηx t τ -1 ≤ 1.
Thus, Lebesgue Theorem implies that

lim t→∞ Q q (t) = ∞ 0 lim t→∞ 1 + ηx t q(τ -1)
x q e -x dx = ∞ 0

x q e -x dx = q! which concludes the first part of the proof.

(ii) is a straightforward consequence of (i).

(iii) We have

µ ′ 1,τ (t) = ∞ 0 (K ′ τ (x + t) -K ′ τ (t)) e -x dx = ∞ 0 K ′ τ (x + t)e -x dx -K ′ τ (t) = ∞ 0 K τ (x + t)e -x dx -K τ (t) -K ′ τ (t) = µ 1,τ (t) -t τ -1 .
Finally, (i) states that t τ -1 /µ 1,τ (t) → 1 as t → ∞ which entails µ ′ 1,τ (t)/µ 1,τ (t) → 0 as t → ∞. Proof of Lemma 3 -Recall that

θ n = 1 µ 1,τ (log(n/k n )) 1 k n -1 kn-1 i=1 (log(X n-i+1,n ) -log(X n-kn+1,n )) d = 1 µ 1,τ (log(n/k n )) 1 k n -1 kn-1 i=1 log H ← (exp K τ (E n-i+1,n )) H ← (exp K τ (E n-kn+1,n )) ,
where E 1,n , . . . , E n,n are ordered statistics generated by n independent standard exponential random variables. The Rényi representation of the Exp(1) ordered statistics (see [START_REF] Arnold | A First course in order statistics[END_REF], p. 72) yields

{E n-i+1,n } i=1,...,kn-1 d = {F kn-i,kn-1 + E n-kn+1,n } i=1,...,kn-1 , (24)
where {F 1,kn-1 , . . . , F kn-1,kn-1 } are ordered statistics independent from E n-kn+1,n and generated by k n -1 independent standard exponential variables {F 1 , . . . , F kn-1 }. We thus have

θ n (k n ) d = 1 µ 1,τ (log(n/k n )) 1 k n -1 kn-1 i=1 log H ← (exp K τ (F kn-i,kn-1 + E n-kn+1,n )) H ← (exp K τ (E n-kn+1,n ))) d = 1 µ 1,τ (log(n/k n )) 1 k n -1 kn-1 i=1 log H ← (exp K τ (F i + E n-kn+1,n )) H ← (exp K τ (E n-kn+1,n )) d = 1 µ 1,τ (log(n/k n )) θθ (1)
n,1 (E n-kn+1,n ) + θ n,2 (E n-kn+1,n ) in view of (A 1 (τ, θ)) and the conclusion follows.

Proof of Lemma 4 -A first order expansion of the function g leads to, Proof of Lemma 5 -Let us introduce for all t ≥ 1 and q ∈ N \ {0}, S (q) n (t) = (k n -1) 1/2 σ q,τ (t) (θ

(q)
n,1 (t)µ q,τ (t)) = (k n -1) -1/2 σ q,τ (t)

kn-1 i=1 Y (q) i (t),
where Y (q) i (t) def = (K τ (F i + t) -K τ (t)) qµ q,τ (t), i = 1, . . . , k n -1 are centered, independent and identically distributed random variables with variance σ 2 q,τ (t). Clearly, in view of the Central Limit Theorem, for all t ≥ 1 and q ∈ N \ {0}, S (q) n (t) converges in distribution to a standard Gaussian distribution. Our goal is to prove that, for all x ∈ R and q ∈ N \ {0}, P(S (q) n (E n-kn+1,n ) ≤ x) → Φ(x) as n → ∞, where Φ is the cumulative distribution function of the standard Gaussian distribution. Lemma 2(i) implies that for all ε ∈ (0, 1), and r ∈ N \ {0}, there exists T ε ≥ 1 such that for all t ≥ T ε ,

(1ε) r! t r(τ -1) ≤ µ r,τ (t) ≤ (1 + ε) r! t r(τ -1) .

Furthermore, for x ∈ R, P(S (q) n (E n-kn+1,n ) ≤ x) -Φ(x) = Tε 0 (P(S (q) n (t) ≤ x) -Φ(x))h n (t)dt + ∞ Tε (P(S (q) n (t) ≤ x) -Φ(x))h n (t)dt

def = A n + B n ,
where h n is the density of the random variable E n-kn+1,n . First, let us focus on the term A n . We have, |A n | ≤ 2 P(E n-kn+1,n ≤ T ε ).

Since E n-kn+1,n / log(n/k) P -→ 1 (see [START_REF] Girard | A Hill type estimate of the Weibull tail-coefficient[END_REF], Lemma 1), it is easy to show that A n → 0. Now, let us consider the term B n . For all t ≥ T ε , E(|Y (q) 1 (t)| 3 ) ≤ E ((K τ (F 1 + t) -K τ (t)) q + µ q,τ (t)) 3 = µ 3q,τ (t) + 3µ q,τ (t)µ 2q,τ (t) + 4µ 3 q,τ (t) ≤ C 1 (ε) t 3q(τ -1) < ∞,

  since τ ∈ [0, 1]. Therefore, b being regularly varying, b(exp K τ (E n-kn+1,n )/b(exp K τ (log(n/k n )) P -→ 1

k

  n (g(E n-kn+1,n )g(log n/k n ))) = k n (E n-kn+1,nlog(n/k n ))g ′ (η n ), with ηn ∈ [min (E n-kn+1,n , log(n/k n )) , max (E n-kn+1,n , log(n/k n ))]. Now, Lemma 1 in [25] shows that √ k n (E n-kn+1,nlog(n/k n )) d -→ N (0, 1) which implies that ηn = log(n/k n )(1 + o P (1)) and the result follows.

Figure 1 :

 1 Figure 1: Empirical squared bias as a function of k obtained with θ n (k n ) computed on 500 samples of size 500 from F 1/2,τ,ρ . Up: ρ = -1/2, down: ρ = -1/4, solid line: τ = 1, dashed line: τ = 1/2, dotted line: τ = 0.

Figure 2 :

 2 Figure 2: Empirical variance as a function of k obtained with θ n (k n ) computed on 500 samples of size 500 from F 1/2,τ,ρ . Up: ρ = -1/2, down: ρ = -1/4, solid line: τ = 1, dashed line: τ = 1/2, dotted line: τ = 0.

.4.2. Finally, other examples of distributions satisfying (A 1 (1, θ)) can be found in the above mentioned table.

Acknowledgments

The authors are grateful to the referees for their helpful comments and to Jonathan El Methni for suggesting the estimator of τ .

|T (3,3) n

in view of Lemma 2, Lemma 5 and Lemma 6. Thus, for all τ ∈ [0, 1), T

-→ 0. Taking ( 17) and ( 18) into account concludes the proof.

Proof of Proposition 4 -From (8), we have

as n → ∞. Now, |b| is a regularly-varying function with index ρ and thus log |b(x)|/ log x → ρ for all x → ∞, see [START_REF] Bingham | Regular Variation[END_REF], Proposition 1.3.6. As a consequence, we obtain

as n → ∞. Let us first remark that, if τ = 1 then (20) implies

and the conclusion follows. Otherwise, if τ ∈ [0, 1), condition (20) can be rewritten as

Besides, since K τ is non-decreasing,

for all τ ∈ [0, 1) and thus, in view of ( 21), necessarily log k n / log n → 0 as n → ∞. As a consequence, log(n/k n ) is asymptotically equivalent to log n and thus K τ (log(n/k n )) is asymptotically equivalent to K τ (log(n)) as well. Replacing in [START_REF] Galambos | The Asymptotic theory of extreme order statistics[END_REF], the conclusion follows.

Proof of Proposition 5 -Let us consider τ ∈ [0, 1/2) and suppose that (8) holds with λ = 0. Following Proposition 4, log(k n ) = -2ρK τ (log n)(1+o(1)) and thus log(k n )/ log(n) → 0 as n → ∞.

A first order Taylor expansion shows that there exists

from [START_REF] Broniatowski | On the estimation of the Weibull tail coefficient[END_REF]. Now, concerning the second term, Theorem 1 entails that

Finally, Q

Combining the above results, Theorem 2 follows.

from [START_REF] Girard | A Hill type estimate of the Weibull tail-coefficient[END_REF]. Here, and in the following, C 1 (ε), C 2 , C 3 (ε) and C 4 (ε) are positive constants independent of t. Thus, from Berry-Esséen's inequality (see [START_REF] Petrov | Sums of independent random variables[END_REF], Theorem 3), we have:

From [START_REF] Girard | A Hill type estimate of the Weibull tail-coefficient[END_REF], since t ≥ T ε , 1) .

Thus, L n ≤ C 4 (ε)(k n -1) -1/2 and therefore

which concludes the proof.

Proof of Lemma 6 -Let us consider the random variables [START_REF] Girard | A Hill type estimate of the Weibull tail-coefficient[END_REF] and λ i,n ≥ 1. Thus, letting

Since |K ρ (exp u) -u| ≤ -ρu 2 /2 for all u ≥ 0, we have θ n,3 (E n-kn+1,n )θ