Giovanni Vincenzo Fracastoro

Joseph Virgone

Chiara Aghemo

Anna Pellegrino

Laura Blaso

Jérôme Savoyat

Kévyn Johannes

Kevyn Johannes

Energy efficiency in public buildings through ICT based control and monitoring systems

Keywords: energy efficiency, existing public buildings, control strategies, dynamic simulations

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

SEEMPubS specifically addresses reduction in energy usage and CO 2 footprint in existing public buildings and spaces by implementing an intelligent ICT-based building monitoring and managing system. Actions of retrofitting on building envelopes or services to reduce energy consumptions are not always possible or economically convenient in existing buildings and in particular in historical buildings where conservation is a matter of priority. In SEEMPubS a system to monitor and control buildings services and appliances will be designed and implemented with the aim of optimizing energy usage without compromising occupants comfort and offering decision makers strategies and tools needed to plan energy saving measures.

The proposed system will make use of "LinkSmart", which is a service-oriented middleware developed in a previous European project [START_REF] Jahn | Hydra Middleware for Developing Pervasive Systems: a Case Study in the eHealth Domain[END_REF], [START_REF] Lardies | Deploying Pervasive Web Services over a P2P Overlay[END_REF] and designed to support the development of networks of embedded systems, simplifying the interconnection of heterogeneous devices that communicate using different protocols. The project will use the LinkSmart middleware potential to create services and applications across heterogeneous devices to develop an energy-aware platform.

The SEEMPubS platform will provide functions and tools to add energy efficiency features to the Building Management System (BMS), by monitoring environmental and energy data in real time, and by controlling the operation of active systems like lighting and HVAC services, taking advantage of natural resources (daylight and solar energy) to ensure the best possible comfort conditions with the most efficient use of energy.

A real-time energy-awareness service for all users of the Public Spaces will be also created and it will combine awareness services with a community portal to actively involve people in energy saving issues.

The functionality of the designed platform will be demonstrated in existing buildings at the Politecnico di Torino Campuses (Italy). Buildings built in different periods, from historical to contemporary constructions, were chosen as pilot study, to take into account potentials and drawbacks resulting from the use of smart ICT based systems in buildings with different features and constraints.

In the paper the activity carried out during the first year of the project to define the new BMS architecture and in particular the control strategies proposed for implementation in the existing buildings is presented. Furthermore a special focus is set on the procedure adopted to evaluate the effectiveness of the proposed control strategies: dynamic simulations have been carried out to assess the saving potentials with respect to the energy performance goals.

Control strategies

The activity carried out during the first year of the project was mainly focused at preparing the groundwork for the development, implementation and validation of the BMS in the Politecnico buildings. To demonstrate the effectiveness of the new system in reducing energy consumption, increasing occupants comfort and simplifying facility managers activities, some rooms, from each Campus site, were selected as case studies [START_REF] Virgone | Building definition: criteria, methodologies and description of the selected buildings, D1.1[END_REF]. Rooms were chosen on the basis of the following criteria:

• representativeness with respect to Politecnico Campus and other Public Buildings • energy saving potentials • characteristics of the existing services.

Both private and public spaces in historical and modern buildings were selected, in particular classrooms, student offices, single offices and open plan offices were chosen as demonstrator. Energy saving potentials related to the control of HVAC services, lighting plants and other electrical appliances, were supposed according to the rooms architectural and plants features (volume, orientation, type of envelope, type of heating and lighting plant, shading system, etc.), the type of activity carried out, the occupancy patterns and the solar/daylight availability. Twelve rooms were selected: six reference rooms, running with the present systems and with manual controls, and six similar test rooms, where the BMS will be implemented for lighting, heating/cooling and electrical appliances control and monitoring. The monitoring of the energy consumptions in each couple of room will provide information on the savings achievable with the designed control system.

Further analyses on the selected rooms were carried on to determine the future control strategies: indoor and outdoor microclimatic and lighting conditions were monitored during different periods of the year and an overall energy auditing was carried out to determine the present energy performance of the Politecnico buildings [START_REF] Virgone | Energy audit certification, D1.2, WP1, Smart Energy Efficient Middleware for Public Spaces SEEMPubS project[END_REF].

2.1

Lighting control strategies Time switching is the strategy that entails to turn automatically on and off luminaires at scheduled times to avoid useless lighting out of working hours. This is the simplest and more spread solution in public and commercial buildings.

