Raphael Gomes
email: raphael.gomes@ifg.edu.br

Georgios Bouloukakis

Fábio Costa

Nikolaos Georgantas

Ricardo Da Rocha
email: rcarocha@acm.org

QoS-Aware Resource Allocation for Mobile IoT Pub/Sub Systems

Keywords: Publish/Subscribe Middleware, Resource Allocation, Mobile Connectivity, Quality of Service

IoT applications are usually characterized by large-scale demand and the widespread use of mobile devices. Similarly, performing interaction among application and system components in a decoupled and elastic way, and enforcing Quality of Service (QoS) usually also become issues. Hence, paradigms such as pub/sub on top of cloud resources represent a suitable strategy for application development. However, management of QoS-aware resource allocation for pub/sub systems remains challenging, especially when system peers connect in an intermittent way. In this paper, we propose a new approach for resource allocation focusing on end-to-end performance in face of peers' disconnections. We evaluate and demonstrate the benefits of our approach using simulations. QoS enforcement was achieved in almost all scenarios, and we have shown that our approach can help reasoning about efficient resource allocation.

Introduction

The widespread use of smart mobile devices paved the way for the development of smartphone applications that can be accessed anywhere anytime. Additionally, such applications access embedded sensors/actuators for providing environmental-related information, opening new business and market opportunities in the so-called Internet of Things (IoT) [START_REF] Atzori | The internet of things: A survey[END_REF]. However, mobile devices may connect and disconnect intermittently for energy saving purposes, and may be forcefully disconnected due to connectivity issues in underlying wireless network. Accordingly, asynchronous messaging patterns, such as the Publish/Subscribe (pub/sub) paradigm, enable event-buffering during disconnected periods and event-delivery during connected periods. In particular, pub/sub provides loosely coupled interaction in both time and space among publishing data sources and subscribing data sinks [START_REF] Eugster | The many faces of publish/subscribe[END_REF]. As a result, several industry standards have adopted pub/sub as part of their interfaces.

Existing middleware protocols such as MQTT [START_REF] Banks | MQTT Version 3.1. 1[END_REF] and AMQP [START_REF] Standard | Oasis advanced message queuing protocol (amqp) version 1[END_REF], as well as tools and technologies such as RabbitMQ [START_REF]Pivotal: RabbitMQ[END_REF], Kafka [START_REF] Kafka | [END_REF] and JMS [START_REF]JMS Specifications[END_REF] follow the pub/sub paradigm. To support the development of effective applications under the constraints found in the IoT (i.e., intermittent connectivity, obsolete data feeds, etc), pub/sub protocols provide several Quality of Service (QoS) features [START_REF] Bouloukakis | Performance modeling of the middleware overlay infrastructure of mobile things[END_REF]. These features aim to enable application developers to tune an application by configuring its QoS metrics at different levels such as end-to-end response times and delivery success rates.

Despite the fact that the QoS features of pub/sub may enable timely data delivery, this can be affected (as well as other QoS metrics) by the the hardware resources used to deploy software components such as message brokers [START_REF] Hoffert | Adapting distributed real-time and embedded pub/sub middleware for cloud computing environments[END_REF]. Besides, although mobile devices have increasing processing, storage, and communication capabilities, they are not able to handle all sorts of tasks in a proper way [START_REF] Botta | Integration of Cloud Computing and IoT: a Survey[END_REF], making imperative the use of external resources. The use of Cloud computing is the most promising solution to enable the deployment of scalable and reliable software components. This further enhances the loosely coupled interaction between publishers and subscribers, also improving reliability as deployed message brokers in the cloud are always connected to receive/forward events.

Different solutions have been proposed for the problem of resource allocation under specific QoS constraints in order to support the development of message brokers in the Cloud [START_REF] Gascon-Samson | Dynamoth: A scalable pub/sub middleware for latency-constrained applications in the cloud[END_REF][START_REF] Nguyen | Resource management for elastic publish subscribe systems: A performance modeling-based approach[END_REF][START_REF] Setty | Cost-effective resource allocation for deploying pub/sub on cloud[END_REF]. However, these solutions mainly focus on the satisfaction of local QoS requirements (e.g., employing load balancing strategies for individual jobs) lacking support for end-to-end non-functional properties. Proposed strategies for end-to-end QoS enforcement in pub/sub systems [START_REF] Barazzutti | Elastic scaling of a high-throughput content-based publish/subscribe engine[END_REF][START_REF] Carvalho | Scalable qos-based event routing in publish-subscribe systems[END_REF][START_REF] Hoffert | Adapting distributed real-time and embedded pub/sub middleware for cloud computing environments[END_REF] have limited scope (e.g., changing on transport protocols) or present limitations such as incompatibility with existing middleware protocols. Additionally, in pub/sub systems, the subscribers' intermittent connectivity affects the existing resource allocation algorithms. For instance, message brokers with local subscribers that disconnect for long periods, demand additional processing and buffer resources. Thus, the design of QoS-aware resource allocation algorithm for mobile IoT applications remains an important challenge as it is necessary to satisfy elastic demands while keeping costs under control.

To deal with the above limitations, in this paper we present a QoS-aware approach for the allocation of resources for IoT applications. We consider IoT applications that run over a pub/sub system with mobile publishers/subscribers, along with message brokers that are deployed in the cloud. We formalize the resource allocation problem and estimate response times by relying on Queueing Network Models [START_REF] Lazowska | Quantitative system performance: computer system analysis using queueing network models[END_REF]. Our approach provides system designers with resource allocation estimates at design time enabling the achievement of accurate end-toend runtime behavior. We evaluate and demonstrate the benefits of our approach using simulations based on both probability distributions and parameters derived from real-world workload traces. The core contributions of the paper are:

1. Formalization of the resource allocation problem in mobile pub/sub systems. 2. A model for the response time from publishers to subscribers, which is obtained by connecting queuing models that represent cloud resources and peers' disconnections. 3. A cost-effective resource allocation strategy based on the splitting of end-toend QoS thresholds and on resource selection in a multi-cloud environment. 4. A simulation environment for the evaluation of QoS properties in pub/sub systems with awareness of the connectivity status of communicating peers. The rest of this paper is organized as follows: Section 2 introduces the pub/sub system model and the problem of allocating resources for message brokers. In Section 3, a formalization of this problem is presented. Our resource allocation approach is provided in Section 4, which takes into account the peers' connectivity. Finally, the validation and evaluation of our approach is considered in Section 5, followed by conclusions and future work in Section 6.

System Model

Mobile IoT applications are typically deployed on resource-constrained devices with intermittent network connectivity. To support the deployment of such applications, the pub/sub interaction paradigm is often employed, as it decouples mobile peers in both time and space. In a pub/sub system, multiple peers interact via an intermediate broker entity -publishers produce events characterized by a specific filter to the broker. Subscribers subscribe their interest for specific filters to the broker, who maintains an up-to-date list of subscriptions.

To support distributed applications spanning a wide-area, the pub/sub system has to be implemented as a set of independent, communicating brokers, forming the broker overlay. As depicted in Fig. 1, in such architectures [START_REF]Distributed Event Routing in Publish/Subscribe Communication Systems: a Survey[END_REF][START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF], peers can access the system through any broker that becomes their home broker. Then, based on the peers' input the pub/sub system performs several processes: i) subscriptions are spread to a subset of existing brokers through a subscription partitioning process; ii) published events correspond to subsets of subscribers determined through a matching process; iii) the produced events are delivered to all the matched subscribers through an event routing process. Regardless of the event routing algorithm in use, produced events pass through a specific path of brokers towards the subscribers. For example, in Fig. 1 the produced events pass through brokers b 2 , b 5 and, finally, b 7 , which is s 1 's home broker.

Building an IoT application over a pub/sub infrastructure, requires the selection of an appropriate protocol (e.g., MQTT). Such a protocol enables peers to access the broker overlay and push/receive events. Additionally, to create the pub/sub broker overlay, it is essential to select the corresponding message broker implementation (e.g., ActiveMQ, VerneMQ, HiveMQ, etc). Every message broker has different capabilities, such as: compatibility with different protocols, support for clustering (i.e., forming a broker network), provision of performance

ƐƵďƐĐƌŝƉƚŝŽŶƐ ƉĂƌƚŝƚŝŽŶŝŶŐ Ğ|ĞŶƚ ŵĂƚĐŚŝŶŐ ďƌŽŬĞƌƐ ƉƵďůŝƐŚĞƌƐ ƐƵďƐĐƌŝďĞƌƐ ܾ 1 ܾ 3 ܾ 2 ܾ 4 ܾ 6 ܾ 9 ܾ 8 ܾ 7 ݏ 1 ݏ 2 ݏ 3  1  3 ܾ 5  2 Fig. 1. Pub/Sub System.
features, etc. Finally, an important design-time decision is the deployment of each broker to an appropriate machine. A common tactic of pub/sub developers is to deploy or assume the deployment of brokers in the cloud.

