Cécile Delcourt
email: <cecile.delcourt@isped.u-bordeaux2.fr

Jean-François Korobelnik

Pascale Barberger-Gateau

Marie-Noëlle Delyfer

Rougier Marie-Bénédicte

Mélanie Le Goff

Florence Malet

Colin Joseph

Jean-François Dartigues

C Cile Delcourt

Jean-Fran Ois Korobelnik

Marie-No Lle Delyfer

Rougier Marie-B N

Lanie Le Goff

Jean-Fran Ois Dartigues

The ALIENOR (Antioxydants, Lipides Essentiels, Nutrition et Maladies Oculaires) Study

Keywords: macular degeneration, glaucoma, nutrition, antioxidants, fatty acids, epidemiology

est destinée au dépôt

are multifactorial, involving genetic and environmental factors. Some risk factors have been identified in the last decades, such as smoking (for cataract and ARM) ( ), ultraviolet light exposure (for cataract) ( ), high intraocular pressure (IOP) (for glaucoma) ( ). More 5 6 7 recently, major genetic polymorphisms associated with ARM have been described ( ).

-9

There is a growing interest in the role of nutritional factors in these diseases, because they are amenable to modification, by acting on food habits or by supplementation with specific nutrients. In particular, the results of the Age-Related Eye Disease Study (AREDS), showing a reduction in the incidence of late ARM with supplementation in antioxidants and zinc, have raised the hope to prevent or delay the degenerative diseases of the eye ( ). 10

Study rationale

Mainly three types of nutritional factors are currently investigated for their potential protection against eye ageing: antioxidants, the carotenoids lutein and zeaxanthin and omega 3 polyunsaturated fatty acids (PUFA).

The retina is particularly susceptible to oxidative stress because of the high level of in-site reactive oxygen species production, due in particular to light exposure and high metabolic activity ( ). Opacification of the lens is due to oxidation of the structural proteins of the 11 lens, inducing their aggregation ( ). A role for oxidative stress in glaucoma has also been suggested ( ). While the role of [START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF] 13 -14

antioxidants in the protection against the development of late ARM is supported both by epidemiological studies ( ) and a large 15 interventional trial ( ), results have been more conflicting with regard to cataract. Indeed, while numerous observational studies 10 evidenced a 20 to 50 reduction of the risk for nuclear cataract in subjects with high dietary intakes or high plasma concentrations of % %

vitamin C and vitamin E, several large randomized clinical trials did not show any reduction in the risk of cataract with antioxidant supplementation ( ). Only the REACT study showed a limited effect of supplementation with vitamin C, E and beta-carotene on cortical 15 cataract ( ). Finally, with regard to glaucoma, very few epidemiological studies are available ( ). [START_REF] Lt | The Roche European American Cataract Trial (REACT): a randomized clinical trial to investigate the efficacy of an oral antioxidant micronutrient mixture to slow progression of age-related cataract[END_REF] 17 -18

A more recent research domain regards the role of two carotenoids, lutein and zeaxanthin, for the protection of the retina and the lens.

These carotenoids accumulate in the centre of the retina, named macula, where they are known as the macular pigment ( ), and they are 19 also the only carotenoids found in the lens ( ). Besides their antioxidant properties, they probably act as a filter against the phototoxic 20 effects of blue light ( ). Epidemiological data are still very scarce in this field, with few studies being prospective, and few including 19 plasma measurements ( ). 19

Finally, omega 3 PUFA include a precursor (alpha-linolenic acid), and three long-chain derivatives (eicosapentaenoic acid (EPA), docosapentaenoic acid (DPA) and docosahexaenoic acid (DHA)). Long chain omega 3 PUFA have important structural and protective functions in the retina ( ). A recent meta-analysis of nine epidemiological studies showed a 38 reduced risk for ARM in subjects with 21 % high consumption of omega 3 PUFA and fish (the major dietary source of long-chain omega 3 PUFA) ( ). Overall, few of these studies 22

were prospective and none included biological measurement of fatty acids status.

Besides a potential direct effect of these nutrients in the eye, their role could be mediated by an effect on atherosclerosis and vascular diseases. Indeed, a role for antioxidants and omega 3 PUFA has been reported in vascular diseases ( ) and ARM and cardiovascular 23 -24 disease share common risk factors, such as smoking, obesity ( ) and hypertension ( ), suggesting a contribution of vascular disease to 25 26 the pathogenesis of ARM.

Thus, there is a growing scientific background to the role of nutrition in the pathogenesis of age-related eye diseases, which may lead to prevention means for these diseases. There is a need for epidemiological prospective studies in different countries and cultures, which will take into account genetic, vascular and nutritional factors (including assessment of dietary intake and biological measurements), since all those dimensions may act in interaction. In particular, very few studies have been performed in Europe, although dietary habits and lifestyle are very different from the United States. We report the design and baseline characteristics of a population-based epidemiological study conducted in France, including the prevalence of eye diseases.

Population and methods

Study aims

The Alienor (Antioxydants, Lipides Essentiels, Nutrition et maladies OculaiRes) Study is a population-based prospective study aiming at assessing the associations of age-related eye diseases (ARM, glaucoma, cataract, dry eye syndrome) with nutritional factors (in particular antioxidants, macular pigment and fatty acids), determined from plasma measurements and estimation of dietary intakes. It also takes into account other major determinants of eye diseases, including gene polymorphisms, environmental factors and vascular factors.

A secondary aim is to assess the quality of eye care in an elderly French population, and the consequences of eye diseases and visual impairment, in particular in terms of disability and depression.

Study sample

Subjects of the Alienor Study were recruited from an ongoing population-based study on the vascular risk factors for dementia, the Three City (3C) Study ( ). The 3C Study included 9294 subjects aged 65 years or more from three French Cities (Bordeaux, Dijon and Montpellier), among which 2104 were recruited in Bordeaux. Subjects were contacted individually from the electoral rolls. They were initially recruited in 1999 2001 and followed-up about every two years since ( ). Data collected at each examination included

cognitive testing with diagnosis of dementia and assessment of vascular risk factors. In addition, at baseline, fasting blood and DNA samples were collected and kept frozen at 80 C.

-°The

Alienor study consisted in an eye examination, which was proposed to all participants in the third follow-up (2006 2007) of the -3C cohort of Bordeaux. Among the 1450 participants of the third follow-up of the Bordeaux cohort of the 3C Study, 963 (66.4 ) % participated in the Alienor Study ( ). A first follow-up eye examination of these subjects is currently underway and we plan to Figure 1 perform at least two additional follow-up examinations, about every two years.

Eye examination

The eye examination took place in the Department of Ophthalmology of the University Hospital of Bordeaux. The eye examination included a recording of ophthalmological history, measures of visual acuity and refraction, two 45 non mydriatic color retinal °photographs (one centred on the macula, the other centred on the optic disc), measures of intraocular pressure and central corneal thickness and break-up time test. A self-completed questionnaire on risk factors specific to the eye (sunlight exposure, television and computer use) and dry eye symptoms (Ocular Surface Disease Index (OSDI) ( )) was filled at home and brought back on the day of the eye 28 examination.

Visual acuity measurements included current and best corrected far visual acuity, using ETDRS charts (Light House Low Vision, New York, NY) and current and best corrected near visual acuity, using the Parinaud charts (Luneau SAS, Chartres, France), which is the usual near vision test used by French ophthalmologists. Refraction was measured using autorefractometer (Speedy K, Luneau, France). Retinal photographs were performed using a non mydriatic retinograph (TRC NW6S, Topcon, Japan). Intraocular pressure was measured with pneumotonometer (KT 800, Kowa, Japan) and central corneal thickness using Pachpen (Accutome Inc., Malvern Pa, USA). Tear break-up time (BUT) test was performed at slit lamp. A fluorescein strip (Fluo Plus, Gecis, France) was applied in the lower eyelid fornix, and the patient asked to blink three times and look straightforward. The breakup time of the tear film observed under cobalt blue filtered light of the slit lamp microscope was recorded with a stopwatch. The mean of three consecutive tear BUT tests was taken into consideration.

Retinal photographs were interpreted in duplicate by two specially trained technicians. Inconsistencies between the two interpretations were adjudicated by a retina specialist for classification of ARM and other retinal diseases, by a glaucoma specialist for classification of glaucoma. All cases of late ARM, other retinal diseases and glaucoma were reviewed and confirmed by specialists.

Classification of ARM