Daylight harvesting is the control strategy that entails to automatically adjust luminaires light flux (dimming) in order to maintain a predetermined illuminance in the room, taking into account the contribution of daylight. The aim of this lighting control strategy is to ensure adequate lighting condition throughout the working hours and to save energy by means of reducing the lighting power as a function of daylighting supply. This strategy is especially effective in those rooms or buildings that are characterised by high daylight availability and all-day working hours.

Occupancy control will turn luminaires on and off when the presence or absence of people is detected in a space. Also in this case the automatic control avoids energy waste produced by the possibility that users leave the spaces forgetting the lights on. The control logic could provide for either switching on and off or for single off, leaving the user, in this second case, the possibility to turn on the light when desired. A lighting control based only on presence detection will be effective in those spaces where user absence is highly probable, and in particular in public or commercial buildings, where users are little motivated at caring about the use of light.

Proposed control logics

According to the information on the rooms features achieved during the first phase of the project, some lighting control logics were initially proposed [START_REF] Pellegrino | Initial energy control and conservation strategies, D2.3.1, WP2, Smart Energy Efficient Middleware for Public Spaces SEEMPubS project[END_REF]. In particular, for spaces with high daylight availability and medium/high users absence probability, a combination of daylight harvesting and occupancy control was proposed. For spaces with low daylight availability, a lighting control based on occupancy sensing was proposed, while a particular solution was planned for large classrooms with no daylight: students absence probability during the day is very low, but the classroom area could be only partially occupied when a small number of students attend the lectures. In this case it was supposed to use several occupancy sensors to dim to a minimum the light corresponding to the unoccupied parts of the classroom.

In all cases the possibility to override the automatic control via manual command is provided.

In the following diagrams the lighting control logics proposed for the selected case studies are presented.

Figure 1 describes the control logics corresponding to a strategy of both daylight harvesting and occupancy control. The lights will be switched on and off when user presence or absence is detected by the occupancy sensor and will be dimmed up or down to integrate daylighting in order to achieve the required lighting conditions for visual comfort. Likewise, figure 2 shows the control logics for controlling lighting as a consequence of users presence. In these cases the lights will be switched on and off when user presence or absence is detected by the occupancy sensors.

HVAC control strategy

Methodology of work

The goal of the SEEMPubS project is to decrease the energy consumption of buildings while ensuring the comfort of the users. We have to take into account two different factors: 1-the type of heating system used in the selected rooms; 2-the intermittent use of the building.

The economic advantage of intermittent use of heating systems in intermittently-occupied buildings (e.g. schools, office buildings) is no longer in doubt. Nevertheless, optimal energy consumption requires that the heating restart time be defined with great precision. In many cases, to avoid risks, the lowering of the temperature during non-occupancy period is limited, which leads to reductions in energy savings.

An intermittent heating controller allows the internal temperature to be lowered during non-occupancy periods, while maintaining the desired temperature during occupancy periods, when these periods are clearly defined [START_REF] Fraisse | Thermal control of a discontinuously occupied building using a classical and a fuzzy logic approach[END_REF]. The different phases of heating are as follows and are illustrated in figure 5 In our case, we want to go further by having a detection of the occupancy. A schedule is always defined allowing turning off the heating when the room is unoccupied, unless a presence is detected. Nevertheless, the user can always act on the system by changing the set point temperature of the fan coils with individual switcher. In fact, lot of classrooms or offices are not used during all the time of the scheduled period. If no presence is detected, the heating is stopped after a little delay. Furthermore, since access to all the information is simultaneously available, strategies of interoperability may be found allowing for example the anticipation of the heating stop if the other loads (solar or internal) are enough.

Heating control strategy

The control strategy proposed is based on a communication between all sub-systems (heating/cooling, lighting, other electricity used). The algorithm logic for heating is presented in figure 6:

• The strategy supposes that every room possesses its own panel of circuit breaker: a circuit breaker for heating (in the case of fan coils it is on the ventilator that we act), one for lighting and one for electricity plugs.

• A minimum indoor temperature should be defined which the heating has to restart. Two practical examples of communication between subsystems are described hereafter:

• The heating schedule is on "unoccupied", but someone enters the office for work. If necessary, lights will be switched on thanks to the presence detector, which will also switch on the heating system for the comfort of the person using the office.

Another example is to anticipate the heating system switch off when heat gains from lighting and electrical devices (computers, …) exceed the heating power needs. A normal feedback control would let the indoor temperature increase above the set-point before stopping the heating systems, with an unnecessary waste of energy. The graphic in figure 7 explains this point.

Theoretical application

The following schema explains the adoption of this strategy on a room.

Numerical simulations

The potential in saving energy of the proposed control solutions has been assessed by means of building performance simulations. The procedure adopted was as follow:

• analysis of available software and selection of the most appropriate with respect to the simulation goal; • monitoring of environmental condition in the selected rooms (illuminance, air temperature, relative humidity);

• models construction and simulation of environmental conditions;

• comparison between monitored data and simulation results;

• further set up of rooms model;

• simulation of rooms performance in terms of energy consumption and environmental conditions when applying the new control strategies.

3.1

Lighting simulations

Methodology

To assess the effectiveness of the proposed lighting control solutions, for each analysed room, the savings from future control strategy respect to the present one has been calculated from total annual electric lighting energy consumptions.

In general, the total annual energy used for lighting depends, among the other factors, on daylight availability. Therefore, to calculate the energy consumption for those rooms where daylight is allowed to enter a dynamic Climate-Based Daylight Modelling (CBDM) approach [START_REF] Reinhart | Dynamic daylight performance metrics for sustainable building design[END_REF]) [START_REF] Mardaljevic | Simulation of annual daylighting profiles for internal illuminance[END_REF] was used to estimate annual daylight availability and, as a consequence, to calculate the electric energy consumption as a function of the type of lighting control system adopted.

Climate-based daylight modelling allows the prediction of various lighting quantities using sun and sky conditions that are derived from standard meteorological datasets. At present there are quite a few software that allows a climate-based daylight simulation. Among them Radiance and Daysim are the most well-known and used in the lighting field.

Daysim calculates the annual daylight availability in arbitrary buildings based on the Radiance backward ray tracer, using external daylighting conditions derived from standard meteorological local datasets. It includes specific occupant behaviour model algorithms to mimic occupant use of personal controls such as light switches and venetian blinds and to predict the electric lighting use due to automated lighting controls such as occupancy sensors and photocell controlled dimming systems. In addition to daylighting metrics, among its outputs, the total annual energy used for lighting [kWh] and the LENI value [kWh/m 2 year] are included (EN 15193, 2007).

For the SEEMPUBS project both Radiance and Daysim were used. The first one to validate the models, the second one to estimate the lighting energy use and the savings obtained with the proposed control solutions.

Model validation

To start the lighting simulation with Radiance or Daysim a 3D model of the selected rooms and their external environment were prepared (Figure 9). The rooms' models were prepared using the parametric software Revit and then imported in Radiance and Daysim through the software Ecotect.

To correctly characterise the model's opaque and transparent surfaces, in field measurements of luminous reflectances and transmittances were carried out. The models' validation was done comparing the output of the Radiance simulations with the quantities measured inside the rooms, with same sun position and sky condition.

As an example, table 1 presents some first results obtained for a clear and an overcast sky condition. The measurements were done in correspondence of two points on a horizontal plane: one near the window (point 1), one far from the window (point 2). The relative differences between calculated and measured values ranges from -12% to 29.4%, therefore confirming an acceptable accuracy of the model used for the lighting simulation.

Simulation results for lighting energy demand

Annual energy demand for lighting, in a building or room, depends on several factors: • indoor daylight availability;

• building usage, in terms of occupancy profile, required illuminance and user behaviour with respect to both electric and daylighting systems; • lighting plant characteristics, mainly concerned with the installed electric power density and the adopted lighting control system.

To calculate the total annual energy used for lighting Daysim requires to define the arrival and departure time, the presence of lunch or intermediate breaks during working hours and the target illuminance, while, for the user's behaviour with respect to lighting and blinds, some different algorithms can be used. For lighting it can be selected an active or an equal mixed of active and passive behaviour. For blinds an active behaviour is considered which may depends on or the user's need to avoid direct sunlight on work plan or to avoid discomfort glare. In general, Daysim defines as "active" the user who operates the electric lighting taking into account the indoor daylight conditions, opening the blinds in the morning, and partly closing them to avoid visual discomfort. While, it defines as "passive" the user who keeps the electric lighting switched on for all working hours and keeps the blinds lowered throughout the year.

The options to simulate lighting and shading control system are:

• shading control: manual, automatic or no movable shading; • lighting control: six different control strategies are considered: 1) manual on/off switch near the door, 2) switch off occupancy sensor, 3) switch on/off occupancy sensor, 4) photosensor controlled dimming system 5) combination switch off occupancy and dimming system 6) combination on/off occupancy and dimming system. Furthermore, as for the characteristics of the lighting plant, the following data are required:

• installed lighting power density (W/m 2 );

• standby power (W/m 2 ) for occupancy sensor, photosensor, etc; • ballast loss factor (%);

• delay time of the occupancy sensor (minutes).