To perform cloud resource allocation, different technologies (e.g., Virtual Machines -VMs [START_REF] Setty | Cost-effective resource allocation for deploying pub/sub on cloud[END_REF] and containers [START_REF] Nguyen | Resource management for elastic publish subscribe systems: A performance modeling-based approach[END_REF]) can be used, each with its strengths and weaknesses. In this paper, we use VMs as the unit of allocation, although we keep the solution as generic as possible to admit other alternatives. Terms such as resource and VM are used interchangeably in the text. For simplicity, we assume that each resource is used by a single broker via on-demand resource instantiation. Accordingly, the pricing of resource allocation is estimated taking the one-hour utilization of an instance of the given resource type.

In IoT scenarios, system deployment usually aims to achieve co-location of things and allocated resources. This strategy is used to decrease the communication demand on devices with hardware and power limitations. Another motivation is that whilst data-processing speeds have increased rapidly, the bandwidth to carry data to and from datacenters has not increased at the same speed [START_REF] Shi | The promise of edge computing[END_REF]. For these reasons, in our approach resource allocation is limited to resources found inside a single region. For cloud vendors such as Amazon [START_REF]Amazon Web Services -Broad & Deep Core Cloud Infrastructure Services[END_REF], which splits a region into multiple availability zones, we adopt a single availability zone. Hence, we neglect data propagation delays inside pub/sub system when evaluating QoS.

Based on the above, several questions arise: i) what is the amount of resources that a developer should allocate for an IoT application that runs over a pub/sub system? ii) Can we ensure specific end-to-end response times between publishers and subscribers by relying on the resulting resource allocation? iii) What is the cost to achieve such end-to-end QoS? iv) Does the intermittent connectivity of peers affect the cost of resource allocation?

In the next section, we delineate our approach using a formal notation for the problem with respect to the questions raised above.

3 QoS-aware Resource Allocation for Pub/Sub Systems

The lack of a direct producer/consumer relationship in pub/sub interactions makes the definition and enforcement of any end-to-end QoS policy very hard [START_REF] Corsaro | Quality of service in publish/subscribe middleware[END_REF]. Additionally, the peers' intermittent connectivity makes the design of a fully decoupled QoS-driven pub/sub system that can scale to different dimensions without under-or over-provisioning of resources even more challenging.

Resource allocation is carried out by translating QoS constraints into infrastructure level parameters, which are then mapped to a number of predefined resource types, described in terms of hardware capacity, cost, and location. We call the joint execution of these tasks resource synthesis. It is not a straightforward task due to the large number of resource type options and intersections among them. Yet, even considering a single region of any given cloud provider, a possibly large number of resource types may need to be inspected and the best cloud vendor must be selected. To elucidate the main elements of the resource synthesis problem and precisely outline its scope, we first formalize it.

Problem Formalization

Given a pub/sub system with intermittently disconnected peers, the Resource Allocation Problem (RAP) consists in selecting the proper resource type and the number of resource instances, in order to deploy a network of brokers aiming at QoS enforcement and cost savings. To mathematically represent event streams, we use a topic-based subscription model, since it is efficient and simple in terms of event classification. Nevertheless, our approach can be used for any model where several classification techniques are applied. We model the parameters concerning the RAP as follows: R = {r j : j ∈ [1.

.|R|]} is the set of event topics that correspond to IoT sensor data, device commands, etc.

S = {s i : i ∈ [1.
.|S|]} is the set of subscribers: devices or persons interested in event notifications. They subscribe to any number of event topics in R. We denote the set of topics that s i subscribes as R si ⊆ R. Let λ sub si,rj be the delivery rates of events to each subscriber s i for publications to topic r j ∈ R si .

P = {p i : i ∈ [1.
.|P|]} is the set of publishers: devices/persons that publish events on some set of topics. We denote the set of topics that p i publishes as R pi ⊆ R. Let λ pub pi,rj be the publication rate of events published to to topic r j by publisher p i ∈ P. We assume that each p i publishes events according to a Poisson process at each topic r j .

We model the connectivity of pub/sub peers as follows: let ON and OFF be the states where the peer is connected and disconnected, respectively. A given peer, is connected (ON state) for an exponentially distributed time period with parameter θ ON (θ ON = 1/T ON ). Upon the expiration of this time, the peer disconnects (OFF state) and stops sending or receiving relevant events for an exponentially distributed time period with parameter θ OFF (θ OFF = 1/T OFF ). Accordingly, let T ON pi , T OFF pi be the connection/disconnection average periods for p i and

T ON si , T OFF si for s i . B = {b k : k ∈ [1.
.|B|]} is the set of pub/sub brokers. A broker forwards events from publishers to interested subscribers or to other brokers in the broker network for eventual consumption by a subscriber. We assume that each publisher/subscriber connects with a single broker that we refer to as its home broker : b pi is the broker that publisher p i publishes to and b si is the broker that subscriber s i receives events from. Furthermore, we define the set of publishers and subscribers connected with b k as

P b k = {p i ∈ P : b k = b pi } and S b k = {s i ∈ S : b k = b si } respectively. V = {v j : j ∈ [1.
.|V|]} is the set of resource types (e.g., VMs).

ζ[] vj is a vector used to describe a resource type. It contains information about hardware capacity (e.g., CPU cores and clock speed, bandwidth, etc.).

c vj is the allocation cost of an instance created using the resource type v j .

∆ si is the end-to-end response time of events matching subscriber's topics R si from the moment they are published until s i receives them.

∆ pi,si is the end-to-end response time of events matching the common subscriber's and publisher's topics (i.e., R pi ∩ R si ) from the moment they are published by p i until s i receives them.

The above delays include event processing times and network delays inside the broker network. Note that in this paper we do not model processing delays of publishers/subscribers. Our main purpose is to estimate delays inside the broker network in order to allocate their resources accordingly.

∆ pi,si b k ,vj is the response time contribution from broker b k on the end-to-end path between p i and s i . This contribution depends on the resource v j selected for broker deployment.

∆ thr is the response time threshold inside the pub/sub system for any endto-end path between p i and s i . When setting this parameter, resource allocation should be performed in such a way that the end-to-end response time (∆ pi,si ) of all events between any p i and s i does not exceed this limit.

x i is an integer variable that indicates if ∆ thr has been satisfied for a given end-to-end path, as follows:

x i = 1, if ∆ si ≤ ∆ thr ; 0, otherwise. (1)
F = {f k : k ∈ [1..|F |]
} is the set of mappings (result of RAP), where each f k is a pair (b k , v j ) representing the mapping of a broker to an allocated resource type (which includes the number of deployed resource instances).

ϕ vj is an objective function depicting the profit in allocating resource v j . It is used to distinguish the best option among feasible solutions.

ϕ(F ) is the composed profit of all resources in F . In this way, the optimal solution satisfies the QoS threshold for all subscribers and gives the best ϕ(F ).

RAP can be more formally expressed as an optimization problem as follows:

Maximize ϕ(F ) = b k ∈B vj ∈V ϕ vj y kj ; subject to si∈S x i = |S|; vj ∈V y kj = 1, k ∈ [1..|B|]; y kj ∈ {0, 1}, k ∈ [1..|B|], j ∈ [1..|V|].
The variable y kj is either 1, implying b k is mapped to v j , or 0 otherwise. As RAP is clearly an optimization problem, we argue that it is not possible find an optimal solution for an instance of this problem in polynomial time. Nevertheless, in the next section, we provide a feasible approach based on a reduction to a version of the knapsack problem and on an analytical model for QoS estimation for solving this problem.

Resource Synthesis with Intermittent Connectivity