Retinal photographs were interpreted according to the international classification ( ) and to a modification of the grading scheme 29 used in the Multi-Ethnic Study of Atherosclerosis for drusen size, location and area ( ). Late ARM was defined by the presence of 30 neovascular ARM or geographic atrophy within the grid (3000 m from the foveola). Neovascular ARM included serous or hemorrhagic μ detachment of the retinal pigment epithelium (RPE) or sensory retina, subretinal or sub-RPE hemorrhages and fibrous scar tissue.

Geographic atrophy was defined as a discrete area of retinal depigmentation, 175 m in diameter or larger, characterized by a sharp border μ and the presence of visible choroidal vessels. Five cases of late ARM had no gradable photographs and were classified by using ophthalmological history of ARM and ARM therapy (in particular antiangiogenic agents and photodynamic therapy), and confirmed by their treating ophthalmologist. Because etiologies of neovascular and atrophic ARM may be different, we separated two groups: subjects with neovascular ARM (with or without geographic atrophy) and subjects with late atrophic ARM (geographic atrophy without neovascular ARM).

Early ARM was classified in two groups (in the absence of late ARM): early ARM 1 (soft distinct drusen without pigmentary abnormalities or pigmentary abnormalities without large drusen (>125 m)); early ARM 2 (soft indistinct drusen and/or reticular drusen μ and/or soft distinct drusen associated with pigmentary abnormalities (hyper-or hypopigmentation)). Soft distinct and indistinct drusen were larger than 125 m in diameter and with uniform density and sharp edges or decreasing density from the center outwards and fuzzy μ edges, respectively. Pigmentary abnormalities were defined as areas of hyperpigmentation and/or hypopigmentation (without visibility of choroidal vessels).

Subjects were classified according to their worse eye, into one of the five exclusive groups: no ARM, early ARM 1, early ARM 2, late atrophic ARM, late neovascular ARM. These definitions of ARM are similar to those used in other large epidemiological studies of ARM, such as the Blue Mountains Eye Study ( ), the Rotterdam Study ( ), or the EUREYE Study ( ), in order to facilitate comparisons 31 32 33 with these studies.

Other retinal diseases

Retinopathy was defined by the presence of microaneurysms and/or soft exudates and/or blot haemorrhages and/or flame-shaped haemorrhages, anywhere on the colour photograph centred on the macula. Epiretinal membranes were defined by the presence of preretinal fibrosis, with retinal folds. The earlier stages, often named cellophane macular reflex, without retinal folds, were not recorded.

Classification of glaucoma

Glaucoma was classified according to the classification proposed by Foster PJ and colleagues ( ), using two steps. Firstly, vertical 34 cup:disc ratio (VCDR) and minimal rim:disc ratio were estimated from optic disc photographs. Subjects were classified as suspects for glaucoma when, in at least one eye, we observed a vertical cup:disc ratio greater or equal to 0.65 and/or a minimal rim:disc ratio lower or equal to 0.1 or an asymmetry of cup disc:ratio between eyes greater or equal to 0.2.

An additional eye examination was performed in 76 of 86 subjects suspect for glaucoma (88 ). This examination included a % white-on-white visual field examination (Octopus 101, Interzeag International, Switzerland), an examination of the optic disc using Heidelberg Retinal Tomograph (HRT II, Heidelberg Engineering, Germany), an evaluation of the irido-corneal angle by gonioscopy, a measure of intraocular pressure using Ocular Response Analyser (Reichert Inc, New York). With regard to visual field testing, reliability was considered as acceptable when the percentages of false-positive and false-negative were below 33 .

%

Glaucoma was defined according to 3 levels of evidence. In category 1, diagnosis was based on structural evidence (VCDR on optic nerve photographs greater or equal to 0.7 and/or asymmetry of VCDR greater than 0.2 and/or minimal rim:disc ratio lower or equal to 0.1) associated with functional evidence (visual field showing at least three contiguous non-edge points with corrected p<1 , of which at least % one point with corrected p<0.5 ), in the absence of other disease (in particular vascular) that might explain the findings. Category 2 was % based on advanced structural damage (VCDR greater or equal to 0.8 or asymmetry of VCDR greater than 0.3) with unproven field loss (unfeasible or unreliable visual field examination). Category 3 included subjects with very low vision (visual acuity <3/60) for whom optic disc photographs and visual field could not be obtained, but glaucoma morbidity was confirmed by their treating ophthalmologist. All glaucoma cases were classified according to category 1 criteria, except one case with category 2 criteria, and one case with category 3 criteria.

Other end-points

Since the eye examination did not include pupil dilation, it was impossible to assess lens opacities. The cataract endpoints therefore relied solely on cataract extraction (confirmed by observation at slit lamp of the absence of the natural lens). Several features of dry eye syndrome were explored: self-reported dry eye, current use of artificial tears, OSDI score ( ) and tear BUT test. 28

Nutritional data

Nutritional data have been collected during the 4 examinations performed in the framework of the 3C with food manufacturers and specific nutrient measurements performed by the Institut des Corps Gras (ITERG, Bordeaux, France)).

Besides, the food frequency questionnaire (FFQ) included 148 food and beverage items, for which the frequency of intake was recorded in 11 classes (from never to 7 times per week), for each of the 3 main meals and 3 between-meal snacks. Concordance between FFQ and 24 h dietary recall was assessed for fatty acids, and showed acceptable correlations between number of weekly servings of foods obtained from the FFQ and the corresponding intakes of fatty acids in the dietary recall ( ). 40

At the next two follow-ups (2003 2004 and 2006 2007) a simplified food frequency questionnaire was administered by the -psychologists during the home visit, in order to detect modifications in dietary habits. We previously published detailed methods and distributions of dietary intake ( ) and of plasma antioxidants ( ) and fatty acids ( , ) in the 3C Study. 41 -43 [START_REF] Helmer | Association between antioxidant nutritional indicators and the incidence of dementia: results from the PAQUID prospective cohort study[END_REF] 36 45

Vascular factors and other variables

At each examination (baseline and follow-ups), a face-to-face administered questionnaire assessed socio-demographic data, health status and general risk factors. In particular, it included a recording of history of cardiovascular disease and vascular risk factors. For subjects who reported the occurrence of vascular events during follow-up, further medical data was obtained general practitioners, specialists and hospital records.