In the following some first results of lighting energy demand for one of the rooms selected as demonstrator in the SEEMPubS project are presented. The selected case study for this first analysis is a single office, with internal movable shading device, southwest oriented. Inputs for simulation are:

• occupancy profile: from 9,00 a.m. to 6,00 p.m., with lunch and intermediate breaks;

• user requirements and behaviour: target illuminance of 500 lx, mix of active and passive user's behaviour for lighting and active behaviour depending on the user's need to avoid direct sunlight on work plan for blinds;

• lighting control systems: the initially proposed control solution for the considered office was a combination of switch on/off based on occupancy and dimming based on photosensor. In this phase of the study all control options available in Daysim were actually simulated to compare their effectiveness with respect to the manual control, which is the solution used at present in the Politecnico buildings. Results are presented in figure 10 and table 2. The control solution proposed at first (combination on/off based on occupancy plus dimming) seems not to provide relevant savings with respect to manual control (-8%). This result is consistent if we consider that a user with mixed active and passive behaviour was selected for manual control and that the presence of the shading device in a southwest oriented room may reduce greatly the annual daylight availability. The results obtained with Daysim demonstrate that, for this room, the most effective control strategy would be a combination of dimming based on light availability and switch off based on occupancy. In this case energy savings with respect to manual control rise up to 22%.

HVAC simulations

Software presentation

TRNSys is a internationally recognized software dedicated to the simulation of dynamic systems, developed by the Solar Energy Laboratory (SEL), University of Madison in the United States. It allows performing dynamic simulations of the thermal behaviour of a mono or multi-zone building. It can also follow hourly consumption (heating, air conditioning) or production (solar panels) annual energy facilities of a building.

TRNSys is in fact a software which compiles different modules (called "types") and allows to link them one to the other to create a realistic model of the building (or the room) tested. Each type has it own part in the simulation. For example, three types are used to create meteorological data of the simulated place, and a special type to model the building (walls and their compositions, windows...).

The new version of TRNSys (v17) was used to perform those simulations. The new 3D plug-in of this version was used on several cases of the project to go further in the interoperability between parametric architectural software (Revit) and energy simulation software (TRNSys; Daysim, etc.)

Modelling of two offices in historical building

The figure below presents the TRNSys simulation diagram used to simulate the buildings with the different types to model all the specifications of the Politecnico campus (fan coils or AHU...).

Fig. 11. Global TRNSYS simulation model

To approach more precisely the reality of the Politecnico campus, two special types were used to simulate fan coils (present in nearly all the rooms of the SEEMPubS project).

Those types use the hot water temperature and the flow rate of the fan to calculate the exact energy consumption of the system. A schedule has also been adopted to recreate the occupancy and no occupancy periods of the general heating system of Politecnico. The hot water temperature of the general heating system was supposed to vary as a function of the outdoor temperature in Torino according to a classical heating law (figure 13).

Simulation results