Our approach focuses on the QoS-aware allocation of resources for deploying message brokers at design time. Initially, a system designer provides the topology and characteristics of the pub/sub system (brokers, peers' intermittent connectivity, etc), its routing algorithm [START_REF]Distributed Event Routing in Publish/Subscribe Communication Systems: a Survey[END_REF] (e.g., rendezvous nodes) and the end-to-end response time threshold (∆ thr ). Then, our approach provides a specification of the corresponding resources, in terms of types and quantity. After deploying brokers based on the specification, end-to-end response times must be below the specified ∆ thr at runtime. In this paper, we are agnostic with respect to the algorithm used to route events. Hence, we assume that the end-to-end paths between publishers and subscribers (i.e., the broker paths) are estimated somehow using the provided routing algorithm. Additionally, we acknowledge that the resulting resource allocation may be invalidated if different routing paths are used at runtime. However, we argue that complementary solutions may benefit from cloud elasticity to perform adaptation of the resource allocation.

To provide an efficient solution for the above-described problem without the costs associated with an exhaustive search strategy, we rely on well-known solutions to the Multiple-choice Multi-dimension Knapsack Problem (MMKP) [START_REF] Moser | An algorithm for the multidimensional multiple-choice knapsack problem[END_REF]. MMKP is a NP-Complete problem defined as follows: given a set H of items divided in h categories Q q , where each category

Q q : q ∈ [1..h], has κ q = |Q q | items such as ∀ 1 ≤ i, j ≤ h and i = j, Q i ∩ Q j = ∅ and ∪ h i=1 Q i = H. Each item o ∈ [1..κ q ],
from category Q q has a non-negative profit qo , and has dimensions given by a weight vector W qo = {w a qo : a ∈ [1.. ]}, where each element w a qo is also a non-negative value. The knapsack dimensions are given by the vector

A = {A a : a ∈ [1.. ]}.
The goal in MMKP is to pick exactly one item from each category in order to maximize the total profit, subject to knapsack dimensions.

In the provided approach, we construct an MMKP instance from a RAP instance. To do so, we rely on results related to solving MMKP. We use the WS-HEU heuristic [START_REF] Yu | Efficient algorithms for Web services selection with end-to-end QoS constraints[END_REF] to efficiently select the resource types in order to reach the thresholds for each constraint. We chose this heuristic because it solves the MMKP problem with an accuracy of 96% compared to the optimal value, and can provide worst-case complexity of O(|S| × |B| 2 × (|V| -1) 2 ). The construction of an MMKP instance from a RAP instance is carried out as follows. Let n be the number of categories (h). We map each b k ∈ B as a category Q q with same number of items (generated from resource types, i.e., each v j ∈ V is mapped as a different item o for each category). In this way, we remove the property of empty set in the items intersection of categories, but this change does not affect the problem since constraints are evaluated separately for each category. We generate the weight vector W qo for each item by using the average delays of each routing path in which the corresponding broker participates, so that [∆ p1,s1 b k ,vj ..∆

p |S| ,s |S | b k ,vj
] is mapped to [w 1 qo ..w qo ], and ϕ vj is mapped to qo . Finally, the response time threshold is multiply mapped as knapsack dimensions A = {A a : a ∈ [1.. ]}.

End-to-end QoS evaluation is carried out in our approach by separately addressing each possible routing path in the pub/sub system. Although this may sound inefficient, we argue that by using the chosen heuristic we can reach the resource synthesis result in admissible time. Additionally, this task is performed at design time, when low overhead is not a major concern. We discuss this further in Section 5 when presenting the experimental evaluation. By using the WS-HEU heuristic, an initial solution is pursued using a greedy strategy based on the ratio between resource cost and QoS offering. In cases where even considering all resource types no feasible solution is found, an event of unaccomplished resource synthesis is triggered. We deal with this problem through the inclusion of new broker instances. To this end, we assume a round-robin load balancer with negligible overhead. The selection of the broker to be replicated is carried out by taking the broker with the worst QoS, which is most likely one of the edge brokers due to the effects of peers' disconnections. Additional broker instances are added until a feasible solution is found. When this happens, there is an attempt to improve the solution by performing simulated annealing [START_REF] Aarts | Simulated annealing and Boltzmann machines[END_REF]. The entire procedure is performed for the resource types from each cloud provider.

The resource synthesis output is a mapping of each broker (and its additional instances) to a selected resource type, taking the less costly result. By using this strategy, resource allocation is performed through the balancing of the contribution to the end-to-end constraints among all participating brokers. As can be seen, a key aspect of this approach is QoS estimation. For this purpose, we propose the performance model described next.

Pub/Sub QoS Estimation

In this subsection, we present our queueing network model which is used as input to the resource allocation algorithm. By relying on our previous work [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF], we model the performance inside a pub/sub broker network by relying on queueing theory. In particular, each queue processes events through a dedicated server. Each server supports a specific service rate (λ) which is exponentially distributed. All queueing centers apply a first-come-first-served (FCFS) queueing policy. We model the network transmission delay between brokers (b k → b i ) using an M /M /1 queue and between b si (s i 's home broker) → s i (subscriber) using an ON /OF F queue. With regard to [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF], in this paper we slightly modify our formal model and queueing models. More specifically, in order to process incoming events at a broker node b k we use the M /M /c queueing model: c is the number of servers of the queue and each server has an independently and identically distributed exponential service-time distribution with mean 1/µ. We correspond c to the number of VM cores in which the broker is deployed. ƌŽŬĞƌ ŶŽĚĞ ; Ϳ As depicted in Fig. 2, we model each broker b k using a single inbound queue q in b k (M/M/c) and multiple outbound queues q out b k (M/M/1 and ON/OFF). Let λ in b k be the arrival rate of events at q in b k , represented as the sum of all event publication/forwarding rates over all publishers/brokers. Forwarding, replication, or dropping of events based on current subscriptions occurs at the exit of q in b k . Let µ in b k be q in b k 's service rate for analyzing an incoming event and determining where to forward it (e.g. based on a topic routing tree). We assume that the service rate is exponentially distributed across all topics with parameter µ in b k . Events that do not match b k 's subscriptions are dropped with rate λ nosub for transmission to s i . We model each q out b k ,si using an ON/OFF queue for transmitting events based on s i 's intermittent connectivity (i.e., T ON si , T OFF si ). Let µ out b k ,si be q out b k ,si 's service rate for transmitting an event to s i . Note that µ out b k ,si and µ out b k ,bi rates model the transmission delay of events inside the network.

dž KEͬK&& YƵĞƵĞ KEͬK&& YƵĞƵĞ DͬDͬϭ YƵĞƵĞ DͬDͬĐ YƵĞƵĞ ܾ ߤ ݅݊ ܾ ݇ , ݏଵ ߤ ݐݑ ܾ ݇ , ݏ ߤ ݐݑ ܾ ݇ , ܾ ߤ ݐݑ ܾ ߣ ݅݊ ܾ ߣ ܾݑݏ݊ ܾ, ݏ 1 ߣ ݕ݂݅ݐ݊ ܾ, ܾ݅ ߣ ݀ݓ݂ ܾ, ݅ݏ ߣ ݕ݂݅ݐ݊ ͙͘͘ ܾ ܵ ܾ ݏ ݅ ݏ 1 ܾ ݅ ܾ ݅  ݅
To build the broker model of Fig. 2, we use three different types of queueing models. Based on standard solutions, each queueing type evaluates several performance metrics (e.g., response time) through analytical models. Particularly, with regard to response time in M/M/1 queues [START_REF] Lazowska | Quantitative system performance: computer system analysis using queueing network models[END_REF], the time that an event remains in the system (corresponding to queueing time + service time, also called average delay) is given by:

∆ qmm1 (µ, λ) = 1 (µ -λ) (2)
Regarding the M/M/c queue, the time that an event is remain in the system is given by [START_REF] Gross | Fundamentals of queueing theory[END_REF]:

∆ qmmc (µ, λ, c) = 1 µ + r c c!(cµ)(1 -ρ) 2 p 0 ( 3
)
where c is the number of servers, r = λ/µ, ρ = r/c and the steady-state probability p 0 can be found in [START_REF] Gross | Fundamentals of queueing theory[END_REF]. Finally, regarding the ON/OFF queue, the time that an event is remain in the system is given by [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF]: Fig. 3. Queneing network for the end-to-end interaction: p2 to s1.

∆ q onof f (µ, λ, T ON , T OFF ) = T OFF 2 T ON +T OFF + T ON +T OFF µT ON 1 -λ T ON +T OFF µT ON (4)
In the next subsection, we show how these analytical models can be used to estimate end-to-end response times.

End-to-end Response Time. We propose a strategy to allocate resources for deploying pub/sub brokers based on the response time threshold (∆ thr ) applied inside the pub/sub system. Hence, in order to allocate resources it is essential to calculate the expected delay between p i and s i (∆ pi,si ) inside the broker network by considering the intermittent connectivity of peers. Based on the broker's queueing model (see Fig. 2), s i 's connectivity affects the resulting delay -i.e., during T OFF si , b k buffers events. Furthermore, events may pass through a subset of brokers, until they arrive to s i 's home broker (b si ). Therefore, for a given s i , the average delay inside a broker node b k can be estimated as follows:

∆ b k = ∆ q in b k + ∆ q out b k ,b i , if b k = b si ∆ q in b k + ∆ q out b k ,s i , if b k = b si (5)
Subsequently, for a given interaction between p i and s i , events pass through a subset of intermediate brokers (b i ) and s i 's home broker (b si ). Let λ pi,si be the rate of events from p i to s i . To estimate ∆ pi,si , it is essential to apply the so called effective service rate (µ in/out b k -ef f ) at each inbound/outbound queue of b k . Such a service rate is calculated only for the λ pi,si rate but by taking into account other rates of events λ in/out-oth b k (lack of subscriptions, forwarding rates to other brokers, etc) [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF].

To demonstrate our approach, we provide the following example: to ∆ p2,s1 , the resulting queueing network is depicted in Fig. 3. Hence, ∆ p2,s1 is given by:

∆ p2,s1 = ∆ b2 + ∆ b5 + ∆ b7
Based on Fig. 3 5), we estimate the end-to-end delay using the corresponding queues. As already pointed out, q in b k is an M/M/c queue, q out b k ,bi is an M/M/1 queue and q out b k ,si is an ON/OFF queue. Hence, by relying on (2), ( 3) and ( 4) the average delay of an intermediate broker, e.g., b 2 is given by:

∆ b2 = ∆ qmmc (µ in b2-ef f , λ p2,s1 , c b2 ) + ∆ qmm1 (µ out b2-ef f , λ p2,s1
) And the average delay of b s1 is given by:

∆ bs 1 = ∆ qmmc (µ in b7-ef f , λ p2,s1 , c b7 ) + ∆ q onof f (µ out b7-ef f , λ p2,s1 , T ON s1 , T OFF s1 ) 0 0.5 1 1.5 2

Experimental Evaluation

The goal of our experiments is to study the effects of our approach on QoS enforcement, on the reduction of the resource allocation cost, and on performance.

In this section, we first introduce a simulation environment developed to enable this evaluation and then discuss the experiments and achieved results.

Simulating Intermittent Connectivity over Pub/Sub Systems

Experimental evaluation requires tools that facilitate the design of experiments while making them repeatable and precise. Simulators are useful tools to build such evaluation environments in the cloud context [START_REF] Zhao | Modeling and simulation of cloud computing: A review[END_REF]. However, to the best of our knowledge, there is no simulation environment for cloud-based pub/sub systems enabling the modeling of the peers' connectivity. For this reason, we developed our own simulator, called Mobile CloudSim (M-CloudSim) 6 , as an extension of the CloudSim simulation toolkit [START_REF] Calheiros | CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF] with the following features. 1) Application model: Simulations in CloudSim are implemented by modeling a set of cloudlets (application tasks) and VMs. On top of it, a cloud mediator is defined to schedule cloudlets according to the available VMs in a discrete-event simulation dynamics. Although this model is feasible to represent the main aspects of cloud applications, it does not allow indirect communication modeling as well as routing in message brokers. To solve this limitation, in our extension we have distinguished two cloudlet categories: event processing and event transmission. We explicitly represent the events routing paths, creating and submitting cloudlets from both categories to simulate event forwarding.

2) Modeling intermittent peer connectivity: one of the main goals in our evaluation is to evaluate the effects of peer disconnection. We handle this by simulating changes on peer connection state. On the simulation, peer connection is checked before the processing, transmission, and delivery of events on home brokers. We only simulate changes of connectivity states for subscribers since during the publishers' disconnections there is no event-transmission to brokers and, therefore, no relation with resource allocation.