Examination also included an inventory of all medications used during the preceding month, which were subsequently coded according to the French translation of the WHO ATC classification ( , Centre National Hospitalier d Information sur le www.theriaque.org ' M dicament). The clinical examination included several measures of systolic and diastolic blood pressure, using a digital electronic é tensiometer (OMRON M4) and anthropometric measurements (height, weight, and waist, arm, calf and cranial circumferences). In addition, at baseline, an ultrasound examination of the carotid arteries was performed in 73 of participants below the age of 85 years.

%

Measurement of blood glucose and lipids were centralized and performed at the Biochemistry Laboratory of the University Hospital of Dijon. Centralized facilities for genotyping are provided by the Lille Genop le. The polymorphisms of apolipoprotein E and the Y402H ô polymorphism of Complement Factor H are currently available on the whole cohort. Finally, a genomewide scan was performed on the whole sample ( ).

The main strength of this study is that it combines clinical, dietary, biological and genetic information, collected over a 7 year period of time before the first eye examination. This will allow to assess the associations of eye diseases with history of nutritional status (collected prospectively), while taking into account vascular and genetic background. Another strength is the fact that we collected both dietary and blood biomarkers of nutritional status. This may give some important insight into the bioavaibility of nutrients.

A potential limitation to our results would be the questionable representativeness of the sample. Indeed, about two third of the participants in the 3C Study accepted the eye examination. This subsample over-represented subjects of younger age and higher socio-economic status, among subjects participating to the 3C Study, who are themselves imperfectly representative of the general population ( ). The included subjects may therefore be healthier and have different lifestyles, in particular concerning diet and physical 27 activity, than the general population. This may in turn affect the distribution of nutritional and vascular characteristics, or the prevalence of eye diseases. However, this appears to have had little impact on the distribution of the parameters of interest in the Alienor study. Indeed, participants were mostly comparable to non participants with regard to nutritional and vascular parameters, after adjustment for age and gender. Among the numerous tested variables, only plasma HDL-cholesterol and triglycerides were significantly different between participants and non participants. Moreover, the prevalence rates of the major ocular end points in participants were very close to those observed in studies performed in similar populations (ARM ( , ), glaucoma ( ), retinal vein occlusion ( ), retinopathy ( ), [START_REF] Augood | Prevalence of age-related maculopathy in older Europeans: the European Eye Study (EUREYE)[END_REF] epidemiological data are particularly scarce, and comparability of studies is low because of differing definitions of dry eye disease.

However, the prevalence of all dry eye disease dimensions appear high in the present population, by comparison with previous studies ( 55). Finally, although the distributions of nutritional and vascular parameters and the prevalence of ocular endpoints may be different -59 from the general population, this is unlikely to bias the estimation of the associations of eye diseases with the vascular and nutritional parameters.

Another potential limitation to this study is the small number of cases for some of the end-points, at least at baseline (late ARM, open-angle glaucoma). However, using the observed distribution of risk factors and endpoints at the first eye examination, and an alpha-level of 5 , statistical power is at least 80 for differences of clinical significance in nutritional risk factors (20 or 30 ), for all

% % % % end-points.
In conclusion, this study confirms the high prevalence of eye diseases in this sample of French elderly subjects. It will add to the knowledge of the epidemiological associations of nutrition with the risk for eye diseases, in a European cohort study. Such information may help design future interventional studies, in terms of the type of nutritional intervention (dietary and/or supplementation, target nutrients and dose) and of target populations (primary or secondary interventions, high-risk populations based on genetic background or other risk factors, populations with nutrient deficiencies). Future interventional studies might be common with other age-related disorders (cardiovascular disease, dementia, Alzheimer s disease, etc ), because of common nutritional determinants. Finally, this study also

' …
includes very complete data on cognition, depressive symptoms, disability and activities of daily living, which will allow the study of the consequences of eye diseases and visual impairment in this sample of French elderly subjects.

Ackowledgements:

This study received financial support from Laboratoires Th a (Clermont-Ferrand, France). This sponsor participated in the design of the é study, but not in the collection, management, statistical analysis and interpretation of the data, nor in the preparation, review or approval of the present manuscript. Cecile Delcourt had full access to all the data in the study and takes responsibility for the integrity of the data and the accuracy of the data analysis. 1.1 0.2 ; 3. 12.9 7.5 18.3 33.8 28.2 39.4

Footnotes:

[ -]

34.6 30.7 38.5

[ - ]
Current use of artificial tears ( )

%
19.5 14.9 24.1

  This research followed the tenets of the Declaration of Helsinki. Participants gave written consent for the participation in the study. The design of this study has been approved by the Ethical Committee of Bordeaux (Comit de Protection des Personnes Sud-Ouest et é Outre-Mer III) in May 2006.

  5

  Distribution of features of dry eye in the Alienor sample (2006 2008) ( 95 confidence interval or mean (standard deviation))

  Study, in Bordeaux. They consist in biological measurements from the fasting blood samples performed during the baseline examination (1999 2001) and dietary assessment at baseline and follow-up examinations. Plasma vitamins A and E, malondialdehyde (MDA) and fatty acids were measured at the Laboratory of Biochemistry and Molecular Biology of the University of Bordeaux 2. Vitamin A and E were measured by reversed-phase high performance liquid chromatography (HPLC). MDA was analysed by a modified method ( ).

	35	Plasma fatty acid
	composition was determined by gas chromatography, after extraction of plasma total lipids with hexane/isopropanol ( ). In addition, 36
	measurements of plasma carotenoids are currently being performed.
	With regard to dietary data, a brief dietary questionnaire was collected at baseline (1999 2001). At Bordeaux, during the first -
	follow-up examination (2001 2002), 1796 subjects participated in a nutritional survey. A 24 h dietary recall and a food-frequency

-

questionnaire were administered at home by dieticians. The dieticians received collective training and monitoring in order to optimize the standardization of the nutritional interviews. With regard to the 24 h dietary recall, nutrient intakes were estimated from food intakes using the BILNUT software (SCDA Nutrisoft, Cerelles, France), which includes food composition tables for France ( ). When necessary, this 37 table was completed by other sources (a French food composition table from the Institut National de la Sant et de la Recherche M dicale é é ( ), a food composition table edited by Souci et al ( ), the United States Department of Agriculture Nutrient Database, direct contact 38 39

Table 1

 1 Declaration of interest: C Delcourt: consultant for Bausch&Lomb, Novartis, Pfizer JF Korobelnik: consultant for Alcon, Novartis, Bayer, Bausch & Lomb, Allergan P Barberger-Gateau: lecture fees for Lesieur, Danone, Bausch & Lomb J Colin: consultant for Addition Technologies Inc, Alcon, Abbott AMO, Optical Express, Horus Pharma, Gene Signal SAS F Malet: consultant for Abbott Medical Optics France, Cibavision. MB Rougier: lecture fees from Zeiss. MN Delyfer, M Le Goff, JF Dartigues: none Klaver CC . Causes and prevalence of visual impairment among adults in the United States . Arch Ophthalmol . 2004 ; 122 : 477 -485 2 . Cigolle CT , Langa KM , Kabeto MU , Tian Z , Blaum CS . Geriatric conditions and disability: the Health and Retirement Study . Ann Intern Med . 2007 ; 147 : 156 -164 3 . Laitinen A , Sainio P , Koskinen S , Rudanko SL , Laatikainen L , Aromaa A . The association between visual acuity and functional limitations: findings from a nationally Global data on visual impairment in the year 2002 . Bull World Health Organ . 2004 ; 82 : 844 -851 5 . Solberg Y , Rosner M , Belkin M . The association between cigarette smoking and ocular diseases . Surv Ophthalmol . 1998 ; 42 : 535 -547 6 . McCarty CA , Taylor HR . A review of the epidemiologic evidence linking ultraviolet radiation and cataracts . Dev Ophthalmol . 2002 ; 35 : 21 -31 7 . Weinreb RN , Khaw PT . Primary open-angle glaucoma . Lancet . 2004 ; 363 : 1711 -1720 8 . Scholl HP , Fleckenstein M , Charbel Issa P , Keilhauer C , Holz FG , Weber BH . An update on the genetics of age-related macular degeneration . Mol Vis . 2007 ; 13 : 196 -205 9 . Yates JR , Sepp T , Matharu BK . Complement C3 variant and the risk of age-related macular degeneration . N Engl J Med . 2007 ; 357 : 553 -561 10 . Age-Related Eye Disease Study Research Group . A randomized, placebo-controlled, clinical trial of high-dose supplementation with vitamins C and E, beta carotene, and zinc for age-related macular degeneration and vision loss: AREDS report no. 8 . Arch Ophthalmol . 2001 ; 119 : 1417 -1436 59 . Viso E , Rodriguez-Ares MT , Gude F . Prevalence of and associated factors for dry eye in a Spanish adult population (the Salnes Eye Study) . Ophthalmic Epidemiol . Comparison of nutritional status between participants and non participants in the Alienor Study (mean (SD)).

	References:
	1 . Congdon N , O Colmain
	representative population survey . Ophthalmic Epidemiol . 2007 ; 14 : 333 -342
	4 . Resnikoff S , Pascolini D , Etya ale

' B , ' D . = Non

participants (n 487) = p-value * Plasma measurements in 1999 2000

	-	N 752 =	N 354 =
	Fatty acids (in of total fatty acids) %
	Saturated	39.6 (5.4)	40.2 (5.6)	0.09
	Monounsaturated	22.9 (3.7)	23.2 (3.9)	0.48
	n-6 PUFA	33.3 (4.9)	32.2 (5.7)	0.06
	n-3 PUFA	4.5 (1.3)	4.3 (1.3)	0.07
	EPA	1.1 (0.6)	1.0 (0.6)	0.13
	DHA	2.5 (0.7)	2.4 (0.8)	0.12
	Alpha-tocopherol (mg/l)	15.9 (4.9)	15.7 (5.0)	0.41
	Dietary

intake from 24h recall in 2001 2002

	-	N 913 =	N 375 =
	Energy intake (kcal)	1722 (541)	1627 (558)	0.15
	Alcohol ( TEI) %	4.9 (5.8)	4.4 (5.4)	0.84
	Proteins ( TEI) %	18.2 (4.8)	18.2 (4.6)	0.80
	Carbohydrates ( TEI) %	46.0 (10.1)	46.7 (9.5)	0.50
	Total fat ( TEI) %	30.9 (8.8)	30.7 (9.1)	0.45
	Saturated fat ( TEI) %	13.1 (4.7)	13.5 (4.8)	0.66
	MUFA ( TEI) %	11.1 (4.0)	10.9 (4.0)	0.46
	n-6 PUFA ( TEI) %	3.4 (2.4)	3.2 (2.1)	0.26
	n-3 PUFA ( TEI) %	0.6 (0.7)	0.6 (0.6)	0.07
	EPA ( TEI) %	0.1 (0.2)	0.1 (0.2)	0.15
	DHA ( TEI) %	0.2 (0.4)	0.1 (0.4)	0.21
	Vitamin E (mg/1000 kcal)	3.9 (2.6)	3.7 (2.2)	0.58
	Vitamin C (mg/1000 kcal)	53.4 (45.0)	51.6 (43.1)	0.47
	:

Vascular risk factors (in 2006 2008)

  adjusted for age and gender using logistic regression ** except for smoking and plasma lipids, which were measured at baseline of the 3C Study(1999 2001)

	Systolic blood pressure (mm Hg)		143.8 (21.4)	143.0 (24.2)	0.22
	Diastolic blood pressure (mm Hg)		75.4 (11.0)	74.5 (12.5)	0.59
			N 902 =	N 408 =
	Total cholesterol (mmol/l)		5.78 (0.98)	5.81 (0.99)	0.92
	LDL-cholesterol (mmol/l)		3.63 (0.85)	3.62 (0.85)	0.76
	HDL-cholesterol (mmol/l)		1.59 (0.40)	1.56 (0.41)	0.01
	Triglycerides (mmol/l)		1.23 (0.60)	1.37 (0.72)	<0.0001
			-
	TEI: total energy intake
	-	**
	Self-reported history of:
	Hypertension		486 (50.7)	257 (54.8)	0.12
	Diabetes		109 (11.4)	62 (13.0)	0.11
	Treatment for angina pectoris		77 (8.2)	45 (9.5)	0.99
	Myocardial infarction in the last 3 years	10 (1.0)	11 (2.3)	0.11
	Stroke in the last 3 years		27 (2.8)	19 (4.0)	0.89
	Angioplasty in the last 3 years		31 (3.2)	14 (2.9)	0.97
	Smoking				0.11
	-never		614 (63.8)	345 (70.9)
	-former		303 (31.4)	115 (23.6)
	-current		46 (4.8)	27 (5.5)
	Body mass index (kg/m ) 2		25.9 (4.1)	25.8 (5.0)	0.50
	Waist circumference (cm)		91.7 (12.3)	92.3 (13.1)	0.09

*

Table 2

 2 Prevalence of major eye diseases in the Alienor sample (2006 2008) ( 95 confidence interval )

	-	% [ %	]
			73 79 years -	≥ 80 years	Total

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

[START_REF] Boscia | Protein oxidation and lens opacity in humans[END_REF]

Results

As expected, by comparison with non participants, participants in the Alienor Study showed some differences in socio-demographic status: they were younger (79.8 years versus 82.9 years), more often males (38.1 in participants versus 31.4 in non participants), had 1 plasma triglycerides (somewhat lower) and HDL-cholesterol (slightly higher).

shows the prevalence of major eye diseases in the participants of the Alienor study. Retinal photographs were gradable for Table 2 ARM in at least one eye for 879 of 963 participants (91 ). The prevalence of late ARM (neovascular or atrophic) increased sharply with % age, from 3.5 and 1.8 in men and women aged 73 to 79 years, to 6.8 and 10.4 in men and women aged 80 years or more, women and epiretinal membranes in 6.3 of men and 2.4 of women.

% %

Glaucoma could be classified in 936 of 963 participants (97.2 ). The prevalence of open-angle glaucoma increased moderately, from % 4.8 and 3.1 in men and women aged 73 to 79 years, to 6.0 and 6.1 of men and women aged 80 years or more. We observed no case % % % of angle closure glaucoma. Seventeen of the 45 glaucoma cases (37.8 ) were previously undiagnosed. In addition, 10.0 of men and % % women were currently under therapy for ocular hypertension and 37.1 of men and 50.2 of women had had cataract extraction.

% %

The distribution of the features of dry eye disease is presented in . As expected, dry eye was more frequent in women, both for Table 3 self-declared dry eye (34.6 in women versus 21.8 in men), current use of artificial tears (21.1 in women versus 11.3 in men) and % % % % symptomatology (mean OSDI score 24.9 in women versus 17.1 in men). However, tear BUT test was similarly low in women and men (mean 6.8 seconds in women and 6.9 seconds in men). There was a slight increase with age of use of artificial tears and OSDI score, but not of self-declared dry eye or tear BUT.

Discussion


Thi Huyen

Chau Nguyen
email: nguyent@ensma.fr

Pascal Richard Lisi

/ Ensma

Nathan Fisher
email: fishern@cs.wayne.edu

The Fully Polynomial-Time Approximation Scheme for Feasibility Analysis in Static-Priority Systems with Arbitrary Relative Deadlines Revisited

We consider sporadic tasks with static priorities and arbitrary deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing worst-case response times for this task model. Fisher and Baruah proposed in 2005 an approximate feasibility test running in polynomial time according to an accuracy parameter (i.e., approximation scheme or FPTAS). We show that this algorithm is valid for the Rate Monotonic scheduling policy, but must be slightly modified to be applicable for arbitrary priority assignment. We also introduce some improvements to achieve a higher efficiency. We illustrate the improved algorithm on a detailed example.

Introduction

A feasibility test is an algorithm used to check if a task set is feasible or not. It can be either used off-line if the system workload is predictable or on-line if new tasks can be admitted at run-time. Two main and linked approaches are used to check whether a task is feasible or not: Response Time Analysis (RTA) that returns the worst-case response time of a task (i.e., the maximum amount of time between a release and a completion of jobs generated by the task) or a Processor Demand Analysis (PDA) that returns a boolean value, feasible or infeasible. In both cases, exact feasibility tests are known for static priority tasks with arbitrary deadlines [START_REF] Lehoczky | Fixed priority scheduling of periodic tasks with arbitrary deadlines[END_REF]. However, it is already known that worst-case response time computation is an NP-hard problem [START_REF] Eisenbrand | Static-priority real-time scheduling: Response time computation is np-hard[END_REF] and cannot be approximated within a constant approximation factor, even in the context of tasks with constrained-deadlines (i.e., deadlines are less than or equal to activation periods). Nevertheless, positive results are known using the resource augmentation techniques [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF][START_REF] Fisher | A polynomial-time approximation scheme for feasibility analysis in static-priority systems with bounded relative deadlines[END_REF][START_REF] Bini | A responsetime bounds in fixed-priority scheduling with arbitrary deadlines[END_REF][START_REF] Nguyen | Approximation techniques for response-time analysis of static-priority tasks[END_REF]. Please notice that the feasibility problem of static priority tasks with constrained-deadlines is still an open issue from the computational point of view: pseudo-polynomial time algorithms are known but it is not known if this problem is NP-hard or not.

However, these exact tests have very efficient implementations in practice that render them quite suitable for feasibility analysis of FP systems. Nevertheless, there are certain scenarios in which schedulability tests cannot be used, where the complexity and execution time of exact tests may become huge drawbacks as in dynamic systems, optimization of large scale systems, etc. For these problems, a pseudo-polynomial algorithm for computing the task set feasibility may be unacceptably slow; instead, it may be acceptable to use a faster algorithm that provides an approximate, rather than exact, analysis [START_REF] Chakraborty | Approximate schedulability analysis[END_REF][START_REF] Fisher | A polynomial-time approximation scheme for feasibility analysis in static-priority systems with bounded relative deadlines[END_REF][START_REF] Bini | A responsetime bounds in fixed-priority scheduling with arbitrary deadlines[END_REF][START_REF] Nguyen | Approximation techniques for response-time analysis of static-priority tasks[END_REF]. This research. In [START_REF] Fisher | A polynomial-time approximation scheme for feasibility analysis in static-priority systems with bounded relative deadlines[END_REF][START_REF] Nguyen | Approximation techniques for response-time analysis of static-priority tasks[END_REF] is studied the approximate feasibility analysis of static priority tasks with constraineddeadlines. In this paper, we revisit the approximate feasibility analysis presented in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] that considers sporadic tasks with static priorities and arbitrary deadlines to be executed upon a uniprocessor platform. Pseudo-polynomial time algorithms are known for computing worst-case response times for this task model. Fisher and Baruah proposed in 2005 an approximate feasibility test running in polynomial time according to an accuracy parameter (i.e., approximation scheme or FPTAS). We will show that, while the algorithm remains correct for rate-monotonic (RM) priority assignments, the algorithm is not correct for non-RM priority assignments and requires some modifications. We revised the algorithm in order to correct the detected problem and we also provide an improvement. We illustrate the revised algorithm on a detailed example.

Organization. Section 2 presents static-priority tasks with arbitrary deadlines. Section 3 presents the task model and basic functions for schedulability analysis of fixedpriority task systems. We shall detail the main ideas of Fisher and Baruah FPTAS. Then, we give a counter example of Fisher and Baruah's FPTAS for arbitrary priority assignment and its correctness for RM. Section 4 presents the revised algorithm according to the detected problems in the former algorithm, presents the revised algorithms and proves its correctness. Lastly, we conclude in Section 5 and give details for some future works.

Task model and notations

A sporadic task τ i , 1 ≤ i ≤ n, is defined by a worstcase execution time (WCET) C i , a relative deadline D i and a period T i which is the minimal interval of time between two consecutive job instances of task τ i . We assume that deadlines are not related to periods (i.e., tasks with arbitrary deadlines). We suppose that ∀i, C i > 0. The l th job of τ i is denoted as τ i,l . The utilization factor of task τ i is the fraction of time that τ i requires the processor:

U i def = C i /T i .
The utilization factor of the task set is:

U def = n j=1 U j .
We assume that sporadic tasks to be run upon a same processor are independent and do not suspend themselves. All the tasks have static priorities that are set before starting the application and never changed at run-time. A task can be preempted by any task of higher priority. At any time, the highest priority task is selected among ready tasks. Without loss of generality, we assume that tasks are indexed in decreasing order of their priorities: τ 1 is the highest priority task and τ n is the lowest one.

The total execution time requested by task τ i over time interval [0, t) is defined by the request bound function:

RBF(τ i , t) def = t T i C i (1)
Then, the cumulative processor demand function of tasks having a priority higher or equal to τ i,l is defined by:

W i,l (t) def = lC i + j<i RBF(τ j , t) (2)

Analysis of Fisher and Baruah Approximation Scheme

Next, we first present the main ideas of the Fisher and Baruah approximation scheme for checking the feasibility of a sporadic task with an arbitrary deadline. Then, we provide a counter example of an important results used in the algorithm. We think that these problems cannot be solved without changing some formulas and proofs. Nevertheless, please notice that the algorithm structure will be preserved.

Fisher and Baruah Algorithm

In order to approximate the request bound function according to an error bound 1 + (accuracy parameter, 0 < < 1), the algorithm presented in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] uses the approximation principle introduced in [START_REF] Fisher | A polynomial-time approximation scheme for feasibility analysis in static-priority systems with bounded relative deadlines[END_REF] for sporadic tasks with constrained-deadlines (i.e., D i ≤ T i for all tasks): we consider the first (k -1) steps of RBF(τ i , t), where k is defined as k def = 1/ -1 and a linear approximation, thereafter. From this definition, we verify that (k + 1) ≥ 1/ .

Hence, an approximate resquest-bound function can be defined as follows:

δ(τ i , t) def = RBF(τ i , t) for t ≤ (k -1)T i , (t + T i )U i otherwise. (3)
Thus, up to time (k-1)T i , no approximation is performed to evaluate the total execution requirement of τ i , and after that it is approximated by a linear function with a slope equal to the utilization factor of task τ i . The approximate cumulative processor demand function of each job τ i,l is defined as follows:

W i,l (t) = lC i + j<i δ(τ j , t) (4)
Fisher and Baruah's algorithm [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] (denoted FB05 below and presented in Algorithm 1) is based on analysing a polynomial number of scheduling points in the Lehoczky's testing set ( [START_REF] Lehoczky | Fixed priority scheduling of periodic tasks with arbitrary deadlines[END_REF]) using the approximate cumulative processor demand function. In a first stage of FB05 algorithm, the testing set is explored for checking the feasibility of jobs of τ i (i.e., jobs with completion time prior or equal to max j∈1,...,i-1 {(k -1)T j }). Thus, the considered testing set is:

Si def = {t = bT a : a = 1 . . . i, b = 1 . . . k -1} ∪ {0} (5)
We call two elements t a-1 and t a (t a-1 < t a ) in some set adjacent if there exists no t in that set satisfying t a-1 < t < t a . Using this testing set, the first stage determines whether all jobs of task τ i with deadlines less than t = max {j∈{1...i} {(k -1)T j } are schedulable. If no deadline is missed up to time t, then the first stage algorithm returns the lowest indexed job (denoted h) whose request is not satisfied by time t.

Task τ i may generate a pseudo-polynomial number of jobs in the level-i busy period. Nevertheless, Fisher and Baruah claim that in every interval (t a-1 , t a ] defined by two adjacent scheduling points in the testing set (i.e., there is no scheduling point between t a-1 and t a in the testing set), only one job of τ i can have its deadline in (t a-1 , t a ]. They defined a simple way to compute the index of the first job of τ i released in (t a-1 , t a ]. For that purpose, a "close" approximation of the workload function is defined to determine the jobs having the execution requests satisfied by time t (Equations 5 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF]) are:

W i (t) = δ(τ i , t) + j<i δ(τ j , t) (6)
Based on that function, Fisher and Baruah indicate that the index of the most recently released job of τ i to have its execution request satisfied by time t is: where Z i (t) determines the number of jobs l ≤ t Ti such that W i (t) > t is defined as follows:

t T i -Z i (t) (7
Z i (t) = max W i (t) -t C i , 0 (8)
As a consequence, in every interval between two adjacent scheduling points in Si , at most one job of τ i is tested to be feasible or not. The complete algorithm of the Ap-proxFirstStage defined in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] is presented in Algorithm 1.

Since the level-i busy period is not necessarily fully explored in the first stage (i.e., when the first stage returns lowest active values), the feasibility status of the analysed tasks can be still open. To cope with that problem, a second stage is run to check in constant time the task using a linear approximation (i.e., a worst-case response time upper bound computed in linear time). The second stage takes as input the job index h returned by the first stage (i.e., the job request is not satisfied by time t).

The main algorithm first performs a call to the first stage. If it returns the index h of a job, then the second stage is called for checking in constant time if τ i,h is feasible or not. Hereafter, we only detail the first stage since the original second stage remains unchanged in the revised algorithm.

Analysis of Fisher and Baruah's Algorithm

We first show that the Fisher and Baruah is not correct under arbitrary priority assignment. Then, we show that the algorithm is correct under the RM scheduling policy.

Problems in the general case. FB05 correctness is based on the fact that at most one job must be checked between two subsequent scheduling points of the testing set Si . We shall see that is not true using a counter-example.

In the same way, the function defined the number of jobs for completion at each scheduling point in the approximate test (i.e., Equation 6 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF]) need also to be modified to correct the proofs (i.e., Lemma 4 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] cannot be proved correct using Equation 6).