In this section we present the first results of the simulation concerning two offices in the Valentino Castle (Politecnico di Torino). One of the offices, the reference room, represents the present situation of the office (occupancy, fan speed selected manually by the occupant, heating based on a automatic schedule which doesn't take into account the occupancy ...). The second office is used to test the control strategy described in the precedent paragraph.

The aim of this study is to measure the energy saving potential of the control strategy proposed in the SEEMPubS project. To perform this goal, a simulation has been made of one cold week (winter condition) and the heating needs and the internal temperature of the two offices were measured.

An important part of our strategy is based on the management of the heating (or cooling) during periods without occupancy.

To see the influence of our strategy an occupancy schedule was created, which simulates four types of day:

• an office day: occupation of the office from 8am to 6pm, • a teaching day: occupancy from 8am to 10am, then after lunch from 1pm to 2pm, and finally after the afternoon class from 4pm to 6pm, • a conference day: no occupancy during the day, • Weekend: no occupancy.

In the simulation performed here we have in the two offices this repartition:

• an office day: Monday and Friday,

• a teaching day: Tuesday and Wednesday ,

• an conference day: Thursday.

• Weekend day: Saturday and Sunday.

In the next table (table 3) the results on the heating needs of the two offices during this cold week are presented: The next figure (figure 14) presents both internal temperatures of the rooms during the week with the external temperature of Torino used to performe the simulation: As we can see on table 3, the control strategy used in the test office allows to perform an important energy saving (-66% compare to the reference room). This result is a consequence of the management of periods without occupants. In a classic office like the reference room, the occupancy is managed by a general schedule for the entire building which cut off the heating from 6pm to 8am and during weekends but the heating is on every day, no matter if the occupant is out for the day. In the test office, a presence detector is used which allows to turn off the heating if no presence is detected for more than 30min.

Furthermore, in the classical office, the fan speed is controlled by the occupant who usually put it to the maximal value, which is 3, so the heating will always be to its maximal power to reach the set point temperature in the room (no matter which the real occupation is). On the other hand, in the test office, a regulator is used to choose the fan speed; for example if the set point temperature is 21°C and the indoor temperature of the room is 20°C, the regulator will select the minimal speed to reach 21°C, but if the temperature is 16°C in the office, it is the maximal speed which will be chosen.

Conclusions

The paper presents some activities carried on in the first phase of the SEEMPubS project and in particular it describes the methodology adopted to define and evaluate the control strategies to be applied in the demonstrator buildings of the Politecnico di Torino to prove the efficacy of the ICT-based BMS that will be designed and implemented in the following phases of the project.

Based on the analysis of buildings and rooms' characteristics, new control strategies have been proposed, both for lighting and for heating, in order to provide energy savings in buildings where heavy retrofitting works are not possible, like for historical buildings. The effectiveness of the proposed control strategies is being evaluated through building performance dynamic simulations.

As far as lighting is concerned, the first energy saving results, obtained for a single office southwest oriented, demonstrated that the initially proposed control solution wouldn't provide the expected savings, while better results could be achieved with a different combination of occupancy based and daylight harvesting control. Higher savings are expected for rooms with greater annual daylight availability (for instance rooms with a minor use of shadings).

A further consideration regards the impact of occupancy profile and users' behaviour: at present the algorithms implemented in Daysim have been used to calculate the energy demand, but different results could be obtained by implementing an "ad hoc" occupancy profile or user behaviour algorithm, as was done for thermal simulations.

To conclude with the thermal simulation part, a first answer about energy saving potential of the control strategy imagined for the SEEMPubS project has been achieved in design conditions. This turned out to be about 60% on this test simulation, but it was based on a reference case with a scarce control. This result has to be completed by an analysis of thermal comfort discrepancies induced by this control and by a yearly study, which also includes warmer days.

Fig. 1 .

 1 Fig.1. Control logic in case of both daylight harvesting and occupancy control.

Fig. 2 .

 2 Fig. 2. Control logic in case of occupancy control in open plan offices Figure 3 describes the lighting control logics designed for big classrooms with no daylight, and figure4shows the logics for those rooms where, together with the electric lighting, shading devices can be automatically controlled on the bases of the sun position and the solar radiation measured on the building roof.

  Fig. 5. Intermittency of heating strategy illustration

Fig. 6 .

 6 Fig. 6. Algorithm for heating strategy

Fig. 8 .

 8 Fig. 8. Evaluation, during time, of the different powers

Fig. 9 .

 9 Fig. 9. 3D model of the building around the simulated rooms

Figure 10 .

 10 Figure 10. Energy demand for different control strategies

Fig 12 .

 12 Fig 12. TRNSYS simulation model to simulate fan coils.

Fig 13 .

 13 Fig 13. Hot water calculation law used

Fig 14 :

 14 Fig 14: indoor temperatures results of the simulation

  To define the most appropriate lighting control strategies, a general overview of the state of the art on lighting control was first carried out(De Stefanis A. et al. 2011). The most recurrent solutions for energy savings are:

	• time switching • daylight harvesting • occupancy control • a combination of the previous.

Table 1 .

 1 Comparison between measured and calculated illuminances.

	Sky	Point	Measured	Calculated	Relative
	condition		Illuminance	Illuminance	difference
			(lx)	(lx)	(%)
	Clear Sky	1 2	26618 1088	31840 958	19.6 -12.0
	Overcast	1	246	276	11.9
	sky	2	74	96	29.4

Table 2 .

 2 Calculated percentage of energy saving with different control strategies, respect to manual control

	Control strategies	Energy savings with
		respect to manual
		control (%)
	Switch off occupancy sensor	-18%
	Switch on/off occupancy sensor	0%
	Photosensor controlled dimming
	system	-5%
	Combination switch off occupancy
	and dimming system	-22%
	Combination on/off occupancy and
	dimming system	-8%

Table 3 .

 3 Maximal power P and heating needs E resulting from the simulation

		Reference office Test office Savings (%)
	P (W)	8794	6755	-23
	E (kWh)	169	58	-66
	P/A (W/m²)	148.4	114	-23
	E/A kWh/m²)	2.86	.97	-66

Acknowledgements