We kept the M-CloudSim functionalities limited to the scope of this paper. As a way of demonstrating the validity of the results provided, we have performed an experimental comparison with two other tools: using the analytical model presented in this paper and using MobileJINQS [START_REF] Bouloukakis | Timeliness evaluation of intermittent mobile connectivity over pub/sub systems[END_REF], an open-source library for building simulations encompassing the constraints of mobile systems (but lacking resource simulation). In this evaluation, we have computed the response time in a specific path of a pub/sub system. In the simulated environment the subscriber remains in the ON and OFF states for exponentially distributed time periods T ON = T OFF = 10/20/40/60 sec. For the analytical model and the MobileJINQS simulation, processing and transmission of events are served with a mean service demand of 0.0625 sec and 0.125 sec, respectively. Accordingly, in the M-CloudSim simulation we set CPU and bandwidth characteristics in the simulated VMs to provide the same timing. We assume sufficient buffer capacities so that no events are dropped. Also events are generated by the publisher with a mean rate varying from 0.05 to 4 events per sec. By applying λ rates greater than 4 events/sec, the system saturates both in the analytical model and in the MobileJINQS simulation. Differently, M-CloudSim can simulate any number of input rates since it works for a predefined time slice by using waiting queues with "infinite" size. The mean response time of 100 independent executions (for each scenario) is depicted in Fig. 4. Confidence intervals of the simulation results are found to be very small and are not presented in the figure. By comparing the curves for the three strategies response times, we notice that results match with high accuracy for arrival rates below to 3.5 events/sec. Differences are noticed for rates equal to or higher than 3.5 events/sec. This is acceptable since the system is close to saturation at these rates.

Resource Synthesis Validation

In this experiment, we check whether QoS enforcement is achieved as a result of the resource synthesis approach. We also evaluate the resulting profit by using the resource allocation cost as a parameter. On top of it, we check whether the peer's intermittent connectivity affects the resource allocation cost. For this purpose, we carry out the resource synthesis in different scenarios and use M-CloudSim to examine the achieved response times. We compare the following scenarios: i) with always-connected pub/sub peers; and ii) with intermittently connected peers due to network issues. In both cases, we apply the methodology illustrated in Fig. 5: we first perform resource synthesis by using as input an end-to-end response time threshold (∆ thr ), the pub/sub system topology (i.e., publishers, subscribers), the flow of events, the end-to-end routing path of events, the peers intermittent connectivity and the available resource types.

For all scenarios, we applied as input the VM types provided by the marketleading vendors according to Gartner's latest report on cloud Infrastructure as a Service [START_REF] Lydia | Magic Quadrant for Cloud Infrastructure as a Service[END_REF] -Amazon [START_REF]Amazon Web Services -Broad & Deep Core Cloud Infrastructure Services[END_REF], Microsoft Azure [23], and Google Cloud Platform [START_REF]Google: Compute Engine[END_REF]. In this experiment, we use the available VM configurations in the São Paulo, Brazil, region on Jan-2018, with a total of 94 resource types. For the pub/sub system we use the same topology of Fig. 1 by taking only events on path p 2 → s 1 . We isolate other flows of this path by estimating the corresponding effective service rate (µ ef f ) for p 2 → s 1 . Larger scale scenarios (with more paths) are used to evaluate the scalability of the approach in the next section. We assume that the broker network is reliable, with no broker overload. In addition, all events have the same size, which is equal to 200 bytes (approximately 200 characters of application payload). Also event processing requires 33.2 CPU instructions (average number of instructions in the method body of general Java programs [START_REF] Collberg | An empirical study of java bytecode programs[END_REF]). We vary the arrival rate of events from 0.5 to 23 events per second. We set ∆ thr with an initial value of 0.025 sec. Then, we increase ∆ thr with increments of 0.025 sec. We perform evaluations until the synthesis result is the same for at least 5 consecutive arrival rate variations (half of the analyzed scenarios). We present the results for the two scenarios next.

Always Connected

As already pointed out, in this scenario we assume that a subscriber is always connected (T OFF si = 0). We use this case to analyze what is the minimum achieved response time in the given scenario and to generate a comparison baseline for the next case. Fig. 6 presents the results of simulated response times and resource allocation cost for selected thresholds. Although we have analyzed several thresholds, for better readability we present only three cases: i) the minimum achieved response time (∆ thr = 0.125); ii) the upper threshold analyzed (∆ thr = 0.275), i.e., when synthesis result is stable for at least half of the arrival rates; and iii) an intermediary value between them (∆ thr = 0.2). We discuss only these thresholds because it is not possible to achieve smaller values with the available resource types (even with multiple instances). On the other hand, higher thresholds do not affect the synthesis result when using the considered arrival rates. As the main result, QoS enforcement was achieved in all scenarios. It is worth noting that the simulated response times are, on average, 30% better than the set of thresholds, while the resource allocation cost was, on average, $0.40, $0.12, and $0.09, respectively for each threshold. As expected, the allocation cost increases for higher arrival rates. As a remark, the resource types on Amazon provided the best results in all scenarios for the São Paulo region.

Network Issues

The actual connectivity of mobile peers depends on the network coverage and capacity, as well as the type of peer mobility. In this scenario, we evaluate the case of subway passengers in order to analyze the effects of the intermittent connectivity of peers on resource allocation. For this purpose, we use our dataset 7of mobile connectivity for the subway system in Paris. The used data show that subway travelers loose and recover network connection for periods that range from several seconds to 5 minutes, maximum. On average, connected periods are 1.5 times larger than the disconnected periods. We randomly select the path Dugommier → Cité Universitaire for this study of subscriber mobility. By analyzing the complementary cumulative distribution functions of connections and disconnections in the above subway path, we conclude that our traces fit best with an exponential distribution, such as T ON si = 155.8 sec and T OFF si = 96 sec. Fig. 7 presents the results for selected thresholds.