We think that the mentioned problems cannot be easily corrected without modifying the formulas presented in the previous section and also the corresponding proofs must be revisited for proving the correctness of the revised algorithm. Nevertheless, we shall prove that through these formula modifications, all these problems can be fixed while preserving the main ideas of the algorithm. We modified the previous functions to enforce the Fisher and Baruah's Lemma 4 correctness. Furthermore, we improve the algorithm by introducing in the first stage a test for checking if the level-i busy period is "approximately" completed or not. Such a modification will decrease the computational effort for checking the feasibility of the analysed task.

We first prove that the observation which is the base for the first stage of the approximation scheme proposed in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] is not correct for non-RM priority assignments: several jobs of the analysed task can complete between two subsequent scheduling points. Proof: Let's consider the counter example below which is also illustrated in the Figure 1:

Theorem 1 The observation "For any two adjacent ele

- ments t 1 , t 2 ∈ S i , |t 2 -t 1 | ≤ T i . Therefore,
τ i = {τ 1 , τ 2 } , P rio(τ 1 ) > P rio(τ 2 ) T 1 = mT 2 k = 2
where k is the number of steps before the approximation.

From Eq. ( 5) we have

S 2 def = {t = bT a | a = 1, . . . , 2, b = 1, . . . , 1} {t = 0} = {t 1 = 0, t 2 = T 1 , t 3 = T 2 }
Note that zero is only defined for some simplifying proof statements. Let's consider t 2 , t 3 which are adjacent in the set S 2 , we have:

|t 2 -t 3 | = |T 1 -T 2 | = |(m -1)T 2 | = A
Increasing m, we obviously can make A > T 2 and by choosing appropriately the relative deadline D 2 < T 2 , m -1 deadlines of τ 2 can elapse between t 2 and t 3 which contradicts the statement mentioned.

We now will prove that using the definition Eq. ( 8) is not correct for establishing Lemma 4 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF].

Theorem 2 The statement "'If l > t

Ti -Z i (t) and t ≥ (l -1)T i , then W i,l (t) > t"' is not correct.

Proof: We prove this by giving a counter-example in which 3 conditions below are satisfied:

1. t ∈ ((l -1)T i , (l -1)T i + D i ] 2. l = t Ti -Z i (t) + 1 3. W i,l (t) ≤ t
First, we choose an arbitrary integer k strictly greater than two to be the number of steps before approximation k.

Then, we choose the task system as follows (every task is presented under the format

τ i =< C i , D i , T i >): τ i = {τ 1 , τ 2 } , P rio(τ 1 ) > P rio(τ 2 ) τ 2 =< (k + 1)αT 2 , kT 2 , T 2 > with an arbitrary real number α such that 0 < α < 1 k+2 τ 1 =< k(1 -(k + 2)α)T 2 , D 1 , kT 2 > Then we choose the time instant t = T 1 = kT 2 . Note that t > (k -1)T 2 (⇒ δ(τ 2 , t) = (t + T 2 )U 2 ) and that since k > 2 ⇒ t < (k-1)kT 2 = (k-1)T 1 (⇒ δ(τ 1 , t) = RBF(τ 1 , t) = t T1 C 1 )
. Finally, we choose i = 2 and we now prove condition 1:

W 2 (t) = δ(τ 2 , t) + j<2 δ j (t) = δ(τ 2 , t) + δ(τ 1 , t) = (t + T 2 )U 2 + t T 1 C 1 = (kT 2 + T 2 )(k + 1)α + k(1 -(k + 2)α)T 2 = kT 2 + αT 2 > kT 2 = t. So W 2 (t) > t ⇒ max W2(t)-t C2 , 0 = Z 2 (t) ≥ 1 ⇒ If we choose l = t T2 -Z 2 (t) + 1 then l ≤ t T2 - 1 + 1 = t T2 = kT2 T2 = k ⇒ (l -1) < k ⇒ t = kT 2 > (l -1)T 2 (a). Moreover, t = kT 2 ≤ (l -1)T 2 + kT 2 = (l -1)T 2 + D 2 (b)
From (a), (b), we have condition 1 is satisfied. Condition 2 is obviously satisfied by the construction of l.

Now we consider the last condition:

W i,l (t) = lC 2 + j<2 δ j (t) = t T 2 - W 2 (t) -t C 2 + 1 C 2 + δ(τ 1 , t) ≤ t T 2 - W 2 (t) -t C 2 + 1 C 2 + δ(τ 1 , t) = t T 2 C 2 + C 2 -W 2 (t) + δ(τ 1 , t) + t = t T 2 C 2 + C 2 -δ(τ 2 , t) + t = RHS
Replace t = kT 2 we have:

RHS = (k + 1)C 2 -(kT 2 + T 2 ) C 2 T 2 + t = t
Condition 3 is proved. hence we have the counter example of the Lemma 4 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF].

Correctness under RM. We will prove that even Rate Monotonic priority assignment (i.e., ∀i ∈ [1, n] :: (T 1 ≤ T 2 ≤ . . . ≤ T i )) the observation that only a single deadline elapse between adjacent testing set points is correct. However, Lemma 4 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] still requires some refinement for ensuring its correctness. We shall see later that a simple additional assumption leads to a correct version of Lemma 4 allowing to use the result into the algorithm Ap-proxFirstStage.

Theorem 3 The statement "If l > t

Ti -Z i (t) and t > (l -1)T i , then W i,l (t) > t" is not correct.

Proof: We prove this by giving a counter-example in which 3 conditions below are satisfied:

1. t > (l -1)T i 2. l = t Ti -Z i (t) + 1 3. W i,l (t) ≤ t
First, we choose an arbitrary positive integer k (to be the number of steps before starting linear approximations) and an arbitrary positive integer m.

Then, we choose the task system as follows:

τ i = {τ 1 , τ 2 } , P rio(τ 1 ) > P rio(τ 2 ) hence T 1 ≤ T 2 τ 2 =< C 1 , D 1 , T > τ 1 =< C 2 , D 2 , T >
where C 1 , C 2 , T are chosen such that:

k + m -1 k + m < C 1 + C 2 T = U 1 + U 2 = U < 1 (9)
Then, we choose the time instant t

= (k -1 + m)T . Note that t > (k -1)T = (k -1)T 1 = (k -1)T 2 (⇒ δ(τ 1 , t) = (t + T 1 )U 1 and δ(τ 2 , t) = (t + T 2 )U 2 ).
Now we choose the task to be considered i = 2 and l = t Ti -Z i (t) + 1 = t T2 -Z 2 (t) + 1 (hence by construction, condition 2 is satisfied). Now, we will prove condition 1:

We have: 9)