We acknowledge the contribution of whole consortium of the SEEMPubs project which collaborated at the achievement of the presented results.


David Bonnin

Corentin Travers

α-registres

Keywords: Envoi de message, tolérance aux pannes, simulation de mémoire partagée

On sait que, dans un système distribué asynchrone avec communication par envoi de messages, il est possible de simuler un registre atomique, à condition que la majorité des processus ne tombent pas en panne. À l'inverse, si une majorité des processus peuvent tomber en panne, cette simulation est impossible. Cet article explore des variantes faibles des registres atomiques qui peuvent être simulées en tolérant une majorité de pannes. Plus précisément, cet article introduit une nouvelle classe de registres, appelés α-registres, et montre comment les simuler. Avec les registres atomiques, une lecture retourne la dernière valeur écrite. Les α-registres les généralisent de la fac ¸on suivante : pour tout intervalle de temps I ne contenant pas d'écriture, au plus α valeurs distinctes sont retournées par les opérations de lecture ayant lieu pendant I. Une simulation d'un α-registre tolérant f pannes dans un système à n processus est présentée pour α = 2M -1, avec M = max(1, 2 fn + 2). Cette simulation est optimale à un facteur constant près : les α-registres ne peuvent pas être simulés en tolérant f pannes si α ≤ M.

Introduction

Registers A register is a basic shared object that allows processes to store and retrieve values. The state of a register consists in a value in some set V ; it supports two operation : WRITE(v), that changes its state to v and READ() that returns the value stored in the register. Several consistency conditions have been defined that specify correct responses for READ() operations overlapping concurrent WRITE() operations [START_REF] Lamport | On interprocess communication[END_REF]. In their strongest form, registers are atomic : each operation appears to take place instantaneously. Registers are useful in distributed computing, because it is often easier to write algorithms and prove results with shared registers than in message-passing systems.

More than twenty years ago, Attiya, Bar-Noy and Dolev showed that atomic registers can be emulated in asynchronous, crash prone message passing systems provided that a majority of the processes do not fail [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF]. This fundamental result enables shared-memory algorithms to be automatically implemented in message passing environment, and thus, problems solvable with shared-memory are solvable in message passing systems. Furthermore, impossibility results and lower bounds established in the message passing model can directly be translated to shared memory.

Beyond the majority barrier A key ingredient of the simulation of registers in message passing is a quorum system, that is a collection of sets of processes such that any two sets intersect. In Attiya, Bar-Noy and Dolev protocol (ABD protocol [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF]), a quorum is any set of nf processes, where n is the total number of processes in the system and f < n 2 an upper bound on the number of failures. Quorums defined as set of nf processes are live, in the sense that any process can broadcast a request and eventually receives replies from nf processes. Each READ() or WRITE() operation uses a quorum of processes to, respectively, gather and propagate information. However, if less than a majority of the processes are non-faulty, i.e. f ≥ n 2 , two quorums may not intersect, leading to READ() operations returning outdated values, because there is no process in the intersection of READ() and WRITE() quorums that could transmit the information of the last written value. Indeed, simulating atomic registers while tolerating f ≥ n 2 failures in asynchronous message passing is not possible [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF].

A few approaches have been proposed to circumvent this impossibility. Probabilistic quorums systems allow two quorums to be non-intersecting with some small probability [START_REF] Abraham | Probabilistic quorums for dynamic systems[END_REF][START_REF] Friedman | Probabilistic quorum systems in wireless ad hoc networks[END_REF][START_REF] Malkhi | Probabilistic quorum systems[END_REF], leading to a small probabil-ity that READ() operations return stall values. The approaches [START_REF] Friedman | Two abstractions for implementing atomic objects in dynamic systems[END_REF] is based on stronger model assumptions : in particular on a quorum oracle that forces quorums of consecutive write/read to intersect.

The question addressed in the paper Given n and n 2 ≤ f < n, what type of (weak) register can be simulated in an n-processes asynchronous message passing system tolerating f failures ?

By the ABD emulation, shared memory may be seen as an high-level language to design message passing algorithms tolerating a minority of failures. The question above thus amounts to finding an equivalent high level construct for the case in which a majority of the processes may fail.

Contributions of the paper

The contribution of the paper is threefold : (1) it introduces α-registers, a new type of register that generalizes atomic registers, where α represents a bound on the number of distinct values that can be read in a period without WRITE() operations (Section 2) ; this property is non-trivial, since the ABD emulation (or simple variants) would lead to an unbounded such number (α = ∞) . ( 2) for f ≥ n 2 and M = 2 fn + 2, it presents a f -resilient message passing implementation of a single-writer multi-reader α-register with α = 2M -1 (Section 3). ( 3) finally, the paper establishes a lower bound linking f , n and α, namely there is no n-processes, f -resilient implementation of an α-register for α ≤ M (Section 4).