QoS enforcement is more challenging with intermittent connectivity. For the given parameters it is not possible to achieve response times lower than 22.95 sec due to the overhead in the processing of buffered events. For this threshold, there is QoS violation in some cases but the values were on average only 3.11% different from the thresholds. The resource allocation cost was, on average, $10.03, $0.14, and $0.03, respectively. This result enforces the need for such a solution for resource allocation tunning since a small change in response time threshold (an increasing of 8.95% on tolerated response time on this case) can result in a substantial decrease in resource allocation cost (a saving of 99.7% on cost).

Performance Evaluation

In the previous experiments, we demonstrated the effectiveness of the resource synthesis approach on QoS enforcement. However, we performed this evaluation using a single event routing path. In order to extend this analysis, we measured the approach performance for higher scale scenarios. For this purpose, we analyzed the processing time to get results when taking many routing paths as input. We do this evaluation using the scenario from the previous experiment with always-connected subscribers, and a publishing rate of 23 events/sec. We set ∆ thr = 10 sec to make QoS fulfillment possible as the scale increases.

In this experiment, we create synthetic pub/sub topologies by varying |B| = [1. .6]. By taking paths of different scales (i.e., number of participating brokers) we generate all possible options in the pub/sub system. In the context of our future work, we intend to use specific event routing algorithms (e.g., selective routing or event gossiping [START_REF]Distributed Event Routing in Publish/Subscribe Communication Systems: a Survey[END_REF]) in order to scale our approach (the set of possible endto-end paths will be reduced). For each scenario, we generate all routing paths with same number of communicating message brokers as follows: we generate all combinations without repetition taking l = [1..|B|] message brokers per path. For each resulting set we then create all possible permutations. Using this strategy, each scenario has a topology with |B| l l! = |B|! (|B|-l)! routing paths what allow us to evaluate the scalability of the approach.

We run the synthesis approach for the same input 100 times and collect the average processing time and confidence interval. All executions were performed on a machine with the following configuration: Intel CPU R Core TM i5 2.67GHz, 4GB RAM, Ubuntu 14.04. The average processing time for each scenario is presented in Table 1. Resource synthesis processing time varies from 0.03 sec to 8.16 min. The high processing time in the worst case scenario is due to a high number of routing paths. In order to evaluate the feasibility of the solution, the processing time must be compared with the duration of the other tasks in the pub/sub system deployment. Regarding this, since we do not use previously instantiated VMs, VM startup is the main bottleneck. The reason for this is that VMs have to be instantiated and configured, which includes communication with the cloud provider, VM loading, and installation of software components. Even though we have not conducted any experiments in this regard, there are a number of results in the literature that indicate an overhead from 44.2 sec to 13.5 min on VM startup in public clouds [START_REF] Mao | A Performance Study on the VM Startup Time in the Cloud[END_REF]. We argue that the overhead imposed by the resource synthesis is acceptable, especially if we consider the achieved benefits.

Conclusions and Future Work

In this paper, we propose a new approach for resource allocation for IoT applications in the Cloud. Such applications run over pub/sub systems and their things can be intermittently disconnected. Our approach can be used as a tool by pub/sub system designers to allocate resources for QoS enforcement. We have evaluated the proposed solution using scenarios based on probability distributions of the events, as well as scenarios based on connectivity parameters derived from real traces. QoS enforcement was achieved in almost all scenarios, which showed only 3.11% of QoS violation in some cases. conclude that resource demand increases with higher arrival rates but also due to peer disconnections. Consequently, the cost of deploying the system is also affected by these parameters. However, we have shown that our approach can help reasoning about efficient resource allocation in a variety of scenarios, saving up to 99.7% on resource allocation cost. Finally, our approach has a feasibly processing time, as corroborated by the experiments.

As future work, we intend to identify the limits for system saturation, given the available resources. We also aim to carry out a more comprehensive performance evaluation using real pub/sub protocols. As further unfolding of the work, we aim to extend this proposal with support for QoS enforcement when using multiple regions.

Fig. 2 .

 2 Fig. 2. Queneing Network for Pub/Sub Broker Node.

.

  Broker b k forwards events matching subscriptions served by other brokers with rate λ f wd b k ,bi through an outbound M/M/1 queue q out b k ,bi . These events are sent from b k to any b i ∈ B, b i = b k . Let µ out b k ,bi be q out b k ,bi 's service rate for transmitting an event to b i . For each of b k 's local subscribers, s i ∈ S b k & b si = b k , b k forwards events matching subscriptions to q out b k ,si with rate λ notif y b k ,si

, b 2 ,

 2 b 5 are intermediate brokers and b 7 is s 1 's home broker (b 7 = b s1 ). Hence, by relying on (

Fig. 4 .

 4 Fig. 4. Comparison of results from M-CloudSim, Analytical Model and MobileJINQS.

Fig. 5 .

 5 Fig. 5. Resource synthesis validation methodology.

Fig. 6 .

 6 Fig.6. Results of synthesis validation for always connected subscriber.

Fig. 7 .

 7 Fig. 7. Results of synthesis validation for subscriber's intermittent connectivity.

Table 1 .

 1 Resource synthesis processing time (in sec)

	Total number		Number of brokers in each routing path
	of brokers	1	2	3	4	5	6
	1	0.03
	2	0.04	0.09
	3	0.06	0.12	0.16
	4	0.08	0.21	0.68	0.99
	5	0.07	0.37	2.14	10.04	14.69
	6	0.10	0.55	5.91	62.41	346.03	489.36

https://github.com/raphaeldeaquino/mcloudsim

https://github.com/boulouk/mobile-jinqs/tree/master/experiments/metro


Xiaodong Lü

Zhiwei Wang

ON THE LARGEST PRIME FACTORS OF CONSECUTIVE INTEGERS

Denote by P + (n) the largest prime factor of an integer n. One of Erdős-Turán's conjectures asserts that the asymptotic density of integers n satisfying P + (n) < P + (n + 1) is 1/2. In this paper, we prove that this density is larger than 0.2017, which improves the previous result "0.1356" of the second author.

Introduction

For each integer n ⩾ 1, let P + (n) denote the largest prime factor of n with the convention that P + (1) = 1. An integer n is called y-friable (or y-smooth) if P + (n) ⩽ y. In 1930, Dickman [START_REF] Dickman | On the frequency of numbers containing prime factors of a certain relative magnitude[END_REF] obtained the well-known result: the following asymptotic formula { n ⩽ x :

P + (n) ⩽ y } ∼ xρ(u) (u ⩾ 1) (1.1)
holds for x → ∞ with u = log x/ log y fixed, where ρ(u) is the Dickman-de Bruijn function function. Later, the distribution of P + (•) has been studied by many mathematicians, for example the work of Dartyge [START_REF] Dartyge | Entiers friables : un tour d'horizon[END_REF], La Bretèche and Tenenbaum [START_REF] De La Bretèche | Propriétés statistiques des entiers friables[END_REF][START_REF] De La Bretèche | Une nouvelle approche dans la théorie des entiers friables[END_REF], Granville [START_REF] Granville | Smooth numbers: computational number theory and beyond[END_REF], Hildebrand [START_REF] Hildebrand | On the local behavior of ψ(x, y)[END_REF][START_REF] Hildebrand | On the number of positive integers ⩽ x and free of prime factors >[END_REF], Hildebrand and Tenenbaum [START_REF] Hildebrand | On integers free of large prime factors[END_REF][START_REF] Hildebrand | Integers without large prime factors[END_REF], Moree [START_REF] Moree | Integers without large prime factors: from Ramanujan to de Bruijn[END_REF]. In recent years, friable integers play an important role in number theory, for example, an extraordinary breakthrough of Zhang [START_REF] Zhang | Bounded gaps between primes[END_REF] towards solving the Twin Prime Conjecture, remarkable progress of Vaughan and Wooley [START_REF] Vaughan | A new iterative method in Waring's problem[END_REF][START_REF] Vaughan | Further improvements in Waring's problem, II: Sixth powers[END_REF][START_REF] Vaughan | Further improvements in Waring's problem[END_REF] in Waring's problem.

In this paper, we aim to study the simultaneous distribution of the function P + (•) at consecutive integers. In the 1930s, Erdős and Turán formulated the following conjecture in the correspondence.