W 2 (t) = δ(τ 2 , t) + j<2 δ j (t) = δ(τ 2 , t) + δ(τ 1 , t) = (t + T )U = ((k -1 + m)T + T )U = ((k + m)T )U > ((k + m)T ) k + m -1 k + m from Eq. (
> (k + m -1)T = t. By definition, Z i (t) = max Wi(t)-t Ci , 0 . As proved above W 2 (t) > t =⇒ W2(t)-t C2 ≥ 1 =⇒ Z 2 (t) = W2(t)-t C2 ≥ 1. Since l = t T2 -Z 2 (t) + 1, we have: l ≤ t T 2 l < t T 2 + 1 (l -1)T 2 < t.
Condition 1 is satisfied. Now, we consider the last condition:

W 2,l (t) = lC 2 + j<2 δ j (t) = t T -Z 2 (t) + 1 C 2 + δ(τ 1 , t) ≤ t T - W 2 (t) -t C 2 + 1 C 2 + δ(τ 1 , t) = t T C 2 + C 2 -W 2 (t) + δ(τ 1 , t) + t = t T C 2 + C 2 -δ(τ 2 , t) + t = RHS
Replace t = (k -1 + m)T , we have the RHS equals t which implies that W 2,l (t) = t and Condition 3 is satisfied. This contradiction is then proved.

Thus, Lemma 4 is not correct for arbitrary t, but the statement holds for any t ≤ max j<i {(k -1)T j } and please notice that the algorithm ApproxFirstStage does not check for t beyond this value. Thus, we can show the algorithm is correct with a refinement of the supposition of the lemma for t in the range zero to max j<i {(k -1)T j }.

Lemma 1 If l > t Ti

-Z i (t), and t ∈

((l -1)T i < t, max j<i {(k -1)T j }] then W i,l (t) > t. Proof: Let a = t Ti -Z i (t) + 1 =⇒ l ≥ a, W i,l (t) ≥ W i,a (t)
For any l, choose an arbitrary t such that (l -1)

T i < t ≤ max j<i {(k -1)T j } =⇒ (a -1)T i < t ≤ max j<i {(k -1)T j }. Since t > (a -1)T i ⇐⇒ t Ti > a -1 ⇐⇒ t T ≥ a.
From definition of a, we obtain Z i (t) ≥ 1. As a consequence, since Z i (t) = max Wi(t)-t Ci , 0 , we obtain

Z i (t) = Wi(t)-t Ci ≥ 1.
We have:

W i,a (t) = aC i + j<i δ(τ j , t) = t T i -Z i (t) + 1 C i + j<i δ(τ j , t) > t T i C i -( W i (t) -t) + j<i δ(τ j , t) > t T i C i -W i (t) + j<i δ(τ j , t) + t > t T i C i -δ(τ i , t) + t = RHS 5 Under RM we have ∀i ∈ [1, n] :: (T 1 ≤ T 2 ≤ . . . ≤ T i ). As a consequence, t ≤ max j<i {(k -1)T j } =⇒ t ≤ (k -1)T i =⇒ δ(τ i , t) = RBF(τ i , t) = t
Ti . Replace this into RHS we have W i,a (t) > t. The lemma is proved.

Thus, using this previous restated Lemma 4 and under the RM scheduling policy, the algorithm ApproxFirstStage is correct.

Revised version of FB05 algorithm

We show now that the algorithm can be modified in order to be applicable for non-RM priority assignment. These modifications are all in the first stage of the original algorithm to enforce the FPTAS correctness.

Preliminary results

Based on this approximate W i,l (t), we define, for each given job τ i,l , an approximate intersection instant R i,l as: Definition 1 Let R i,l denote the first intersection between W i,l (t) and f (t) = t, then R i,l can be defined by:

R i,l def = min t | W i,l (t) = t (10)
Then we define Ni as the index of the last job in the first level-i busy period considered in our test:

Definition 2 Ni def = min l ∈ N | R i,l ≤ (l -1)T i + T i (11)
Finally, we define, for a given task τ i , the set of points constructing intervals to be tested in our approximation as:

S i def = {t = bT a | a = 1, . . . , i -1; b = 1, . . . , k -1} {0} {∞} (12)
Zero and infinite points are only introduced to simplify some proof statements. Furthermore, the relative deadline D i is not defined in the testing set but is directly exploited in the algorithm. We then define a primitive interval of some set as an interval (t a-1 , t a ] bounded by two adjacent points t a-1 and t a of that set.

From this section to the rest of this paper, in the context concerning the approximate algorithm (presented in the next subsections), we will use the term "a job τ i,l is completed" to indicate "the approximate processor demand function W i,l (t) cuts the processor capacity function" (i.e., f (t) = t), the term "meet the deadline" to indicate " R i,l ∈ [(l -1)T i , (l -1)T i + D i ] ", the term "the intersection time" to indicate "the approximate intersection time", and so on.

Notice that R i,l is just the first instant when W i,l (t) = t and not necessarily the completion time of τ i,l in the general case. But, these intersection points R i,l correspond to upper bounds on job completion times if they belong to the first level-i busy period, as stated in the following lemma:

Lemma 2 ∀i ≤ n, l ≤ Ni , R i,l > (l -1)T i First, we present the following properties of R i,l Lemma 3 ∀i ≤ n, let l, h two natural numbers such that l < h, then R i,l < R i,h Proof: By definition W i,h ( R i,h ) = R i,h . Moreover, l < h =⇒ W i,l (t) < W i,h (t). Therefore: W i,l ( R i,h ) < R i,h =⇒ ∃t * < R i,h :: ( W i,l (t * ) = t * ) Since R i,l def = min {t | W i,l (t) = t}, then R i,l ≤ t * and as a consequence R i,l < R i,h .

Now we prove Lemma 2:

Proof: If Ni = 1 then the lemma obviously holds as the first intersection is always after 0.

If Ni > 1 then by Definition 11, ∀i ≤ n, l ≤ Ni -1, R i,l > (l -1)T i + T i > (l -1)T i . From Lemma 3, we know that R i, Ni > R i, Ni-1 = ( Ni -1 -1)T i + T i = ( Ni -1)T i . The lemma is proved.
Hence, we have a necessary and sufficient condition for checking if a job of a task τ i is approximately feasible as follows:

Theorem 4 l ≤ Ni :: R i,l ≤ (l -1)T i + D i if, and only if, ∃t ∈ ((l -1)T i , (l -1)T i + D i ] : W i,l (t) ≤ t Proof:
The "only" if direction statement is straightforward from Lemma 2 and the definition of R i,l . For the "if" direction, let us choose an arbitrary t * ∈ ((l -1)T i , (l -

1)T i + D i ] : W i,l (t) ≤ t. As W i,l (t) is a non-decreasing left-continuous step function and W i,l (0) = lC i > 0, then ∃t int ≤ t * :: ( W i,l (t int ) = t int ) From definition of R i,l =⇒ R i,l ≤ t int ≤ t * =⇒ R i,l ≤ (l -1)T i + D i . Using Lemma 2, we have R i,l > ((l -1)T i and thus R i,l ∈ ((l -1)T i , (l -1)T i + D i ].
The theorem is proved.

Properties of primitive interval

Now we can use R i,l to verify, in the context that the first level-i busy period has not been terminated, if τ i,l meet its deadline or not.

Based on the results presented in the previous section, we will propose in the next sections an algorithm that verifies the feasibility of τ i by analyzing all the intersection instant R i,l located in a given primitive intervals of S i . In order to reduce this complexity, now we are looking for some properties allowing for testing the feasibility of the first job in each primitive interval. Precisely, the first job of τ i will have a longer upper bound on the response time than any other response time of τ i that is computed from an Ri,j in the same primitive interval.

First of all, we prove the following property of all jobs of a task τ i that completed in the same primitive interval of S i : Lemma 4 For any i ≤ n, l and h two natural numbers such that l < h and any two adjacent scheduling points

t 1 < t 2 in S i such that R i,l , R i,h ∈ (t 1 , t 2 ] then R i,h < R i,l + (h -l)T i .
Proof: Let T denote the set of all tasks τ j such that j < i and (k -1)T j ≤ t 1 . In other words, T is the set of all tasks whose the approximate RBF becomes a linear function after t 1 . Note that T ⊆ 1..i -1.

We can rewrite W i,l (t) in (t 1 , t 2 ] as follows:

W i,l (t) = lC i + j<i δ(τ j , t) = lC i + j<i,j / ∈T RBF(τ j , t) + j∈T (t + T j )U j = lC i + j<i,j / ∈T RBF(τ j , t) + j∈T T j U j + t j∈T U j Let A = lC i + j<i,j / ∈T RBF(τ j , t) + j∈T T j U j , B = j∈T U j .
Then we have:

W i,l (t) = A + Bt
Note that at all instant t ∈ (t 1 , t 2 ], A and B are constant.

Since from definition of

W i,l (t), W i,h (t) = W i,l (t) + (h -l)C i =⇒ we obtain W i,h (t) = (h -l)C i + A + Bt Now we compute R i,l , R i,h according to these new for- mulas of W i,l (t) and W i,h (t). As R i,l is the intersection of W i,l (t) with y = t in (t 1 , t 2 ] =⇒ R i,l = A 1 -B .
Similarly,

R i,h = A + (h -l)C i 1 -B
Hence we have:

R i,h -R i,l = A + (h -l)C i 1 -B - A 1 -B = (h -l) C i 1 -B = (h -l)T i U i 1 -B = RHS
Replacing B = j∈T u j , we have:

1 -B = 1 - j∈T U j ≥ 1 - j<i U j > 1≤j≤n U j - j<i U j > U i
Hence we obtain:

U i 1 -B < 1 =⇒ RHS < (h -l)T i .
The lemma is proved. From the lemma above, we obtain the main property about response time of jobs in a primitive interval: given two adjacent points t 1 , t 2 of S i , provided that the level-i busy period have not been terminated before t 1 , then the next theorem implies: 1. To verify if any jobs completed in (t 1 , t 2 ] have met their deadlines, we just need to check the job having been released sooner in the interval (t 1 , t 2 ].

2. To verify if between those 2 jobs there exists a job that is completed before the activation of its subsequent instance, it is sufficient to check the job having been released later. This latter property allows to check if the level-i busy period is "approximately" completed or not.

Theorem 5 For any i ≤ n, l, h ∈ N, l < h and any 2 adjacent points

t 1 < t 2 in S i such that R i,l , R i,h ∈ (t 1 , t 2 ]
then we have:

R i,l ≤ (l -1)T i + D i =⇒ R i,h ≤ (h -1)T i + D i , (13a) R i,h > (h -1)T i + T i =⇒ R i,l > (l -1)T i + T i (13b)
Proof: First, we prove Eq. (13a):

R i,l ≤ (l -1)T i + D i R i,h -(h -l)T i ≤ (l -1)T i + D i (for R i,h -(h -l)T i < R i,l from Lemma 4) R i,h ≤ (h -1)T i + D i
Now we prove Eq. (13b):

R i,h > (h -1)T i + T i R i,l + (h -l)T i > (h -1)T i + T i (for R i,h < R i,l + (h -l)T i from Lemma 4) R i,l > (l -1)T i + T i
The theorem is proved.

The following result follows directly from Theorem 5 for the necessary condition (the sufficient condition is obvious):

Corollary 1 ∀t 1 , t 2 ∈ S i , Let first and last respectively be defined as:

f irst def = min l ∈ N | R i,l ∈ (t 1 , t 2 ] last def = max l ∈ N | R i,l ∈ (t 1 , t 2 ]
then the following inequalities are always satisfied:

R i,f irst ≤ (f irst -1)T i + D i ⇐⇒ (14a) ∀l ∈ [f irst, last] : R i,l ≤ (l -1)T i + D i , (14b) R i,last > (last -1)T i + T i ⇐⇒ (14c) ∀l ∈ [f irst, last] : R i,l > (l -1)T i + T i (14d)
From the corollary above, we obtain that in each primitive interval there might be a pseudo-polynomial number of jobs of τ i having been completed, but provided that the first level-i busy period have not already been terminated in previous primitive intervals, then we just need to check only the first job against its deadline to conclude the feasibilities of all these jobs. Moreover, in order to verify if the level-i busy period has been terminated in the analysed primitive interval, it is sufficient to check only the last job against the activation of its subsequent instance. As a consequence, in every primitive interval, if the last job of τ i is completed before the next release of τ i , then it is unnecessary to test the subsequent primitive intervals (i.e., the level-i busy period has been completed in the current primitive interval).

Finally, we are looking for some method to identify the indexes of the first and the last job having been completed in a given primitive interval of S i .

For this purpose, we first introduce the following function that is used to determine the set of jobs that have their approximate execution requests satisfied by any time instant t,

W i (t) def = RBF(τ i , t) + j<i δ(τ j , t) (15)
W i (t) represents a "close" approximate to the cumulative requests of task τ i and all higher priority tasks with respect to any given time t. In comparison , W i,l (t) is only a "close" approximation when t lies in the interval ((l -1)T i , lT i ]. Please note that the function corresponds to the modification of Equation 6(i.e. Equation 13 in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF]).

Notice that the number of active jobs at time t would be O(D i /T i ). The next function is used to identify the index of the most recently released job of τ i to have its execution request approximately satisfied by time t.

I i (t) def = t T i - W i (t) -t C i ( 16
)
I i (t) is based on a modification of the function Z i (t) defined in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF].Precisely, we removed the maximum function in order to prove the two next lemmas. If the value of I i (t) is not negative then it is used to determine the index of the most recently released job to have its execution request satisfied (according to the approximation scheme) by time t. By finding the index of the most recently released job of τ i to complete execution with respect to time t, we can determine in constant time the set of active jobs that have their execution requests satisfied at or prior to t.