Computational Model and Definition of α-Registers

Message passing asynchronous distributed system We consider a distributed system made of a set Π of n asynchronous processes {p 1 , . . . , p n }, as described in e.g. [START_REF] Attiya | Distributed Computing : Fundamentals, Simulations, and Advanced Topics[END_REF]. Each pair of processes {p i , p j } is connected by a bi-directional channel. Channels are reliable and asynchronous, meaning that each message sent by p i to p j is received by p j after some finite, but unknown, time ; there is no global upper bound on message transfer delays. The algorithm in Section 3 assumes FIFO channels, that is for any pair of processes p i , p j , the order in which the messages sent by p i to p j are received is the same as the order in which they are sent. An execution is a possibly infinite sequence of steps. Processes may fail by crashing. A process that crashes prematurely halts and never recovers. In an execution, a process is faulty if it fails and correct otherwise. f denote an upper bound on the maximal number of processes that may fail.

Definition of α-registers

As classical read/write registers, an α-register supports two operations : WRITE(v), where v is value taken from some set V and READ(). A WRITE(v) operation returns an acknowledgment ok and a READ() returns a value u ∈ V ∪ {⊥}, ⊥ being the initial value of the α-register. In an admissible execution, no process starts a WRITE(v) or READ() operation while its previous operation, if any, has not returned. The execution interval I(op) of an operation op by process p lasts from the invocation of op until it returns ; if p never returns, I(op) has no end. Two operations op 1 and op 2 are concurrent if I(op 1 ) ∩ I(op 2 ) = / 0. A terminating operation op 1 precedes operation op 2 if I(op 1 ) ∩ I(op 2 ) = / 0 and I(op 1 ) ends before I(op 2 ) begins, written op 1 ≺ op 2 . An operation op is active in an interval I if I ∩ I(op) = / 0. To simplify the exposition, we assume without loss of generality that no two distinct WRITE() operations have the same input value. We will write op 1 op 2 if op 1 precedes or is concurrent to op 2 .

In any admissible execution e, a α-register satisfies the following properties.

1. Termination. Any READ() or WRITE(v) operation performed by a correct process terminates. 2. Non-spurious value. For any terminating READ() operation R that returns u, either u = ⊥ or there exists a WRITE(u) operation W such that W R. 3. Chronological read. Let R, R ′ be two terminating READ() operations performed by the same process in that order and let u, u ′ be the values returned. If u = ⊥, then u ′ = ⊥ and WRITE(u) WRITE(u ′ ). 4. Non-triviality. Let R be a READ() operation by process p, returning value u. If there is a WRITE() operation by p that precedes R, u = ⊥. Moreover, if W is the last WRITE() operation by p that precedes R, WRITE(u) is either W or a WRITE() operation W ′ by another process such that W W ′ .

5.

Propagation. Let u ∈ V such that a correct process performed a terminating WRITE(u) or a READ() returning u. Eventually, for every terminating READ() with return value u ′ , then WRITE(u) WRITE(u ′ ).

6. α-Bounded reads. Let R 1 , . . . , R ℓ be terminating READ() operations performed in an interval I , returning values {u 1 , . . . , u ℓ } = V R . Let V W be the set of values written during I ( ∀v ∈ V W , some Write(v) was active during I ). Then, V O = V R \ V W , the set of old values read during I , is of size at most α.

This section presents a protocol (Algorithm 3.1) that implements a single-writer multiple-readers (SWMR) α-register in an asynchronous system in which up to f ≤ n -1 processes may fail, with α = 2M -1, where

M = 2 f -n + 2 if f ≥ n
2 and M = 1 otherwise. The algorithm assumes that channels are FIFO.

Algorithm 3.1 SWMR α-register (code for process p i )

vr i , tsr i ← v i ,ts i ; seq i ← seq i + 1 ; Qr i ← / 0 ; Qe i ← / 0 ; n iter ← n iter + 1 ; 13: wait until |Qr i ∪ Qe i | ≥ n -f ; 14: until (|Qe i | ≥ n -f ) or (n iter ≥ N) ⊲ N = (4 f + 2)(⌊ n n-f ⌋ + 1)
if Accept i [ j] > 0 then Accept i [ j] ← Accept i [ j] -1 23: else v i ,ts i ← v,ts ; Accept i [1..n] ← [2, . . . , 2] ⊲ if Accept i [ j] = 0 24:
send UPDATE(seq i , v i ,ts i , seq) to p j