Conjecture 1 (Erdős-Turán). For x → ∞, we have { n ⩽ x : P + (n) < P + (n + 1)

} ∼ 1 2 x. (1.2)
Conjecture 1 is a constant concern for Erdős even though he thought it might be intractable by any technique at our disposal (see [START_REF] Erdős | Some unconventional problems in number theory[END_REF] or [START_REF] Tenenbaum | Some of Erdős' unconventional problems in number theory, thirty-four years later[END_REF]). Later in 1978, Erdős and Pomerance conjectured that the largest prime factors of n and n + 1 are "independent events". Conjecture 3 (De Koninck-Doyon). Fix an arbitrary integer k ⩾ 2 and let n be a large number. Let a 1 , a 2 , . . . , a k be any permutation of the numbers 0, 1, . . . , k -1. Then,

Prob [ P + (n + a 1 ) < P + (n + a 2 ) < • • • < P + (n + a k ) ] = 1 k! .
There has been some progress towards these problems.

• For the Conjecture 1 (Erdős-Turán), in 1978 Erdős and Pomerance [START_REF] Erdős | On the largest prime factors of n and n + 1[END_REF] first proved that there exists a positive asymptotic density of integers n with P + (n) < P + (n + 1). More precisely, they proved that

{ n ⩽ x : P + (n) < P + (n + 1) } > 0.0099x (x → ∞). (1.3)
Later in 2005, the asymptotic density 0.0099 was improved to 0.05544 by La Bretèche, Pomerance and Tenenbaum [START_REF] De La Bretèche | Products of ratios of consecutive integers[END_REF], and to 0.5866 by Fouvry's arguments in "Further remarks" of the same paper [START_REF] De La Bretèche | Products of ratios of consecutive integers[END_REF]. Recently, the second author improved the asymptotic density to 0.1063 [START_REF] Wang | On the largest prime factors of consecutive integers in short intervals[END_REF], and then further to 0.1356 [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF].

On the other hand, in 2001 Rivat [START_REF] Rivat | On pseudo-random properties of P (n) and P (n + 1)[END_REF] proved a P + y (n)-version of the Erdős-Turán conjecture for some small y. Here we just write a more concise version. Define P + y (n) = max{p | n : p ⩽ y} the greatest prime factor p of n which satisfies p ⩽ y. Then for 3 ⩽ y ⩽ exp( log x 100 log log x ), we have

{ n ⩽ x : P + y (n) < P + y (n + 1) } ∼ 1 2 x (x → ∞).
Very recently Teräväinen [START_REF] Teräväinen | A note on binary correlations of multiplicative functions[END_REF] proved a logarithmic version of the Conjecture 1.

δ ( {n ∈ N : P + (n) < P + (n + 1)} ) = 1 2
where the logarithmic density δ of the set A ⊂ N is defined by

δ(A) = lim x→∞ 1 log x ∑ n⩽x, n∈A
1 n whenever it exists. Besides, he also proved a logarithmic version of Conjecture 2.

• For the Conjecture 3 with k = 3, in 1978 Erdős and Pomerance [START_REF] Erdős | On the largest prime factors of n and n + 1[END_REF] observed that the patterns P + (n -1) > P + (n) < P + (n + 1) (1.4) and P + (n -1) < P + (n) > P + (n + 1) (1.5) both occur infinitely often and conjectured that these two patterns occur for a positive density of n. In addition, they proved that there are infinitely many integers n such that P + (n -1) < P + (n) < P + (n + 1)

by considering the integers n of the form n = p 2 k 0 with k 0 well defined. Finally, for the fourth pattern, in 2001 Balog [START_REF] Balog | On triplets with descending largest prime factors[END_REF] proved the following lower bound

{ n ⩽ x : P + (n -1) > P + (n) > P + (n + 1) } ≫ x 1/2 (x → ∞).
Recently, the second author [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF] In addition, we can get a nontrivial upper bound for the above four patterns respectively by considering the distance between friable integers. Just after the second author's submission [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF], Teräväinen [START_REF] Teräväinen | A note on binary correlations of multiplicative functions[END_REF] obtained a similar results to ( * ) et ( * * ) with an unspecified positive density by using another method. • For the Conjecture 3 with k ⩾ 4, little is known. In the same paper [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF], the second author proved the existence of a positive density of integers n with the largest prime factors P + (n + j), j ⩽ k -1 in the following two certain patterns. More precisely, for any fixed integer k ⩾ 3 and j 0 ∈ {0, . . . , k -1}, there exist two positive constants

C 3 (k) and C 4 (k) such that { n ⩽ x : P + (n + j 0 ) = min 0⩽j⩽k-1 P + (n + j) } ⩾ C 3 (k)x + o(x) and { n ⩽ x : P + (n + j 0 ) = max 0⩽j⩽k-1 P + (n + j) } ⩾ C 4 (k)x + o(x).
Besides consecutive integers, the second author recently studied the largest prime factors of consecutive integers with one of which without small prime factor. We refer the reader to [START_REF] Wang | Autour des plus grands facteurs premiers d'entiers consécutifs voisins d'un entier criblé[END_REF] for more details. Now we consider the pattern P + (n) < P + (n + 1), i.e. the conjecture of Erdős-Turán. In [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF], the second author starts from the inclusion-exclusion principle

∑ n<x P + (n)<P + (n+1) 1 = ∑ n<x P + (n+1)>x 1-c 1 - ∑ n<x P + (n)>P + (n+1)>x 1-c 1 + ∑ n<x P + (n)<P + (n+1)⩽x 1-c 1 =: S A -S B + S C , (1.6)
where 0 < c ⩽ 1/2 is a parameter. Then the sum S A is estimated by a result of Hildebrand [START_REF] Hildebrand | On the number of positive integers ⩽ x and free of prime factors >[END_REF] and S B is estimated by the Rosser-Iwaniec sieve and a theorem of Bombieri-Vinogradov type. For the sum S C , the second author gives a nontrivial lower bound by introducing a well adapted system of weights ω(n; y, z) defined by

ω(n; y, z) := ∑ z<p⩽y p|n 1 ⩽ log x log z (1.7)
for n ⩽ x, z < y.

In this paper, we focus on the sum S C . In fact, in [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF], the second author only sieves out the x 0.414 -friable integers n ⩽ x such that n + 1 has a prime factor in the interval (x 0.414 , x 1/2 /(log x) B ] with B > 0, due to a formidable obstacle: the level of distribution Q = x 1/2 /(log x) B for friable integers (see Lemma 2.2). Here by using a switch skill, we can sieve out some friable integers n such that n + 1 has a prime factor larger than x 1/2 . So that we can improve the previous lower bound 0.0118x of S C in [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF], and then prove that the density of the pattern P + (n) < P + (n + 1) is larger than 1/5. More precisely, we have the following result.

Theorem 1. For x → ∞, we have { n < x : P + (n) < P + (n + 1) } > 0.2017x. (1.8)
The lower bound is also true for the pattern P + (n) > P + (n + 1).

Throughout this paper, we denote by ε an arbitrarily small positive constant, and p, p ′ primes.

Lemmas

Denote by

S(x, y)

:= { n ⩽ x : P + (n) ⩽ y } (2.1)
the set of y-friable integers not exceeding x and

Ψ(x, y) := |S(x, y)| (2.2)
the cardinality of S(x; y). Then we have the following lemma.

Lemma 2.1 (Hildebrand,[START_REF] Hildebrand | On the number of positive integers ⩽ x and free of prime factors >[END_REF]). For any ε > 0, we have

Ψ(x, y) = xρ(u) { 1 + O ε ( log(u + 1) log y )}
uniformly, for each ε > 0, in the domain

x ⩾ x 0 (ε), exp { (log log x) 5/3+ε } ⩽ y ⩽ x,
where u = log x/ log y and ρ(u) is the Dickman-de Bruijn function which is defined by differential equation

{ ρ(u) = 1, 0 ⩽ u ⩽ 1, uρ(u) ′ = -ρ(u -1), u > 1.
The second lemma concerns the distribution of friable integers in arithmetic progressions. Lemma 2.2. For any given positive constant A > 0, there exists a constant B = B(A) > 0 such that the estimate

∑ q⩽x 1/2 /(log x) B max t⩽x max (a,q)=1 ∑ n∈S(t, y) n≡a (mod q) 1 - 1 φ(q) ∑ n∈S(t, y) (n, q)=1 ≪ x (log x) A (2.3)
holds uniformly for 2 ⩽ y ⩽ x, where the constant implied by the symbol " ≪ " depends only on A.

In [START_REF] Wolke | Über die mittlere verteilung der werte zahlentheoretischer funktionen auf restklassen[END_REF], Wolke proved a theorem of Bombieri-Vinogradov type for sifted numbers without small prime factors, and in the same paper he also announced the similar result for friable integers. Fouvry and Tenenbaum [START_REF] Fouvry | Entiers sans grand facteur premier en progressions arithmétiques[END_REF] proved a slightly weaker form of the formula (2.3). In addition, for Lemma 2.2 we can also see the work of Fouvry-Tenenbaum [START_REF] Fouvry | Répartition statistique des entiers sans grand facteur premier dans les progressions arithmétiques[END_REF], Harper [START_REF] Harper | Bombieri-Vinogradov and Barban-Davenport-Halberstam type theorems for smooth numbers[END_REF] and Drappeau [START_REF] Drappeau | Théorèmes de type Fouvry-Iwaniec pour les entiers friables[END_REF].

For q ∈ N and (a, q) = 1, define π(x; ℓ, a, q) = ∑ ℓp⩽x ℓp≡a (mod q)

1 and π ′ (x; ℓ, a, q) = ∑ p⩽x ℓp≡a (mod q) 1.

Lemma 2.3. For any given positive constant A > 0, there exists a constant B = B(A) > 0 such that the estimate

∑ q⩽x 1/2 /(log x) B max y⩽x max (a,q)=1 ∑ L 1 <ℓ⩽L 2 (ℓ, q)=1 f (ℓ) ( π(y; ℓ, a, q) - li(y/ℓ) φ(q) ) ≪ x (log x) A (2.4)
and

∑ q⩽x 1/2 /(log x) B max y⩽x max (a, q)=1 ∑ L 1 <ℓ⩽L 2 (ℓ, q)=1 f (ℓ) ( π ′ (y/L 2 ; ℓ, a, q) - li(y/L 2 ) φ(q) ) ≪ x (log x) A (2.5) hold for (log y) 2B < L 1 ⩽ L 2 < x 1-ε
, where |f (ℓ)| ⩽ 1 and the constant implied by the symbol " ≪ " depends only on ε and A.

Proof. For (2.4), it is the Theorem 2 in [START_REF] Pan | On the representation of every large even integer as a sum of a prime and an almost prime[END_REF]. To prove (2.5), we can follow step by step Pan-Ding-Wang's arguments of Theorem 2 in [START_REF] Pan | On the representation of every large even integer as a sum of a prime and an almost prime[END_REF], so we omit the proof. □

The fourth lemma is the estimation of S A and S B in (1.6).

Lemma 2.4. Taking c = 0.2056 in (1.6), one has

S A -S B ⩾ 0.1238x.
Proof. See section 10 in [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF]. □

Estimation of S C

In this section, we mainly focus on the estimation of S C which is defined by (1.6) with c = 0.2056. The improvement in Theorem 1 comes from a switch skill to sieve out some shifted friable integers with a large prime factor and a modification of well adapted system of weights ω(n; y, z) with more delicate calculation of S C .

Recall the definitions of S(x, y) and Ψ(x, y) in (2.1) and (2.2) respectively. Define

P (y, z) = ∏ z<p<y p, S + (x; y, z) = { n ⩽ x : z < P + (n) ⩽ y } .
Then we have

S C = ∑ n<x P + (n)<P + (n+1)⩽x 1-c 1 ⩾ ∑ n∈S(x, x δ 1 ) (n+1, P (x 1 2 /(log x) B , x δ 1 ))>1 1 + ∑ n∈S + (x; x δ 2 ,x δ 1 ) (n+1, P (x 1 2 /(log x) B , x δ 2 ))>1 1 + ∑ n∈S(x, x 1-η 1 ) (n+1, P (x 1-c , x 1-η 1 ))>1 1 + ∑ n∈S + (x; x 1-η 2 ,x 1-η 1 ) (n+1, P (x 1-c , x 1-η 2 ))>1 1 =:S C 1 + S C 2 + S C 3 + S C 4 , (3.1)
where η 1 , η 2 , δ 1 , δ 2 are four parameters satisfying

c < η 2 < η 1 < δ 1 < δ 2 < 1 2 . (3.2)
For the inequality in (3.1), it is obvious that the integers n counted in S C 1 and S C 2 (or in S C 3 and S C 4 ) are disjoint. Besides, noting that Next we will estimate the four sums respectively.

x δ 1 • x 1-η 1 > x, x δ 2 • x 1-η 2 > x by the choice of η 1 , η 2 , δ 1 , δ 2 in (3.2),

Estimation of S C 1 and S C 2

First we will follow the approach of [START_REF] Wang | Sur les plus grands facteurs premiers d'entiers consécutifs[END_REF] to estimate S C 1 and S C 2 . By the definition of ω(n; y, z) in (1.7), we have

ω ( n + 1; x 1/2 /(log x) B , x δ 1 ) { ⩽ 1 δ 1 , ( n + 1, P (x 1/2 /(log x) B , x δ 1 ) ) > 1, = 0, otherwise. (3.3)
Hence we detect the condition

(n + 1, P (x 1/2 /(log x) B , x δ 1 )) > 1 in S C 1 by (3.
3) and we obtain a lower bound of S C 1 :

S C 1 ⩾ δ 1 ∑ n∈S(x, x δ 1 ) ω(n + 1; x 1/2 /(log x) B , x δ 1 ) = δ 1 ∑ n∈S(x, x δ 1 ) ∑ p|(n+1) x δ 1 <p⩽x 1/2 /(log x) B 1 = δ 1 ∑ δ 1 <p⩽x 1/2 /(log x) B ∑ n∈S(x, x δ 1 ) n≡-1 (mod p) 1 = δ 1 ( S ( 1
)
C 1 + S (2) C 1
) , (3.4) where S

(1)

C 1 = ∑ x δ 1 <p⩽x 1/2 /(log x) B 1 φ(p) ∑ n∈S(x, x δ 1 ) (n, p)=1
1,

S

(2)

C 1 = ∑ δ 1 <p⩽x 1/2 /(log x) B ( ∑ n∈S(x, x δ 1 ) n≡-1 (mod p) 1 - 1 φ(p) ∑ n∈S(x, x δ 1 ) (n, p)=1 1
) .

For S

(2)

C 1 , by Lemma 2.2, we have

S ( 2
)
C 1 ≪ ∑ p⩽x 1/2 /(log x) B ∑ n∈S(x, x δ 1 ) n≡-1 (mod p) 1 - 1 φ(p) ∑ n∈S(x, x δ 1 ) (n, p)=1 1 ≪ x(log x) -A . (3.5)
for any A > 0, which is admissible. We use Lemma 2.1 to estimate S

(1)

C 1 , and have

S ( 1
)
C 1 = ∑ x δ 1 <p⩽x 1/2 /(log x) B 1 p -1 Ψ(x, x δ 1 ) = xρ ( 1 δ 1 ) log 1 2δ 1 + o(x).
(3.6)

Therefore we have from (3.5) and (3.6) that

S C 1 ⩾ xρ ( 1 δ 1 ) δ 1 log 1 2δ 1 + o(x). ( 3.7)
Since

S C 2 = ∑ n∈S(x, x δ 2 ) (n+1, P (x 1 2 /(log x) B , x δ 2 ))>1 1 - ∑ n∈S(x, x δ 1 ) (n+1,P (x 1 2 /(log x) B , x δ 2 ))>1 1 ⩾ δ 2 ( ∑ n∈S(x, δ 2 ) - ∑ n∈S(x, δ 1 ) ) ω ( n + 1; x 1/2 /(log x) B , x δ 2 ) ,
A similar manipulation allows us to deduce that

S C 2 ⩾ x ( ρ ( 1
δ 2 ) -ρ ( 1 δ 1 ) ) δ 2 log 1 2δ 2 + o(x). (3.8)

Estimation of S C 3 and S C 4

We now turn to consider the sums S C 3 and S C 4 . Noting that x 1-η 1 > x 1/2 , x 1-η 2 > x 1/2 , so we can not use Lemme 2.2, i.e. the theorem of Bombieri-Vinogradov type for friable integers directly as we have done for S C 1 and S C 2 .

For S C 3 , it counts the number of x 1-η 1 -friable integers n such that n + 1 has at least one prime factor in the interval (x 1-η 1 , x 1-c ) with c < η 1 < 1/2. Then we have

S C 3 = ∑ n∈S(x, x 1-η 1 ) (n+1, P (x 1-c , x 1-η 1 ))>1 1 = ∑ x 1-η 1 <p<x 1-c ∑ dp⩽x P + (dp-1)⩽x 1-η 1 1 = ∑ x 1-η 1 <p<x 1-c ∑ dp⩽x 1 - ∑ x 1-η 1 <p ′ <x ∑ x 1-η 1 <p<x 1-c ∑ dp⩽x dp-1≡0 (mod p ′ ) 1.
(3.9)

For the sum S C 4 , it counts the number of (x 1-η 1 , x 1-η 2 ]-friable integers n, i.e. x 1-η 1 < P + (n) ⩽ x 1-η 2 , such that n + 1 has at least one prime factor in the interval

(x 1-η 2 , x 1-c ) with c < η 2 < η 1 < 1/2. So we have S C 4 = ∑ n∈S + (x; x 1-η 2 ,x 1-η 1 ) (n+1, P (x 1-c , x 1-η 2 ))>1 1 = ∑ x 1-η 2 <p<x 1-c ∑ dp⩽x x 1-η 1 <P + (dp-1)⩽x 1-η 2 1 = ∑ x 1-η 1 <p ′ ⩽x 1-η 2 ∑ x 1-η 2 <p<x 1-c ∑ dp⩽x dp-1≡0 (mod p ′ ) 1.
(3.10) Combing (3.9) and (3.10), we have

S C 3 + S C 4 = ∑ x 1-η 1 <p<x 1-c ∑ dp⩽x 1 - ∑ x 1-η 1 <p ′ <x ∑ x 1-η 1 <p<x 1-c ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 + ∑ x 1-η 1 <p ′ <x 1-η 2 ∑ x 1-η 2 <p<x 1-c ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 = S C 3 + S C 4 , (3.11)
where

S C 3 := ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x 1 - ∑ x 1-η 1 <p ′ <x ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 and S C 4 := ∑ x 1-η 2 <p<x 1-c ∑ dp⩽x 1 - ∑ x 1-η 2 <p ′ <x ∑ x 1-η 2 <p<x 1-c ∑ dp⩽x dp-1≡0 (mod p ′ ) 1.
Invoking the identity log(dp -1) = ∑ m|(dp-1)

Λ(m)

and prime number theory, we find

∑ x 1-α <p<x 1-β ∑ dp⩽x 1 = 1 log x ∑ x 1-α <p<x 1-β ∑ dp⩽x log(dp -1) + o(x) = 1 log x ∑ p ′ <x log p ′ ∑ x 1-α <p<x 1-β ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 + 1 log x ∑ k⩾2 ∑ p ′k <x log p ′ ∑ x 1-α <p<x 1-β ∑ dp⩽x dp-1≡0 (mod p ′k ) 1 + o(x) ⩾ 1 log x ∑ p ′ <x log p ′ ∑ x 1-α <p<x 1-β ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 + o(x).
(3.12) for 0 < β < α < 1.

Now for S C 3 , we have

S C 3 = ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x 1 - ∑ x 1-η 1 <p ′ <x ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 ⩾ 1 1 -η 1 1 log x ∑ p ′ <x log p ′ ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 + ( 1 - 1 1 -η 1 ) ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x 1 - ∑ x 1-η 1 <p ′ <x ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 + o(x) (3.13)
where we have used the estimation (3.12) with (α, β) = (η 1 , η 2 ). For the second term on the right-hand side of (3.13), we use Mertens' formula. And for the the first term on the righthand side of (3.13), we split it into two sums according to whether p ′ > x 1-η 1 or p ′ ⩽ x 1-η 1 .

So we obtain

S C 3 = 1 1 -η 1 1 log x ∑ p ′ ⩽x 1-η 1 log p ′ ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 + 1 log x ∑ x 1-η 1 <p ′ <x ( 1 1 -η 1 log p ′ -log x ) ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 - η 1 1 -η 1 log 1 -η 2 1 -η 1 x + o(x) = 1 log x ( 1 1 -η 1 S A + S B ) - η 1 1 -η 1 log 1 -η 2 1 -η 1 x + o(x), (3.14)
where

S A : = ∑ p ′ ⩽x 1-η 1 log p ′ ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1, S B : = ∑ x 1-η 1 <p ′ <x ( 1 1 -η 1 log p ′ -log x ) ∑ x 1-η 1 <p⩽x 1-η 2 ∑ dp⩽x dp-1≡0 (mod p ′ ) 1.
For S A , we have lower bound

S A ⩾ ∑ p ′ ⩽x 1-η 1 log p ′ ∑ x η 2 <d<x η 1 (d, p ′ )=1 ∑ x 1-η 1 <p⩽x/d dp-1≡0 (mod p ′ ) 1 ⩾S A 1 + S A 2 -S A 3 , (3.15)
where )

S A 1 : = ∑ p ′ <x 1/2 /(log x) B log p ′ φ(p ′ ) ∑ x η 2 <d<x η 1 (d, p ′ )=1 ∑ x 1-η 1 <p⩽x/d 1, S A 2 : = ∑ p ′ <x 1/2 /(log x) B log p ′ ∑ x η 2 <d<x η 1 (d, p ′ )=1 ( ∑ dp⩽x dp-1≡0 (mod p ′ ) 1 - 1 φ(p ′ ) ∑ dp⩽x 1 ) , S A 3 : = ∑ p ′ <x 1/2 /(log x) B log p ′ ∑ x η 2 <d<x η 1 (d, p ′ )=1 ( ∑ p<x 1-η 1 dp-1≡0 (mod p ′ ) 1 - 1 φ(p ′ ) ∑ p<x 1-η 1
.

for some B > 0.

For S A 2 , taking (L 1 , L 2 , ℓ) = (x η 2 , x η 1 , d) and f (ℓ) ≡ 1 in (2.4) of Lemma 2.3, one has upper bound

S A 2 ⩽ ∑ q< x 1/2 (log x) B log q ∑ x η 2 <d<x η 1 (d, q)=1 ∑ dp⩽x dp≡1 (mod q) 1 - 1 φ(q) ∑ x η 2 <d<x η 1 (d,q)=1 ∑ dp⩽x 1 ≪ x (log x) A (3.16)
for any A > 0, which is admissible. Similarly, for S A 3 , taking (L 1 , L 2 , ℓ) = (x η 2 , x η 1 , d) and f (ℓ) ≡ 1 in (2.5) of Lemma 2.3, one has upper bound

S A 3 ⩽ ∑ q< x 1/2 (log x) B log q ∑ x η 2 <d<x η 1 (d, q)=1 ∑ p<x 1-η 1 dp≡1 (mod q) 1 - 1 φ(q) ∑ x η 2 <d<x η 1 (d,q)=1 ∑ p<x 1-η 1 1 ≪ x (log x) A (3.17)
for any A > 0, which is also admissible. Then for S A 1 , it follows from partial summation and prime number theorem that

S A 1 = ∑ p ′ <x 1/2 /(log x) B log p ′ φ(p ′ ) ∑ x η 2 <d<x η 1 (d, p ′ )=1 ∑ x 1-η 1 <p<x/d 1, = ( 1
2 log 1 -η 2 1 -η 1 + o(1)
)

x log x.

(3.18)

For the sum S B , we have trivially

S B ⩾ 0. ( 3

Conjecture 2 (

 2 Erdős-Pomerance). For any a, b ∈ [0, 1], denote by B(x; a, b) the number of n ⩽ x with P + (n) ⩽ x a and P + (n) ⩽ x b , B(x; a, b) := { n ⩽ x : P + (n) ⩽ x a , P + (n + 1) ⩽ x b } . Then the asymptotic density b(a, b) := lim x→∞ B(x; a, b) exists and equals ρ( 1 a )ρ( 1 b ). In 2011, De Koninck and Doyon formulated a more general conjecture in order to study the distance between friable integers.

1

 1

  .19) So from (3.14)-(3.19) we obtain a lower bound of S C 3 : By the same method of estimation of (3.20), we can get a lower bound of S C 4 : Hence from (3.11), (3.20) and (3.21), we have S C 3 + S C 4 ⩾ S C 3 + S C 4

			S C 3 ⩾ x	1 -2η 1 2(1 -η 1 )	log	1 -η 2 1 -η 1	+ o(x).	(3.20)
			S C 4 ⩾ x	1 -2η 2 2(1 -η 2 )	log	1 -c 1 -η 2	+ o(x).	(3.21)
	⩾	(	1 -2η 1 2(1 -η 1 )	log	1 -η 2 1 -η 1	+	1 -2η 2 2(1 -η 2 )	log	1 -η 2 1 -c	+ o(1) )	x.	(3.22)

Acknowledgements

The authors would express their sincere gratitude to Cécile Dartyge and Jie Wu for their helpful advice and constant encourage. The first author is supported by the China Postdoctoral Science Foundation (No. 2017M621829), the Jiangsu Province Postdoctoral Science Foundation (No. 1701142C) and the Yangzhou University Overseas Study Program. The second author is supported by China Scholarship Council.

The second author is supported by the China Scholarship Council.

Finally, combing (3.7), (3.8) and (3.22), we get

with η 2 , η 1 , δ 1 , δ 2 satisfying the condition (3.2).

Proof of Theorem 1

We conclude from Lemma 2.4 and (3.23) that

where

With the help of Mathematica 8.0, we find

by taking η 2 = 0.3190, η 1 = 0.4098, δ 1 = 0.4099 and δ 2 = 0.4576. Now Theorem 1 comes from (4.1), (4.2) and (4.4).

Xiaodong Lü