Lemma 5 If

I i (t) > 0 then ∀l ∈ {1, . . . , I i (t)} , W i,l (t) ≤ t Proof: Let b = I i (t) =⇒ l ≤ b, W i,l (t) ≤ W i,b (t)
We have:

W i,b (t) = bC i + j<i δ(τ j , t) = t T i - W i (t) -t C i C i + j<i δ(τ j , t) = t T i C i - W i (t) -t C i C i + j<i δ(τ j , t) ≤ t T i C i - W i (t) -t C i C i + j<i δ(τ j , t) ≤ t T i C i + j<i δ(τ j , t) -W i (t) + t ≤ W i (t) -W i (t) + t = t
The lemma is proved.

Lemma 6 If , t ∈ ((l -1)T i , (l -1)T i +D i ] and l > I i (t) then W i,l (t) > t Proof: Let a = I i (t) + 1 =⇒ l ≥ a, W i,l (t) ≥ W i,a (t)
We have:

W i,a (t) = aC i + j<i δ(τ j , t) = t T i - W i (t) -t C i + 1 C i + j<i δ(τ j , t) > t T i C i -( W i (t) -t) + j<i δ(τ j , t) > t T i C i + j<i δ(τ j , t) -W i (t) + t > W i (t) -W i (t) + t = t
The lemma is proved. Note that this function I i (t) cannot be applicable for t = ∞. Besides, for the last primitive interval of S i , which has ∞ as its right bound, it is also unnecessary to verify if the first level-i busy period has been terminated within or not (since U < 1, the level-i busy period will complete before time ∞). Therefore, we divide all the jobs of τ i into two sets: one for jobs completed prior or equal to max j∈1,...,i-1 {(k -1)T j } (i.e., completed in some primitive intervals of S i that is not the last one) and one for jobs completed in (max j∈1,...,i-1 {(k -1)T j } , ∞) (i.e., completed in the last primitive interval of S i ). In this latter case, all approximate request bound functions are linear functions. Due to these remarks, the algorithm is still divided into two stages as in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF].

First Stage: Job with completion time prior or

equal to max j∈1,...,i-1 {(k -1)T j } We construct an algorithm which determines, for any 2 adjacent points t 1 , t 2 ∈ S i {∞}, which jobs of τ i have their execution requests satisfied in (t 1 , t 2 ]. Also, we can check in constant time whether all these jobs respect their respective deadlines as well as whether the level-i busy period has been terminated in that interval. The complete algorithm is presented in Algorithm 2.

We summarized the main differences between the revised version and the original version:

• The following functions have been changed: Z i (t)

and W i (t),

• the FBApproxFirstStage checks if a job has its deadline in the current primitive interval. But, it does not check if the job completes or not within the interval. Note that in the revised version, the I i (t) function is computed at the beginning of each iteration and compared with the value of the previous iteration (i.e., last active value), whereas it is called at the end of the FBApproxFirstStage algorithm. Thus, in the revised version, it is checked if there is at least one job completed in the current primitive interval.

Second Stage:

Job with completion time after max j∈1,...,i-1 {(k -1)T j } The second stage is not modified in comparison with the original second stage algorithm. Please consult [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] for details.

Detailed example

We illustrate the approximation scheme proposed in this paper by considering the task set presented in [START_REF] Lehoczky | Fixed priority scheduling of periodic tasks with arbitrary deadlines[END_REF]: τ 1 (C 1 = 26, D 1 = 40, T 1 = 70) and τ 2 (C 2 = 62, D 2 = 140, T 2 = 100). Using Deadline Monotonic, we assign to τ 1 the higher priority. We now consider the feasibility of τ 2 using both exact and approximation methods. The exact response time analysis stops after considering 7 jobs in the level-i busy period: for the τ 2,7 the response time is R 2,7 = 96 < 100 = T 2 (see [START_REF] Lehoczky | Fixed priority scheduling of periodic tasks with arbitrary deadlines[END_REF] for details). Since all jobs meet their deadline (i.e., R i,l ≤ (l -1)T 2 + D 2 ) then τ 2 is stated feasible. Now, we analyze the feasibility of τ 2 using the approximation scheme. We choose = 0.25 thus k = 3 and S i = {0, 70, 140, ∞}. The two stages of the Approximate analysis will be executed. In the first stage we consider jobs completed prior or at t = 140 by using ApproxFirst-Stage.

• Before the first iteration of the loop in ApproxFirst-Stage, last active = 0. where f (t) = t intersects W 2,last (t), we obtain t = R 2,last = R 2,1 = 114 > (1 -1).100 + 100 =⇒ The first level-i busy period have not been terminated yet in this interval. We assign last active = last = 1 then we continue testing.

• As there is no more t a to test, we return last active+ 1 = 1 + 1 = 2.

Now we turn to consider the jobs completed after t = 140 using ApproxSecondStage. h used in this stage is the return value of the ApproxFirstStage hence h = 2 =⇒ R i,h = R 2,2 = 238, (63) < (2-1).100+140. Therefore, we conclude τ 2 is feasible.

Figure 1 .

 1 Figure 1. The interval between two adjacent elements in S i can be greater than T i

• 1 >

 1 In the first iteration we consider the first primitive interval (0, 70], t a = t 1 = 70. Since I 2 (70) = 70 100 -W2(70)-70 62 = 0 = last active we jump to the next iteration. last active remains 0. • Now we consider (70, 140], t a = t 2 = 140. Since I 2 (140) = 140 100 -W2(140)-140 62 = last active we set f irst = last active + 1 = 0 + 1 = 1, next = I 2 (140) = 1. Computing the instant in the interval (70, 140] where f (t) = t intersects W 2,f irst (t), we obtain t = R 2,f irst = R 2,1 = 114 < (1 -1).100 + 140 =⇒ There exists no job completed in this interval that has violated its deadline. Computing the instant in the interval (70, 140]

) Algorithm 1. Fisher and Baruah ApproxFirstStage input

  Let t a-1 be the adjacent element prior to t a in Si ; Let y be the total execution requirement of all jobs of priority greater than τ i released at time t a ; a = (t a-1 , W i,lowest active (t a-1 ) + y) ; b = (t a , W i,lowest active (t a )); Determine if the line (a, b) intersects with f (t) = t ; Let this point of intersection be t ; if t > (lowest active -1)T i + D i then return "not feasible" else lowest active=lowest active+1 ; end

	:
	τ = C[n], T [n], D[n] : array of integers	/ * Task parameters * /
	i : integer	/ * Index of the analysed task * /
	k : integer	/ * The FPTAS accuracy parameter * /
	output: lowest active : integer	/ * Lowest active job * /
	Construct Si using Equation 5	/ * Ordered set of scheduling points * /
	lowest active=1	/ * index of job to be analysed * /
	foreach t

a ∈ Si -{0} do if t a > (lowest active-1)T i + D i then / * a job completes in (t a-1 , t a ] * / x = max 0, ta Ti -Z i (t) ; lowest active = max(x + 1, lowest active); end return lowest active;

Conclusions

We revised the approximation scheme presented in [START_REF] Fisher | A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines[END_REF] to achieve its correctness for arbitrary priority assignment. We prove that the original algorithm is valid for RM. We then propose several formula modifications, a complete revised version of the algorithms for improving its efficiency. We already improve that function in [START_REF] Nguyen | Approximation techniques for response-time analysis of static-priority tasks[END_REF] for approximating worst-case response time of static priority tasks with constrained-deadlines. We want to extend the feasibility test presented here to compute approximate worst-case response time with guaranteed resource augmentation ratio.