As in the ABD protocol [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF], each time a new value is written it is first associated with a unique timestamp (line 6). As there is a single writer, no two values are associated with the same timestamp. Each process p i maintains a pair of local variables v i ,ts i which store the most recent value p i knows of together with its timestamp. We say that p i accepts a pair v,t when p i changes v i ,ts i to v,t (line 23).

Although the timestamps are unbounded integers in this algorithm, it is possible to have a similar implementation that only uses a finite number of different timestamps. This can be done by using the principles described in [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF], but would probably need a larger namespace for timestamps.

Processes constantly exchange messages of type UPDATE containing data of the form (sq, v,ts , osq), where v,ts is the local v i ,ts i variable of the sender. The sq and osq are sequence numbers such that a process can determine whether this message is related to its current operation or not.

Write() operations The implementation of a WRITE(v) operations is similar to the implementation in the ABD protocol [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF]. After a new timestamp t has been associated with v line 6, the writer p n changes its local variable v n ,ts n to v,t . It then waits until each process in a quorum of (nf ) processes have accepted v,t , and the operation then returns (line 7-line 8).

Values dissemination

The new pair v,t is disseminated by the UPDATE messages sent by the writer : once v n ,ts n has been changed, every UPDATE sent by p n contains v,t , until a new WRITE() starts.

We want α to be as small as possible. To that end, the algorithm first bounds the number of messages sent but not delivered. Indeed, at any time, each channel contains at most 2 messages. Hence, at any given time, the system contains at most O(n 2 ) distinct values stored either locally by the processes or carried by not yet delivered messages. Of note, α is unbounded for the ABD protocol when used with f ≥ n/2.

Next, to further decrease α, the algorithm tries to reduce the number of values accepted by each process. Each process p i is endowed with an array Accept i [1..n] with one entry per process. Initially, Accept i [ j] = 2 and at any time, Accept i [ j] ∈ {0, 1, 2} for any j, 1 ≤ j ≤ n. Accept i [ j] < 2 means that p i knows that its current value is outdated by p j 's current value (line 21 -line 22). However, p i does not update immediately v i ,ts i with the more recent pair v,t it has just received. Indeed, this pair may no longer be stored by any process, that is v,t is only contained in messages not yet delivered. Instead, the algorithm ensures that when p i changes v i ,ts i to v,t , v,t is actually stored locally by some process at some time since p i discovers that v i ,ts i contains an outdated pair (line 21-line 23). Hence, for any given interval I, each process p i may accept and thus read only one value among the values carried by the messages it its input channels at the beginning of I. Therefore, assuming that no WRITE() operations overlap I, α = O(n). A finer analysis, taking into account the fact values read in the absence of concurrent WRITE() operations are accepted by at least nf processes, leads to α = 2M -1 = 4 f -2n + 3.

Read() operations A READ() operation (line 10-line 15) by process p i consists in up to N = O( f n n-f ) iterations. At the beginning of iteration s, the variable vr i ,tsr i is updated, and the two sets Qe i and Qr i , intended to contain processes that hold a pair equal to or more recent than, respectively, vr i ,tsr i , are emptied (line 12). An iteration terminates when p i knows that at least nf processes store values at least as recent as vr i (line 13). The READ() operation terminates (1) immediately if |Qe i | ≥ nf , i.e., for at least nf processes p j , there is a time at which v j = vr i or (2) after N iterations have been performed.

Condition (1) may never be reached in any number of iterations if the READ() operation is concurrent to a large number of WRITE() operations. But, if the READ() operation is performed in the absence of concurrent WRITE() operations, condition (1) will necessarily be reached in less than N iterations, as shown in [START_REF] Bonnin | α-register[END_REF].

The proof of this algorithm, i.e., the fact that this algorithm satisfies the properties of an α-register with α = 2M -1, is presented in [START_REF] Bonnin | α-register[END_REF].

Lower bound

In [START_REF] Bonnin | α-register[END_REF], a lower bound has also been proven, presented as the following theorem : Theorem 4.1. Let n, f such that f ≥ n 2 . For any implementation of a SWMR α-register for n processes that tolerates f failures, α ≥ M.

The idea of the proof is to assume there exists an algorithm implementing an α-register with α < M, and then to construct a family of executions leading to M distinct values being returned by READ() operations during a period without WRITE(). Those executions are described both at high level, with the calls of operations by some processes, and lower level, with the forced delay of messages in channels.

R éf érences