William F Mills

Paco Bustamante

Rona A R Mcgill

Orea R J Anderson

Stuart Bearhop

Yves Cherel

Stephen C Votier

Richard A Phillips

Mercury exposure in an endangered seabird

Keywords: pollution, seabirds, Thalassarche chrysostoma, heavy metals, Southern Ocean

Introduction

Mercury (Hg) is a pervasive environmental contaminant that can negatively impact humans and wildlife [START_REF] Scheuhammer | Effects of environmental methylmercury on the health of wild birds, mammals, and fish[END_REF]. Hg derives from both natural and anthropogenic sources; however, human activities have increased the global Hg pool and projections suggest that global anthropogenic Hg emissions are likely to increase [START_REF] Selin | Global biogeochemical cycling of mercury: A Review[END_REF][START_REF] Streets | Projections of global mercury emissions in 2050[END_REF][START_REF]Global Mercury Assessment 2018[END_REF].

In its gaseous, elemental form, Hg can travel long distances to remote locations through atmospheric transport [START_REF] Fitzgerald | The case for atmospheric mercury contamination in remote areas[END_REF]. Once deposited in the marine environment, inorganic Hg (iHg) is converted (through methylation) to the more toxic form, methyl-Hg ([CH3Hg] + ; or MeHg), which, once assimilated, bioaccumulates in marine organisms and biomagnifies through food webs from lower to higher trophic levels [START_REF] Bargagli | Environmental contamination in Antarctic ecosystems[END_REF][START_REF] Driscoll | Mercury as a global pollutant: Sources, pathways, and effects[END_REF]. Long-lived marine top predators, such as many seabird species, are therefore potentially exposed to high Hg concentrations through their prey [START_REF] Bearhop | Bioamplification of mercury in great skua Catharacta skua chicks: the influence of trophic status as determined by stable isotope signatures of blood and feathers[END_REF].

Seabirds are often used as indicators of marine ecosystem health [START_REF] Furness | Seabird as monitors of the marine environment[END_REF], including the bioavailability of Hg [START_REF] Carravieri | Penguins as bioindicators of mercury contamination in the Southern Ocean: birds from the Kerguelen Islands as a case study[END_REF][START_REF] Carravieri | Penguins as bioindicators of mercury contamination in the southern Indian Ocean: geographical and temporal trends[END_REF]. Studies of seabird communities in the Southern Hemisphere, from Antarctica to the subtropics, have revealed considerable interspecific variation in Hg contamination [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Becker | Feather mercury concentrations in Southern Ocean seabirds: variation by species, site and time[END_REF][START_REF] Becker | Feather mercury levels in seabirds at South Georgia: influence of trophic position, sex and age[END_REF][START_REF] Blévin | Wide range of mercury contamination in chicks of Southern Ocean seabirds[END_REF][START_REF] Polito | Differing foraging strategies influence mercury (Hg) exposure in an Antarctic penguin community[END_REF][START_REF] Carravieri | Mercury exposure in a large subantarctic avian community[END_REF]. The Procellariiformes (albatrosses and petrels) are the most abundant and diverse seabird group in the Southern Ocean, and albatrosses (Diomedeidae) are consistently the most contaminated family of birds [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF][START_REF] Thompson | Comparison of the levels of total and organic mercury in seabird feathers[END_REF][START_REF] Thompson | The chemical form of mercury stored in South Atlantic seabirds[END_REF]. Phylogeny exerts a major influence on Hg exposure among albatrosses, such that members of the Diomedea genus typically display the highest levels [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF]. Indeed, in the oceans, only some marine mammals show higher Hg concentrations [START_REF] Muirhead | Heavy metal concentrations in the tissues of seabirds from Gough Island, South Atlantic Ocean[END_REF]. Hg contamination within seabird populations is often highly variable and governed by factors such as age, sex, breeding status and foraging ecology [START_REF] Bearhop | Bioamplification of mercury in great skua Catharacta skua chicks: the influence of trophic status as determined by stable isotope signatures of blood and feathers[END_REF][START_REF] Polito | Differing foraging strategies influence mercury (Hg) exposure in an Antarctic penguin community[END_REF][START_REF] Bearhop | Variability in mercury concentrations of great skuas Catharacta skua: the influence of colony, diet and trophic status inferred from stable isotope signatures[END_REF]. Moreover, at high concentrations, Hg can have fitness consequences [START_REF] Goutte | Survival rate and breeding outputs in a high Arctic seabird exposed to legacy persistent organic pollutants and mercury[END_REF][START_REF] Tartu | To breed or not to breed: Endocrine response to mercury contamination by an Arctic seabird[END_REF][START_REF] Tartu | Corticosterone, prolactin and egg neglect behavior in relation to mercury and legacy POPs in a long-lived Antarctic bird[END_REF]. To date, the drivers of intraspecific variation in Hg contamination, and its consequences for breeding and survival, have only been studied in one albatross species, the wandering albatross (Diomedea exulans) [START_REF] Bustamante | High feather mercury concentrations in the wandering albatross are related to sex, breeding status and trophic ecology with no demographic consequences[END_REF][START_REF] Carravieri | Wandering albatrosses document latitudinal variations in the transfer of persistent organic pollutants and mercury to southern ocean predators[END_REF][START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF][START_REF] Goutte | Demographic consequences of heavy metals and persistent organic pollutants in a vulnerable long-lived bird, the wandering albatross[END_REF].

The present study focuses on grey-headed albatrosses (Thalassarche chrysostoma) breeding at South Georgia-a remote island south of the Antarctic Polar Front (APF) in the Atlantic sector of the Southern Ocean. South Georgia hosted 47 674 breeding pairs of this species in 2003/2004, which represented by far the largest population globally (approx. 50%), but has been in long-term decline and is currently listed as endangered by theWorld Conservation Union [START_REF] Poncet | Recent trends in numbers of wandering (Diomedea exulans), blackbrowed (Thalassarche melanophris) and grey-headed (T. chrysostoma) albatrosses breeding at South Georgia[END_REF][START_REF] Phillips | The conservation status and priorities for albatrosses and large petrels[END_REF]. This species is extremely long-lived [START_REF] Froy | Contrasting drivers of reproductive ageing in albatrosses[END_REF], and forages at mid-to high trophic levels-predominantly consuming cephalopods, but also fish and Antarctic krill (Euphausia superba) [START_REF] Phillips | Sexual segregation in distribution, diet and trophic level of seabirds: Insights from stable isotope analysis[END_REF][START_REF] Mills | Long-term trends in albatross diets in relation to prey availability and breeding success[END_REF]. During the non-breeding period, free from the constraints of central place foraging, birds disperse across a wide range of oceanic habitats though mainly targeting the Subantarctic Zone (SAZ) between the APF and the Subtropical Front (STF) [START_REF] Clay | Proximate drivers of spatial segregation in non-breeding albatrosses[END_REF][START_REF] Mills | Stable isotopes demonstrate intraspecific variation in habitat use and trophic level of non-breeding albatrosses[END_REF][START_REF] Croxall | Global circumnavigations: tracking year-round ranges of nonbreeding albatrosses[END_REF]. Hg exposure tends to be high in this species, with intrapopulation variation reflecting its generalist feeding habits and wide foraging range [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF]. In this cross-sectional study, we measured feather THg concentrations in a very large sample of individuals of known age, sex and breeding history. The vast majority (>90%) of the THg excreted into albatross body feathers is MeHg [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF][START_REF] Thompson | Comparison of the levels of total and organic mercury in seabird feathers[END_REF][START_REF] Renedo | Assessment of mercury speciation in feathers using species-specific isotope dilution analysis[END_REF]. Our main aimswere to: (i) analyse long-term trends in Hg exposure of this species at South Georgia (1989-2014); (ii) examine large-scale spatial variation in Hg exposure by comparing our data with other breeding populations [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Becker | Feather mercury levels in seabirds at South Georgia: influence of trophic position, sex and age[END_REF][START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF][START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF]; (iii) assess Hg exposure in relation to intrinsic factors (sex, age and breeding history) and, using stable isotope ratios as proxies, to foraging habitat (δ 13 C) and trophic level (δ 15 N) and (iv) test for short-term relationships between Hg exposure and subsequent breeding outcome. This final point is of particular interest, given that breeding success in this population is low and highly variable, contributing to its long-term decline [START_REF] Pardo | Additive effects of climate and fisheries drive ongoing declines in multiple albatross species[END_REF].

Material and methods

(a) Study site and sample collection

Fieldwork was carried out at Bird Island, South Georgia (54°00'S, 38°03'W) (Figure 1). Since the 1970s, intensive study colonies of grey-headed albatrosses have been visited daily to weekly throughout the breeding season to record the identities of breeders and non-breeders, laying and fledging dates, and nest survival [START_REF] Pardo | Additive effects of climate and fisheries drive ongoing declines in multiple albatross species[END_REF]. Chicks have been ringed annually and the modal age of first breeding is 12 years [START_REF] Prince | Population dynamics of black-browed and grey-headed albatrosses Diomedea melanophris and D. chrysostoma at Bird Island, South Georgia[END_REF]. Birds were sexed from records of observed copulatory position, egg-laying attendance pattern or using DNA extracted from blood samples [START_REF] Fridolfsson | A simple and universal method for molecular sexing of non-ratite birds[END_REF]. All birds bred in the sampling year. A random collection of relatively unabraded body feathers were obtained from the breast region of adults (n = 78) of known breeding history in December and January in the 2013/2014 breeding season. Grey-headed albatrosses are not in active body feather moult at Bird Island between October and February [START_REF] Prince | Moult in black-browed and grey-headed albatrosses Diomedea melanophris and D. chrysostoma[END_REF]; hence, THg concentrations and stable isotope ratios (see below) of body feathers sampled during the breeding season should reflect Hg burdens, foraging areas and trophic levels when grown in the preceding non-breeding period. Previous studies of Hg in grey-headed albatrosses at South Georgia (reflecting THg concentrations in 1989, 1998 and 2001)were of feathers collected in a similar manner.

(b) Total mercury analysis

Hg in feathers is essentially inert and cannot be reincorporated into body tissues [START_REF] Appelquist | Mercury monitoring: mercury stability in bird feathers[END_REF]. Feathers were cleaned of surface lipids and contaminants using chloroform : methanol solution (2 : 1v/v) followed by successive Milli-Q® water rinses. Feathers were air-dried and cut into small fragments with stainless steel scissors. For each individual, three feathers were analysed separately and whole feathers were analysed excluding only the rachis. Feather THg concentrations were measured using an Advanced Mercury Analyser spectrophotometer (Altec AMA 254) at the laboratory Littoral Environnement et Sociétés (LIENSs, France). For each individual feather, a minimum of two aliquots (range: 0.40-1.50 mg dry weight [dw]) were analysed, and the means and relative standard deviation between measurements were calculated (all samples RSD <10%). THg concentrations are presented in μg g -1 dw.

Accuracywas tested using a certified reference material (dogfish liver DOLT-5, NRC, Canada; certified Hg concentration: 0.44 ± 0.18 μg g -1 dw) every 10 samples. The measured values were 0.46 ± 0.02 μg g -1 dw (n = 21), and thus, the recovery rate was 105 ± 5%. Blanks were analysed at the beginning of each set of samples and the detection limit of the method was 0.005 μg g -1 dw.

(c) Stable isotope analysis

Stable isotope ratios of carbon ( 13 C/ 12 C, expressed as δ 13 C) and nitrogen ( 15 N/ 14 N, δ 15 N) were measured on the same individual feathers as THg concentrations. Feather stable isotope ratios reflect those of prey during the period of their synthesis, and because they are metabolically inert once grownthey preserve an isotopic record of diet at the time of formation [START_REF] Bearhop | Factors that influence assimilation rates and fractionation of nitrogen and carbon stable isotopes in avian blood and feathers[END_REF][START_REF] Hobson | Assessing avian diets using stable isotopes I: turnover of 13 C in tissues[END_REF]. For stable isotope analyses, cleaned and cut feathers were packed into tin capsules (aliquots: 0.70 ± 0.01 mg [mean ± s.e.]). Stable isotope analyses were conducted at the Natural Environment Research Council (NERC) Life Sciences Mass Spectrometry Facility in East Kilbride. Stable isotope ratios of carbon and nitrogen were determined by a continuous-flow mass spectrometer (Thermo Scientific [Bremen, Germany] Delta Plus XP) coupled with an elemental analyser (Elementar [Langenselbold, Germany] vario PYRO cube). To correct for instrument drift, three internal laboratory standards were analysed for every 10 samples. Stable isotope ratios are reported as δ-values and expressed as ‰ according to the equation:

δX=[(Rsample/Rstandard) -1] × 10 3
where X is 13 C or 15 N, R is the corresponding ratio 13 C/ 12 C or 15 N/ 14 N and Rstandard is the ratio of international references Vienna PeeDee Belemnite for carbon and atmospheric N2 (air) for nitrogen. Measurement precision (standard deviation associated with replicate runs of USGS40) was ±0.1 ‰ for δ 13 C and ±0.2 ‰ for δ 15 N.

(d) Data analysis

Analyseswere conducted using R v. 3.4.4 [START_REF] Core | R: A Language and Environment for Statistical Computing[END_REF]. One-way ANOVAs and post hoc Tukey's HSD tests were used to test for differences among reported THg concentrations (based on three feathers pooled) from previous studies of grey-headed albatrosses at South Georgia.

Generalized linear mixed-effects models (GLMMs; gamma distribution and identity link function) were used to assess variation in feather THg concentrations using the 'lme4' package in R [START_REF] Bates | lme4: Linear mixed-effects models using Eigen and S4[END_REF]. Predictor variables were trophic level (δ15N), foraging habitat (δ 13 C), sex (males, n = 48; females, n = 30), age (range: 12-36 years) and previous breeding outcome. Although grey-headed albatrosses are predominantly biennial breeders, with a non-breeding period lasting approximately 16 months, a minority attempt to breed annually [START_REF] Ryan | Breeding frequency in grey-headed albatrosses Thalassarche chrysostoma[END_REF]. Individuals were therefore grouped according to their breeding outcomes (successful, failed or deferred) in the 2 years prior to sampling. Individual identity was included as a random effect to account for repeated measurements. Feather δ 15 N and δ 13 C values were included in the same models as therewas no evidence of collinearity (all variance inflation factors greater than 2). All possible models were ranked using the Akaike Information Criteria adjusted for small sample sizes (AICC), and models within two AICC units of the top model (≤2 AICC) were considered equally plausible [START_REF] Burnham | Model selection and multimodel inference: a practical information-theoretic approach[END_REF]. AICC weights (ωi) were used to assess the weight of evidence in favour of a given model among the candidate set [START_REF] Burnham | Model selection and multimodel inference: a practical information-theoretic approach[END_REF]. Predictor variables were standardized (i.e.

subtract by mean and divide by standard deviation) to facilitate model fitting. In a second step, one-way ANOVAs with post hoc Tukey's HSD tests were to identify significant differences in feather THg concentrations among foraging zones. Feathers were assigned to foraging zones based on their δ 13 C values-those corresponding to foraging in the Antarctic Zone (south of the APF; less than -21.2 ‰), SAZ (north of the APF and south of the STF; -21.2 ‰ to -18.3 ‰) and the Subtropical Zone (north of the STF; greater than -18.3 ‰) [START_REF] Jaeger | Seabird satellite tracking validates the use of latitudinal isoscapes to depict predators' foraging areas in the Southern Ocean[END_REF].

Spearman's rank correlations were used to test for relationships between feather THg concentrations and arrival date (Julian days) of grey-headed albatrosses at South Georgia.

Binomial generalized linear models (GLMs; binomial distribution and logit link function)were used to test for a relationship between feather THg concentrations and the subsequent breeding outcome (failed, n = 55; successful, n = 23). Predictor variables retained in the previous models were included as covariates, and males and females were analysed separately. Grey-headed albatrosses lay a single egg clutch with no replacement, and both parents incubate the egg.

Significance was assumed at α = 0.05 in all analyses.

Results

(a) Temporal trends and spatial variation

THg concentrations were measured in 229 body feathers from 78 individual grey-headed albatrosses sampled in 2013/2014. Average THg concentrations of body feathers were 13.04 ± 8.03 μg g -1 dw (range: 2.06-35.14 μg g -1 dw), and all measurements were greater than 2 μg g -1 dw. A total of 190 (83%) feathers had THg concentrations greater than 5 μg g -1 dw. Feather THg concentrations measured in greyheaded albatrosses in previous studies at South Georgia, and other island groups are presented in table 1. Average feather THg concentrations for the South Georgia population in 2013 were higher than previously recorded at Campbell Island, Marion Island (Prince Edward Islands) and South Georgia. Average feather THg concentrations differed between the four previous studies at South Georgia (one-way ANOVA, F3,143 = 23.6, p < 0.001), and post hoc Tukey's HSD tests (all p < 0.05) confirmed that feather THg concentrations in 2013 were higher than in 1989, 1998 and 2001 (Figure 2).

(b) Variation in feather total mercury concentrations

The most parsimonious GLMMexplaining variation in feather THgconcentrations included the effects of δ 15 N (estimate ± s.e., 3.37 ± 0.36, p < 0.0001) and δ 13 C (-1.34 ± 0.35, p < 0.001) (Table 2), reflecting positive relationships with trophic level and latitude (Figures 3 and4). A similar model that also contained sex as a non-significant fixed effect (0.75 ± 1.63, p = 0.64) had less than 2 ΔAICC; however, this model had a greatly reduced ωi. Models including other predictor variables (age and breeding history) received less support (all greater than 2 ΔAICC).

Feather THg concentrations were significantly different between moulting zones (one-way ANOVA, F2,226 = 22.41, p < 0.001). Post hoc Tukey's HSD tests indicated that feathers associated with moulting in the AZ (mean ± s.d., 4.12 ± 1.20 μg g -1 dw, n = 27) had lower THg concentrations than those associated with the SAZ (14.33 ± 7.88 μg g -1 dw, n = 184) or the STZ (13.27 ± 7.13 μg g -1 dw, n = 18); means for these last two groupswere not significantly different (Figure 4).

(c) Relationships between total mercury concentrations and subsequent breeding outcome

No significant relationships were found between feather THg concentrations and arrival dates of males (rS = 0.07, p = 0.40) or females (rS = -0.01, p = 0.92). Average THg concentrations were significantly higher in body feathers of males that failed to fledge a chick in the sampling year (14.96 ± 9.05 µg g -1 dw) compared to those that were successful (11.53 ± 6.66 µg g -1 dw) (binomial GLM: χ 2 = 11.30, p < 0.001) (Figure 5), but were similar among females that failed (11.81 ± 7.56 µg g -1 dw) or were successful in fledging their chick (11.99 ± 6.04 µg g -1 dw) (χ 2 = 0.31, p = 0.58).

Discussion

Feather analyses offer a non-lethal method to obtain information about Hg exposure during the non-breeding period, and measuring THg in albatross feathers provides information about contamination of prey and hence exposure to MeHg in the food web [START_REF] Thompson | Comparison of the levels of total and organic mercury in seabird feathers[END_REF][START_REF] Renedo | Assessment of mercury speciation in feathers using species-specific isotope dilution analysis[END_REF][START_REF] Albert | Using blood and feathers to investigate large-scale Hg contamination in Arctic seabirds: a review[END_REF]. This study provides a detailed analysis of the underlying drivers and consequences of high feather THg concentrations in the endangered grey-headed albatross at South Georgia. Results from the present work also provide new insights into long-term changes in Hg exposure of this species and differences in exposure among breeding populations throughout the Southern Ocean.

(a) Temporal trends in mercury exposure (1989-2014)

By comparison with previous ecotoxicological studies at South Georgia [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Becker | Feather mercury levels in seabirds at South Georgia: influence of trophic position, sex and age[END_REF][START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF], the present study found a striking threefold increase in mean body feather THg concentrations of grey-headed albatrosses since the late-1980s. A similar increase has been found in other marine predators foraging in subantarctic waters. For instance, in the southern Indian Ocean, macaroni penguins (Eudyptes chrysolophus) and gentoo penguins (Pygoscelis papua) had higher feather THg concentrations in 2007 compared with the 1970s [START_REF] Carravieri | Penguins as bioindicators of mercury contamination in the southern Indian Ocean: geographical and temporal trends[END_REF], and feather THg concentrations from black-browed albatross (Thalassarche melanophris) at the Falkland Islands have increased since 1986 [START_REF] Furtado | Body feather mercury and arsenic concentrations in five species of seabirds from the Falkland Islands[END_REF]. Moreover, at Gough Island, Atlantic petrels (Pterodroma incerta), soft-plumaged petrels (Pterodroma mollis) and sooty albatrosses (Phoebetria fusca) all had higher feather THg concentrations in 2009/2010 compared with the mid-1980s [START_REF] Becker | Feather mercury concentrations in Southern Ocean seabirds: variation by species, site and time[END_REF]. Similar trends are not observed in lower trophic level organisms (cephalopod and myctophid species) at South Georgia [START_REF] Seco | Mercury levels in Southern Ocean squid: Variability over the last decade[END_REF][START_REF] Seco | Main drivers of mercury levels in Southern Ocean lantern fish Myctophidae[END_REF]; however, these samples were collected far to the south of the subantarctic and subtropical waters used by the majority of grey-headed albatrosses.

There are two plausible explanations for the temporal trend observed in our study. Firstly, greyheaded albatrosses may have shifted their diets or foraging habitats to more contaminated prey or regions. Analyses of stomach contents of chicks have revealed a major dietary shift in breeding grey-headed albatrosses at South Georgia since the mid-1990s, including a reduction in the occurrence of the seven-star flying squid (Martialia hyadesi) and an increase in mackerel icefish (Champsocephalus gunnari) [START_REF] Mills | Long-term trends in albatross diets in relation to prey availability and breeding success[END_REF]. However, adults may not consume the same prey that they provision to chicks and, given the difficulties in obtaining samples, the only conventional diet information for grey-headed albatrosses outside of the breeding period is for the cephalopod component [START_REF] Alvito | Cephalopods in the diet of nonbreeding black-browed and greyheaded albatrosses from South Georgia[END_REF]. Regardless, differences in stable isotope ratios of grey-headed albatross feathers from 2001 (δ 15 N, 10.48 ± 0.89 ‰; δ 13 C, -19.17 ± 1.12 ‰) contrast with the values of 12.71 ± 1.33 ‰ and -20.09 ± 1.30 ‰ in our study and provide support for the dietary shift hypothesis [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF]. Moreover, the increased variance in stable isotope ratios corresponds with the higher standard deviations of THg concentrations in our study. Secondly, exposure of MeHg to grey-headed albatrosses at South Georgia may have increased. Much of the Hg that enters marine food webs originates from low-oxygen subsurface waters [START_REF] Blum | Methylmercury production below the mixed layer in the North Pacific Ocean[END_REF][START_REF] Cossa | Mercury in the Southern Ocean[END_REF]. In a warming world, oxygen minimum zones are expected to increase, hence potentially enhancing methylation of Hg and its bioavailability to marine predators. Moreover, artisanal and smallscale gold mining, a major source of Hg contamination that is prevalent in South America, is increasing [START_REF]Global Mercury Assessment 2018[END_REF]. Rivers may deliver large amounts of Hg into the oceans [START_REF] Fisher | Riverine source of Arctic Ocean mercury inferred from atmospheric observations[END_REF]. Potentially, Hg in rivers flowing onto the Patagonian Shelf may be carried south in the Brazil Current and, at the confluence with the Falklands Current, be transported east in the South Atlantic Current to grey-headed albatross foraging areas [START_REF] Phillips | Sexual segregation in distribution, diet and trophic level of seabirds: Insights from stable isotope analysis[END_REF][START_REF] Clay | Proximate drivers of spatial segregation in non-breeding albatrosses[END_REF][START_REF] Mills | Stable isotopes demonstrate intraspecific variation in habitat use and trophic level of non-breeding albatrosses[END_REF]. Both hypotheses require further investigation, including via direct measurements of Hg in water samples or prey of grey-headed albatrosses.

(b) Comparisons with other populations and albatross species

Average body feather THg concentrations in grey-headed albatrosses from South Georgia, sampled in 2013/2014, were higher than those reported for this species at either Campbell or Marion Island [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF][START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF]. Non-breeding birds from these sites are oceanic foragers that predominantly target subantarctic waters [START_REF] Cherel | A comprehensive isotopic investigation of habitat preferences in nonbreeding albatrosses from the Southern Ocean[END_REF]; however, there is considerable spatial segregation between the two populations that have been tracked during the non-breeding period-birds from Marion avoid core regions in the southwest Atlantic used by birds from South Georgia [START_REF] Clay | Proximate drivers of spatial segregation in non-breeding albatrosses[END_REF]. Birds from other Indian Ocean populations are likely to do the same.

Accordingly, birds from all populations may use broadly the same habitat type, but our results indicate that the South Georgia population is exposed to higher Hg levels in the southwest Atlantic, potentially for the reasons mentioned above. To the best of our knowledge, there are no published data on Hg contamination for the grey-headed albatross populations at Crozet, Kerguelen, Macquarie or the island groups off southern Chile. Phylogeny is a significant driver of Hg contamination in albatrosses, such that species in the genus Thalassarche tend to have lower concentrations than Phoebetria or Diomedea [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF]. However, the mean feather THg concentrations in grey-headed albatrosses reported here are higher than in light-mantled albatross (Phoebetria palpebrata) at any site, and even the southern royal albatross (Diomedea epomophora) and northern royal albatross (D. sanfordi); indeed, they are the highest recorded for any member of the Thalassarche genus [18; and references therein].

(c) Factors underlying feather total mercury concentrations

Foraging habitat, inferred from δ 13 C values, was an important driver of body feather THg concentrations. The Southern Ocean shows a latitudinal decrease in δ 13 C from subtropical to Antarctic waters, which is reflected in the tissues of albatrosses [START_REF] Jaeger | Seabird satellite tracking validates the use of latitudinal isoscapes to depict predators' foraging areas in the Southern Ocean[END_REF][START_REF] Cherel | Geographical variation in carbon stable isotope signatures of marine predators: a tool to investigate their foraging areas in the Southern Ocean[END_REF][START_REF] Quillfeldt | Moving polewards in winter: a recent change in the migratory strategy of a pelagic seabird?[END_REF], and body feather THg concentrations in albatrosses appear to reflect MeHg intake during growth [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF]. The threshold δ 13 C values thatwe used to assign moulting location to north or south of the APF and STF were derived from tracked wandering albatrosses in the Indian Ocean [START_REF] Jaeger | Seabird satellite tracking validates the use of latitudinal isoscapes to depict predators' foraging areas in the Southern Ocean[END_REF]. However, the paths of oceanographic fronts can be highly variable between years [START_REF] Moore | Variability in the location of the Antarctic Polar Front (90 o -20 o W) from satellite sea surface temperature data[END_REF], and stable isotope values are therefore broadly indicative of water masses rather than latitude per se. Allowing for some uncertainty, our results are nevertheless indicative of lower THg concentrations in feathers of grey-headed albatrosses grown in Antarctic compared with subantarctic and subtropical waters. A near identical pattern was found in the light-mantled albatross from the Kerguelen Islands, sooty albatross from Gough Island and grey-headed albatross at Marion Island [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF]. Moreover, a similar latitudinal pattern in Hg exposure has been found in a number of Southern Hemisphere seabird species, of varying trophic levels, includingwandering albatross at the Crozet archipelago [START_REF] Bustamante | High feather mercury concentrations in the wandering albatross are related to sex, breeding status and trophic ecology with no demographic consequences[END_REF][START_REF] Carravieri | Wandering albatrosses document latitudinal variations in the transfer of persistent organic pollutants and mercury to southern ocean predators[END_REF], as well as chicks of skuas (Stercorarius spp.) and multiple penguin species from the southern Indian Ocean [START_REF] Carravieri | Penguins as bioindicators of mercury contamination in the southern Indian Ocean: geographical and temporal trends[END_REF][START_REF] Carravieri | From Antarctica to the subtropics: contrasted geographical concentrations of selenium, mercury, and persistent organic pollutants in skua chicks (Catharacta spp.)[END_REF]. Community-level studies have also documented the same trend with latitude [START_REF] Anderson | Influence of trophic position and foraging range on mercury levels within a seabird community[END_REF][START_REF] Blévin | Wide range of mercury contamination in chicks of Southern Ocean seabirds[END_REF][START_REF] Carravieri | Trace elements and persistent organic pollutants in chicks of 13 seabird species from Antarctica to the subtropics[END_REF]. A recent review including all 20 albatross taxa breeding in the Southern Ocean found foraging habitat (δ 13 C) to be an important driver of feather THg concentrations, with a similar step increase north of the APF as in our study [START_REF] Cherel | Accumulate or eliminate? Seasonal mercury dynamics in albatrosses, the most contaminated family of birds[END_REF]. The majority ofMeHg accumulated by seabirds is of mesopelagic origin, and recent work suggests that more efficient Hg methylation at depth, combined with higher vertical mixing, in subtropical compared with higher latitude waters could bring newly formed MeHg to the surface and hence increase bioavailability to seabirds [START_REF] Renedo | A"seabirdeye"on mercury stable isotopes and cycling in the Southern Ocean[END_REF].

In our analyses, feather THg concentrations were also positively related to δ 15 N values, which provide a proxy for trophic level. This is reflective of the biomagnification of MeHg in food webs. The relationship between δ 15 N and Hg exposure is often apparent when comparing mean values for different species within seabird communities [START_REF] Carravieri | Penguins as bioindicators of mercury contamination in the Southern Ocean: birds from the Kerguelen Islands as a case study[END_REF][START_REF] Blévin | Wide range of mercury contamination in chicks of Southern Ocean seabirds[END_REF], but is less frequently observed within a single species [START_REF] Bearhop | Bioamplification of mercury in great skua Catharacta skua chicks: the influence of trophic status as determined by stable isotope signatures of blood and feathers[END_REF]. That it was apparent in our study population is probably because grey-headed albatrosses at South Georgia consume a wide range of prey from multiple trophic levels [START_REF] Mills | Long-term trends in albatross diets in relation to prey availability and breeding success[END_REF], and the variation in δ 15 N values among individuals was very high (range: 8.8-15.

‰).

A model also containing sex received less support in explaining feather THg concentrations; however, males exhibited higher feather concentrations than females. Male grey-headed albatrosses at South Georgia are heavier, with larger wing areas and higher wing loadings than females [START_REF] Phillips | Seasonal sexual segregation in two Thalassarche albatross species: competitive exclusion, reproductive role specialization or foraging niche divergence?[END_REF]. During the non-breeding period, males forage at slightly higher trophic levels and at higher latitudes compared with females [START_REF] Mills | Stable isotopes demonstrate intraspecific variation in habitat use and trophic level of non-breeding albatrosses[END_REF], and tracking data show that core areas but not overall distributions were segregated to some extent during the non-breeding summer only [START_REF] Clay | Proximate drivers of spatial segregation in non-breeding albatrosses[END_REF][START_REF] Croxall | Global circumnavigations: tracking year-round ranges of nonbreeding albatrosses[END_REF]. No effects of age were found in the present study, which is in agreement with results from other albatross species [START_REF] Bustamante | High feather mercury concentrations in the wandering albatross are related to sex, breeding status and trophic ecology with no demographic consequences[END_REF][START_REF] Carravieri | Wandering albatrosses document latitudinal variations in the transfer of persistent organic pollutants and mercury to southern ocean predators[END_REF][START_REF] Tavares | Influence of age, sex and breeding status on mercury accumulation patterns in the wandering albatross Diomedea exulans[END_REF][START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF], and previous studies of grey-headed albatrosses with much smaller sample sizes [START_REF] Becker | Feather mercury levels in seabirds at South Georgia: influence of trophic position, sex and age[END_REF][START_REF] Thompson | Temporal and spatial variation in mercury concentrations in some albatrosses and petrels from the sub-Antarctic[END_REF]. However, it should be noted that our study was crosssectional, and it is unknown whether Hg exposure affects adult survival in grey-headed albatrosses. Hence, selective mortality of particular phenotypes cannot be excluded except by conducting a longitudinal study [START_REF] Froy | Contrasting drivers of reproductive ageing in albatrosses[END_REF]. Stable isotope ratios of adult seabird feathers provide information about foraging ecology in the non-breeding period [START_REF] Mills | Stable isotopes demonstrate intraspecific variation in habitat use and trophic level of non-breeding albatrosses[END_REF][START_REF] Cherel | A comprehensive isotopic investigation of habitat preferences in nonbreeding albatrosses from the Southern Ocean[END_REF]. However, owing to different integration periods, it has been suggested that relationships between stable isotopes and THg concentrations may be spurious [START_REF] Bond | Relationships between stable isotopes and metal contaminants in feathers are spurious and biologically uninformative[END_REF]; nonetheless, in albatrosses, both stable isotope ratios and THg concentrations appear to reflect diet during feather synthesis [18; and references therein].

(d) Fitness correlates of Hg exposure

Albatrosses are likely better adapted than other birds to Hg exposure and may tolerate higher concentrations; regardless, albatrosses are k-selected species and should prioritize adult survival over the immediate reproductive event. In our study, Hg exposure was clearly not sufficient to cause direct morality, or to prompt birds to defer breeding. At South Georgia, most reproductive failures occur during incubation, and consistently successful grey-headed albatrosses arrive earlier at the colony, have shorter incubation shifts and hatch larger chicks with higher growth rates compared with less successful birds [START_REF] Prince | Population dynamics of black-browed and grey-headed albatrosses Diomedea melanophris and D. chrysostoma at Bird Island, South Georgia[END_REF][START_REF] Cobley | Individual quality and reproductive performance in the Grey-headed Albatross Diomedea chrysostoma[END_REF]. No significant relationships between Hg exposure and arrival date were found; however, feather THg concentrations of male grey-headed albatrosses that failed in their breeding attempt were significantly higher than in those that successfully fledged a chick. Ackerman et al. [START_REF] Ackerman | Avian mercury exposure and toxicological risk across western North America: a synthesis[END_REF] converted published Hg toxicity benchmarks in birds into blood-equivalent THg concentrations and documented negative effects with those as low as 0.2 μg g -1 wet weight (ww) [START_REF] Ackerman | Avian mercury exposure and toxicological risk across western North America: a synthesis[END_REF]. Average feather THg concentrations of failed male birds in our study were equivalent to a blood THg equivalent of 1.15 μg g -1 ww. Generally, health, physiology, behaviour and reproduction tend to be impacted at blood-equivalent THg concentrations of approximately 1.0 μg g -1 ww and more substantial impairments to health and reproduction at approximately 2.0 μg g -1 ww [START_REF] Ackerman | Avian mercury exposure and toxicological risk across western North America: a synthesis[END_REF].

Male snow petrels (Pagodroma nivea) with higher Hg burdens are more likely to neglect eggs, and male black-legged kittiwakes (Rissa tridactyla) show reduced breeding success and are more likely to skip breeding (with ≤0.4 μg g -1 ww blood THg equivalent in both cases) [START_REF] Tartu | To breed or not to breed: Endocrine response to mercury contamination by an Arctic seabird[END_REF][START_REF] Tartu | Corticosterone, prolactin and egg neglect behavior in relation to mercury and legacy POPs in a long-lived Antarctic bird[END_REF][START_REF] Ackerman | Avian mercury exposure and toxicological risk across western North America: a synthesis[END_REF][START_REF] Tartu | Mercury exposure, stress and prolactin secretion in an Arctic seabird: an experimental study[END_REF]. Hg exposure weakened immune function in black-footed albatrosses (Phoebastria nigripes) [START_REF] Finkelstein | Contaminant-associated alteration of immune function in black-footed albatross (Phoebastria nigripes), a North Pacific predator[END_REF], though the blood-equivalent THg concentrations were far higher than birds in our study. Although there was no evidence of fitness consequences of high feather Hg contamination in a previous study of wandering albatrosses at the Crozet archipelago [START_REF] Bustamante | High feather mercury concentrations in the wandering albatross are related to sex, breeding status and trophic ecology with no demographic consequences[END_REF], high blood THg concentrations in the same population negatively impacted long-term breeding probability, hatching and fledging probabilities [START_REF] Goutte | Demographic consequences of heavy metals and persistent organic pollutants in a vulnerable long-lived bird, the wandering albatross[END_REF]. Grey-headed albatrosses are declining more steeply at South Georgia than at any other island group where there is a major population (approx. 50%); numbers are increasing at Diego Ramirez and Crozet, broadly stable at the Prince Edward Islands and declining slowly at Kerguelen [START_REF] Ryan | Recent population estimates and trends in numbers of albatrosses and giant petrels breeding at the sub-Antarctic Prince Edward islands[END_REF][START_REF] Robertson | Continued increase in the number of black-browed albatrosses (Thalassarche melanophris) at Diego Ramírez, Chile[END_REF][START_REF] Weimerskirch | Status and trends of albatrosses in the French southern territories, western Indian ocean[END_REF]. However, the differing population trends could relate to factors other than Hg burdens, particularly the relative overlap with different fishing fleets and hence bycatch rates, which vary greatly.At South Georgia, breeding success is low, highly variable and has contributed to the negative population trends over the last 35 years [START_REF] Pardo | Additive effects of climate and fisheries drive ongoing declines in multiple albatross species[END_REF]. Our results suggest that Hg exposure may be a contributing factor. Future work should examine birds observed as non-breeders at the colony, and also examine the risks posed by other pollutants, particularly given the increase in recovery rates per capita of marine debris (predominantly plastics) associated with albatrosses at South Georgia since the mid-1990s, and their potential role in contaminant transmission [START_REF] Phillips | Albatrosses and petrels at South Georgia as sentinels of marine debris input from vessels in the southwest Atlantic Ocean[END_REF]. Table 1. Results from previous studies measuring total mercury (THg) concentrations (µg g -1 dw) in body feathers of grey-headed albatrosses (Thalassarche chrysostoma). Values presented are means ± standard deviation (range). Sampling procedure refers to whether THg concentrations were measured separately in multiple feathers (individual) or if multiple feathers were pooled before analysis (pooled).

Ethics

Breeding site location

Sampling year n Sampling procedure Feather THg (µg g -1 dw)

.

  All sampling was approved by the British Antarctic Survey Ethics Committee and carried out with permission of the Government of South Georgia and the South Sandwich Islands. Data accessibility. Raw data are available as electronic supplementary material. Competing interests. The data supporting this paper are available from the Dryad Digital Repository: https://dx.doi.org/10.5061/dryad.vdncjsxsq [77]. Authors' contributions. W.F.M, P.B and R.A.P conceived the experimental design. R.A.P was responsible for sample collection. W.F.M, R.A.R.M and P.B conducted the laboratory analyses. W.F.M analysed the data and drafted the manuscript. All authors contributed to the writing of the manuscript, gave final approval for publication and agree to be held accountable for the work performed therein. Funding. W.F.M is supported by a NERC GW4+ Doctoral Training Partnership studentship from the Natural Environment Research Council (NE/L002434/1). Stable isotope analyses were funded by the NERC Life Sciences Mass Spectrometry Facility (grant number EK311-12/18). The Institut Universitaire de France (IUF) is acknowledged for its support to P.B as a Senior Member.

Figure 1 .

 1 Figure 1. Location of Bird Island, South Georgia (cross), in relation to the Antarctic Polar Front (dashed line) and Subtropical Front (dot-dash line).

Figure 2 .

 2 Figure 2. Temporal increase in mean (± standard deviation) total Hg concentrations (µg g -1 dw) of body feathers of grey-headed albatrosses (Thalassarche chrysostoma) from Bird Island, South Georgia. Data are based on multiple body feathers pooled per individual.

Figure 3 .

 3 Figure 3. Total Hg concentrations (µg g -1 dw) in body feathers of grey-headed albatrosses (Thalassarche chrysostoma) from Bird Island, South Georgia sampled in 2013/14, in relation to: (A) feather δ 13 C values, and (B) feather δ 15 N values. Vertical dashed lines are δ 13 C estimates associated with foraging at the Antarctic Polar Front (-21.2 ‰) and Subtropical Front (-18.3 ‰) [51]. Body feathers with δ 13 C values associated with foraging south of the Antarctic Polar Front are coloured grey.

Figure 4 .

 4 Figure 4. Mean (± standard deviation) body feather total Hg concentrations (µg g -1 dw) of grey-headed albatrosses (Thalassarche chrysostoma) from Bird Island, South Georgia, sampled in 2013/14, in relation to moulting zones. The Antarctic Zone (AZ; south of the Antarctic Polar Front), Subantarctic Zone (SAZ; between the Antarctic Polar Front and Subtropical Front) and Subtropical Zone (STZ; north of the Subtropical Front) are separated by δ 13 C estimates of the Antarctic Polar Front (-21.2‰) and Sub-Tropical Front (-18.3‰) [51].

Figure 5 .

 5 Figure 5. Total Hg concentrations (µg g -1 dw) in body feathers of grey-headed albatrosses (Thalassarche chrysostoma) that failed to fledge a chick ("Failed"), or successfully fledged a chick ("Successful") at Bird Island, South Georgia in the 2013/14 breeding season. Males (A) and females (B) were analysed separately. Values are means and standard deviations.

Acknowledgements

. The authors are grateful to the many fieldworkers at Bird Island who carried out the routine monitoring and collected albatross feathers, to Maud Brault-Favrou and Carine Churlaud for their assistance with Hg analyses and to Danielle Buss for her statistical advice. Constructive comments from two anonymous reviewers substantially improved this work. Thanks are also due to the CPER (Contrat de Projet Etat-Région) and the FEDER (Fonds Européen de Développement Régional) for funding the AMA of LIENSs laboratory. This work represents a contribution to the Ecosystems component of the British Antarctic Survey Polar Science for Planet Earth Programme, funded by the Natural Environment Research Council.


Hiroto Yasumi
email: yasumi.hiroto.yf9@is.naist.jp

Fukuhito Ooshita
email: f-oosita@is.naist.jp

Michiko Inoue

Sébastien Tixeuil
email: sebastien.tixeuil@lip6.fr

Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs

Keywords: 2012 ACM Subject Classification Theory of computation → Distributed algorithms; Theory of computation → Concurrent algorithms population protocol, uniform bipartition, distributed protocol Digital Object Identifier 10.4230/LIPIcs.OPODIS.2020.33

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of arbitrary communication graphs. As a result, we investigate the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

Introduction

Background

In this paper, we consider the population protocol model introduced by Angluin et al. [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF].

The population protocol model is an abstract model for low-performance devices. In the population protocol model, devices are represented as anonymous agents, and a population is represented as a set of agents. Those agents move passively (i.e., they cannot control their movements), and when two agents approach, they are able to communicate and update their states (this pairwise communication is called an interaction). A computation then consists of an infinite sequence of interactions.

Related Works

The population protocol model was proposed by Angluin et al. [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], who were recently awarded the 2020 Edsger W. Dijkstra prize in Distributed Computing for their work. While the core of the initial study was dedicated to the computability of the model, subsequent works considered various problems (e.g., leader election, counting, majority, uniform k-partition) under different assumptions (e.g., existence of a base station, fairness, symmetry of protocols, and initial states of agents).

The leader election problem was studied from the perspective of time and space efficiency. Doty and Soloveichik [20] proved that Ω(n) expected parallel time is required to solve leader election with probability 1 if agents have a constant number of states. Relaxing the number of states to a polylogarithmic value, Alistarh and Gelashvili [START_REF] Alistarh | Polylogarithmic-time leader election in population protocols[END_REF] proposed a leader election protocol in polylogarithmic expected stabilization time. Then, Gąsieniec et al. [23] designed (a protocol is self-stabilizing if its correctness does not depend on its initial global state). This impossibility can be avoided if oracles are available [9,18] or if the self-stabilization requirement is relaxed: Sudo et al. [30] proposed a loosely stabilizing protocol for leader election (loose stabilization relates to the fact that correctness is only guaranteed for a very long expected amount of time).

The counting problem was introduced by Beauquier et al. [11] and popularized the concept of a base station. Space complexity was further reduced by follow-up works [10, 24], until Aspnes et al. [8] finally proposed a time and space optimal protocol. On the other hand, by allowing the initialization of agents, the counting protocols without the base station were proposed for both exact counting [16] and approximate counting [START_REF] Alistarh | Timespace trade-offs in population protocols[END_REF]16]. In [START_REF] Alistarh | Timespace trade-offs in population protocols[END_REF], Alistarh et al. proposed a protocol that computes an integer k such that 1 2 log n < k < 9 log n in O(log n) time with high probability using O(log n) states. After that, Berenbrink et al. [16] designed a protocol that outputs either log n or log n in O(log 2 n) time with high probability using O(log n • log log n) states. Moreover, in [16], they proposed the exact counting protocol that computes n in O(log n) time using Õ(n) states with high probability.

The majority problem was addressed under different assumptions (e.g., with or without failures [6], deterministic [22,25] or probabilistic [START_REF] Alistarh | Space-optimal majority in population protocols[END_REF]12,13, 25] solutions, with arbitrary communication graphs [27], etc.). Those works also consider minimizing the time and space complexity. Berenbrink et al. [14] show trade-offs between time and space for the problem.

To our knowledge, the uniform k-partition problem and its variants have only been considered in complete communication graphs. Lamani et al. [26] studied a group decomposition problem that aims to divide a population into groups of designated sizes. Yasumi et al. [32] proposed a uniform k-partition protocol with no base station. Umino et al. [31] extended the result to the R-generalized partition problem that aims at dividing a population into k groups whose sizes follow a given ratio R. Also, Delporte-Gallet et al. [19] proposed a k-partition protocol with relaxed uniformity constraints: the population is divided into k groups such that in any group, at least n/(2k) agents exist, where n is the number of agents.

Most related to our work is the uniform bipartition solution for complete communication graphs provided by Yasumi et al. [33,35]. For the uniform bipartition problem over complete graphs with designated initial states, Yasumi et al. [33,35] various assumptions such as: (i) an initialized base station, a non-initialized base station, or no base station (an initialized base station has a designated initial state, while a noninitialized has an arbitrary initial state), (ii) asymmetric or symmetric protocols (asymmetric protocols allow interactions between two agents with the same state to map to two resulting different states, while symmetric protocols do not allow such a behavior), and (iii) global or weak fairness (weak fairness guarantees that every individual pairwise interaction occurs infinitely often, while global fairness guarantees that every recurrently reachable configuration is eventually reached). Furthermore, they also study the solvability of the uniform bipartition problem with arbitrary initial states. Table 1 shows the minimum number of states to solve the uniform bipartition with designated initial states over complete communication graphs.

There exist some protocol transformers that transform protocols for some assumptions into ones for other assumptions. In [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], Angluin et al. proposed a transformer that transforms a protocol with complete communication graphs into a protocol with arbitrary communication graphs. This transformer requires the quadruple state space and works under global fairness. In this transformer, agents exchange their states even after convergence. For the uniform bipartition problem, since agents must keep their groups after convergence, they cannot exchange their states among different groups and thus the transformer proposed in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] cannot directly apply to the uniform bipartition problem. Bournez et al. [17] proposed a transformer that transforms an asymmetric protocol into symmetric protocol by assuming additional states. In [17], only protocols with complete communication graphs were considered and the transformer works under global fairness. We use the same idea to construct a symmetric uniform bipartition protocol under global fairness without a base station.

Our Contributions

In this paper, we study the solvability of the uniform bipartition problem with designated initial states over arbitrary graphs. A summary of our results is presented in Table 2. Let us first observe that, as complete communication graphs are a special case of arbitrary communication graphs, the impossibility results by Yasumi et al. [35] remain valid in our setting. With a base station (be it initialized or non-initialized) under global fairness, we extend the three states protocol by Yasumi et al. [35] from complete communication graphs to arbitrary communication graphs. With a non-initialized base station under weak fairness, we propose a new symmetric protocol with 3P + 1 states, where P is a known upper bound of the number of agents. These results yield identical upper bounds for the easier cases of asymmetric protocols and/or initialized base station. In addition, we also show a condition of communication graphs in which the number of states in the protocol can be reduced from 3P + 1 to constant. Concretely, we show that the number of states in the protocol can be reduced to 3l + 1 if we assume communication graphs such that every cycle either includes the base station or its length is not a multiple of l, where l is a positive integer at least three. On the other hand, with no base station under global fairness, we prove that four and five states are necessary and sufficient to solve uniform bipartition with asymmetric and symmetric protocols, respectively. In the same setting, in complete graphs, three and four states were necessary and sufficient. So, one additional state enables problem solvability in arbitrary communications graphs in this setting. With no base station under weak fairness, we prove that the problem cannot be solved, using a similar argument as in the impossibility result for leader election by Fischer and Jiang [21]. Overall, we show the solvability of uniform bipartition in a variety of settings for a population of agents with designated initial states assuming arbitrary communication graphs. In cases where the problem remains feasible, we provide upper and lower bounds with respect to the number of states each agent maintains, and in all cases where global fairness can be assumed, our bounds are tight.

In this paper, because of space limitations, we omitted proofs of lemmas and theorems (see the full version [34]).

Definitions

Population Protocol Model

A population whose communication graph is arbitrary is represented by an undirected connected graph G = (V, E), where V is a set of agents, and E ⊆ V × V is a set of edges that represent the possibility of an interaction between two agents. That is, two agents u ∈ V and v ∈ V can interact only if (u, v) ∈ E holds. A protocol P = (Q, δ) consists of Q and δ, where Q is a set of possible states for agents, and δ is a set of transitions from

Q × Q to Q × Q.
Each transition in δ is denoted by (p, q) → (p , q ), which means that, when an interaction between an agent x in state p and an agent y in state q occurs, their states become p and q , respectively. Moreover, we say x is an initiator and y is a responder. When x and y interact as an initiator and a responder, respectively, we simply say that x interacts with y. Transition (p, q) → (p , q ) is null if both p = p and q = q hold. We omit null transitions in the descriptions of protocols. Protocol P = (Q, δ) is symmetric if, for every transition (p, q) → (p , q ) in δ, (q, p) → (q , p ) exists in δ. In particular, if a protocol P = (Q, δ) is symmetric and transition (p, p) → (p , q ) exists in δ, p = q holds. If a protocol is not symmetric, the protocol is asymmetric.

Protocol P = (Q, δ) is deterministic if, for any pair of states (p, q) ∈ Q × Q, exactly one transition (p, q) → (p , q ) exists in δ.
We consider only deterministic protocols in this paper. A global state of a population is called a configuration, defined as a vector of (local) states of all agents. A state of agent a in configuration C, is denoted by s(a, C). Moreover, when C is clear from the context, we simply use s(a) to denote the state of agent a. A transition between two configurations C and C is described as C → C , and means that configuration C is obtained from C by a single interaction between two agents. For two configurations C and C , if there exists a sequence of configurations In this paper, we consider three possibilities for the base station: initialized base station, non-initialized base station, and no base station. In the model with a base station, we assume that a single agent, called a base station, exists in V . Then, V can be partitioned into V b , the singleton set containing the base station, and V p , the set of agents except for the base station. The base station can be distinguished from other agents in V p , although agents in V p cannot be distinguished. Then, the state set Q can be partitioned into a state set Q b for the base station, and a state set Q p for agents in V p . The base station has unlimited resources (with respect to the number of states), in contrast with other resource-limited agents (that are allowed only a limited number of states). So, when we evaluate the space complexity of a protocol, we focus on the number of states |Q p | for agents in V p and do not consider the number of states |Q b | that are allocated to the base station. In the sequel, we thus say a protocol uses x states if |Q p | = x holds. When we assume an initialized base station, the base station has a designated initial state. When we assume a non-initialized base station, the base station has an arbitrary initial state (in Q b ), although agents in V p have the same designated initial state. When we assume no base station, there exists no base station and thus V = V p holds. For simplicity, we use agents only to refer to agents in V p in the following sections. To refer to the base station, we always use the term base station (not an agent). In the initial configuration, both the base station and the agents are not aware of the number of agents, yet they are given an upper bound P of the number of agents. However, in protocols except for a protocol in Section 3.2, we assume that they are not given P .

C = C 0 , C 1 , . . . , C m = C such that C i → C i+1 holds for every i (0 ≤ i < m),

Uniform Bipartition Problem

Let f : Q p → {red, blue} be a function that maps a state of an agent to red or blue. We define the color of an agent a as f (s(a)). Then, we say that agent a is red (resp., blue) if f (s(a)) = red (resp., f (s(a)) = blue) holds. If an agent a has state s such that f (s) = red (resp., f (s) = blue), we call a a red agent (resp., a blue agent). For some population V , the number of red agents (resp., blue agents) in V is denoted by #red(V ) (resp., #blue(V )). When V is clear from the context, we simply write #red and #blue.

A configuration C is stable with respect to the uniform bipartition if there exists a partition {H r , H b } of V p that satisfies the following conditions: An execution Ξ = C 0 , C 1 , C 2 , . . . solves the uniform bipartition problem if Ξ includes a configuration C t that is stable for uniform bipartition. Finally, a protocol P solves the uniform bipartition problem if every possible execution Ξ of protocol P solves the uniform bipartition problem.

3

Upper Bounds with a Non-initialized Base Station

In this section, we prove some upper bounds on the number of states that are required to solve the uniform bipartition problem over arbitrary graphs with designated initial states and a non-initialized base station. More concretely, with global fairness, we propose a symmetric protocol with three states by extending the protocol by Yasumi et al.

[35] from a complete communication graph to an arbitrary communication graph. In the case of weak fairness, we present a symmetric protocol with 3P + 1 states, where P is a known upper bound of the number of agents.

Upper Bound for Symmetric Protocols under Global Fairness

The state set of agents in this protocol is Q p = {initial, red, blue}, and we assume that f (initial) = f (red) = red and f (blue) = blue hold. The designated initial state of agents is initial. The idea of the protocol is as follows: the base station assigns red and blue to agents whose state is initial alternately. As the base station cannot meet every agent (the communication graph is arbitrary), the positions of state initial are moved throughout the communication graph using transitions. Thus, if an agent with initial state exists somewhere in the network, the base station has infinitely many chances to interact with a neighboring agent with initial state. This implies that the base station is able to repeatedly assign red and blue to neighboring agents with initial state unless no agent anywhere in the network has initial state. Since the base station assigns red and blue alternately, the uniform bipartition is completed after no agent has initial state.

To make red and blue alternately, the base station has a state set Q b = {b red , b blue }. Using its current state, the base station decides which color to use for the next interaction with a neighboring agent with initial state. Now, to move the position of an initial state in the communication graph, if an agent with initial state and an agent with red (or blue) state interact, they exchange their states. This implies that eventually an agent adjacent to the base station has initial state and then the agent and the base station interact (global fairness guarantees that such interaction eventually happens). Transition rules of the protocol are the following (for each transition rule (p, q) → (p , q ), transition rule (q, p) → (q , p ) exists, but we omit the description).

(b

red , initial) → (b blue , red) 2. (b blue , initial) → (b red , blue) 3. (blue, initial) → (initial, blue) 4. (red, initial) → (initial, red)
From these transition rules, the protocol converges when no agent has initial state (indeed, no interaction is defined when no agent has initial state).

Theorem 1. In the population protocol model with a non-initialized base station, there exists a symmetric protocol with three states per agent that solves the uniform bipartition problem with designated initial states assuming global fairness in arbitrary communication

Variables at the base station:

RB ∈ {r, b}: The state that the base station assigns next Variables at an agent x: color x ∈ {ini, r, b}: Color of the agent, initialized to ini depth x ∈ {⊥, 1, 2, 3, . . . , P }: Depth of agent x in a tree rooted at the base station, initialized to ⊥ 1: when an agent x and the base station interact do Note that, under weak fairness, this protocol does not solve the uniform bipartition problem. This is because we can construct a weakly-fair execution of this protocol such that some agents keep initial state infinitely often. For example, we can make an agent keep initial by constructing an execution in the following way.

If the agent (in initial) interacts with an agent in red or blue, the next interaction occurs between the same pair of agents.

Upper Bound for Symmetric Protocols under Weak Fairness

A protocol over arbitrary graphs

In this protocol, every agent x has variables color x and depth x . Variable color x represents the color of agent x. That is, for an agent x, if color x = ini or color x = r holds, f (s(x)) = red holds. On the other hand, if color x = b holds, f (s(x)) = blue holds. The protocol is given in Algorithm 1. Note that this algorithm does not care an initiator and a responder. The basic strategy of the protocol is the following. 1. Create a spanning tree rooted at the base station. Concretely, agent x assigns its depth in a tree rooted at the base station into variable depth x . Variable depth x is initialized to ⊥. Variable depth x obtains the depth of x in the spanning tree as follows: If the base station and an agent p with depth p = ⊥ interact, depth p becomes 1. If an agent q with depth q = ⊥ and an agent p with depth p = ⊥ interact, depth p becomes depth q + 1. By these behaviors, for any agent x, eventually variable depth x has a depth of x in a tree rooted at the base station. 2. Using the spanning tree, carry the initial color ini toward the base station and make the base station assign r and b to agents one by one. Concretely, if agents x and y interact and both depth y < depth x and color x = ini hold, x and y exchange their colors (i.e., ini is carried from x to y). Hence, since ini is always carried to a smaller depth, eventually an agent z with depth z = 1 obtains ini. After that, the base station and the agent z interact and the base station assigns r or b to z. Note that, if the base station assigns r (resp., b), the base station assigns b (resp., r) next. Then, for any agent v, eventually color v = ini holds. Hence, there exist n/2 red (resp., blue) agents, and n/2 blue (resp., red) agents if variable RB in the base station has r (resp., b) as an initial value. Therefore, the protocol solves the uniform bipartition problem. Theorem 2. Algorithm 1 solves the uniform bipartition problem. That is, there exists a protocol with 3P + 1 states and designated initial states that solves the uniform bipartition problem under weak fairness assuming arbitrary communication graphs with a non-initialized base station.

A protocol with constant states over a restricted class of graphs

In this subsection, we show that the space complexity of Algorithm 1 can be reduced to constant for communication graphs such that every cycle either includes the base station or its length is not a multiple of l, where l is a positive integer at least three.

We modify Algorithm 1 as follows. Each agent maintains the distance from the base station by computing modulo l plus 1. That is, we change lines 7 and 8 in Algorithm 1 to depth x ← depth y mod l + 1 and depth y ← depth x mod l + 1, respectively. Now depth x ∈ {⊥, 1, 2, 3, . . ., l} holds for any agent x. Then we redefine the relation depth x < depth y in lines 9 and 12 as follows: depth x < depth y holds if and only if either

depth x = 1 ∧ depth y = 2, depth x = 2 ∧ depth y = 3, depth x = 3 ∧ depth y = 4, . . ., depth x = l -1 ∧ depth y = l, or depth x = l ∧ depth y = 1 holds.
We can easily observe that these modifications do not change the essence of Algorithm1. For two agents x and y, we say x < y if depth x < depth y holds. Each agent x eventually assigns a depth of x modulo l plus 1 to depth x , and at that time there exists a path x 0 , x 1 , . . . , x h such that x 0 is a neighbor of the base station, x = x h holds, and x i < x i+1 holds for any 0 ≤ i < h. In addition, there exists no cycle x 0 , x 1 , . . . , x h = x 0 such that x i < x i+1 holds for any 0 ≤ i < h. This is because, from the definition of relation '<', the length of such a cycle should be a multiple of l, but we assume that underlying communication graphs do not include a cycle of agents in V p whose length is a multiple of l. Hence, similarly to Algorithm 1, we can carry the initial color ini toward the base station and make the base station assign r and b to agents one by one.

Corollary 3. There exists a protocol with 3l + 1 states and designated initial states that solves the uniform bipartition problem under weak fairness assuming arbitrary communication graphs with a non-initialized base station if, for any cycle of the communication graphs, it

either includes the base station or its length is not a multiple of l, where l is a positive integer at least three.

Upper and Lower Bounds with No Base Station

In this section, we show upper and lower bounds of the number of states to solve the uniform bipartition problem with no base station and designated initial states over arbitrary communication graphs. Concretely, under global fairness, we prove that the minimum number of states for asymmetric protocols is four, and the minimum number of states for symmetric protocols is five. Under weak fairness, we prove that the uniform bipartition problem cannot be solved without a base station using proof techniques similar to those Fischer and Jiang

(r

ω , r ω ) → (r, b) 2. (r ω , b ω ) → (b, b) 3. (r ω , r) → (r, r ω ) 4. (b ω , b) → (b, b ω ) 5. (r ω , b) → (r, b ω ) 6. (b ω , r) → (b, r ω )

Upper Bound for Protocols under Global Fairness

In this subsection, over arbitrary graphs with designated initial states and no base station under global fairness, we give an asymmetric protocol with four states and a symmetric protocol with five states. First, we show the asymmetric protocol with four states. We define a state set of agents as Q = {r ω , b ω , r, b} , and function f as follows:

f (r ω ) = f (r) = red and f (b ω ) = f (b) = blue.
We say an agent has a token if its state is r ω or b ω . Initially, every agent has state r ω , that is, every agent is red and has a token. The transition rules are given in Algorithm 2 (for each transition rule (p, q) → (p , q ) except for transition rule 1, transition rule (q, p) → (q , p ) exists, but we omit the description).

The basic strategy of the protocol is as follows. When two agents with tokens interact and one of them is red, a red agent transitions to blue and the two tokens are deleted (transition rules 1 and 2). Since n tokens exist initially and the number of tokens decreases by two in an interaction, n/2 blue agents appear and n/2 red agents remain after all tokens (except one token for the case of odd n) disappear. To make such interactions, the protocol moves a token when agents with and without a token interact (transition rules 3, 4, 5, and 6). Global fairness guarantees that, if two tokens exist, an interaction of transition rule 1 or 2 happens eventually. Therefore, the uniform bipartition is achieved by the protocol.

Theorem 4. Algorithm 2 solves the uniform bipartition problem. That is, there exists a protocol with four states and designated initial states that solves the uniform bipartition problem under global fairness over arbitrary communication graphs.

Furthermore, we obtain a symmetric protocol under the assumption by using a similar idea of the transformer proposed in [17]. The transformer simulates an asymmetric protocol on a symmetric protocol. To do this, the transformer requires additional states. Moreover, the transformer works with complete communication graphs. We show that one additional state is sufficient to transform the asymmetric uniform bipartition protocol into the symmetric protocol even if we assume arbitrary graphs (see the full version [34]). Theorem 5. There exists a symmetric protocol with five states and designated initial states that solves the uniform bipartition problem under global fairness with arbitrary communication graphs.

Lower Bound for Asymmetric Protocols under Global Fairness

In this section, we show that, over arbitrary graphs with designated initial states and no base station under global fairness, there exists no asymmetric protocol with three states.

To prove this, we first show that, when the number of agents n is odd and no more than P/2, each agent changes its own state to another state infinitely often in any globally-fair execution Ξ of a uniform bipartition protocol Alg, where P is a known upper bound of the number of agents. This lemma holds regardless of the number of states in a protocol. Lemma 6. Assume that there exists a uniform bipartition protocol Alg with designated initial states over arbitrary communication graphs assuming global fairness. Consider a graph G = (V, E) such that the number of agents n is odd and no more than P/2. In any globally-fair execution Ξ = C 0 , C 1 , . . . of Alg over G, each agent changes its state infinitely often.

Proof. (Proof sketch) First, for the purpose of contradiction, we assume that there exists an agent v α that never changes its state after some stable configuration C h in a globally-fair execution Ξ over graph G. Let s α be a state that v α has after C h . Let v β ∈ V be an agent adjacent to v α and S β be a set of states that v β has after C h . Since the number of states is finite, there exists a stable configuration C t that occurs infinitely often after C h . Next, let

G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be graphs that are isomorphic to G. Moreover, let v α ∈ V 1 (resp., v n+β ∈ V 2
) be an agent that corresponds to v α ∈ V (resp., v β ∈ V ). We construct G = (V , E ) by connecting G 1 and G 2 with an additional edge (v α , v n+β ) (see Figure 1). Over G , we consider an execution Ξ such that, agents in G 1 and G 2 behave similarly to Ξ until C t occurs in G 1 and G 2 , and then make interactions so that Ξ satisfies global fairness. Since Ξ is globally-fair, we can show the following facts after G 1 and G 2 reach C t in Ξ .

v α has state s α as long as v n+β has a state in S β . v n+β has a state in S β as long as v α has state s α . From these facts, in Ξ , v α continues to have state s α and v n+β continues to have a state in S β . Hence, in Ξ , each agent in V 1 cannot notice the existence of agents in V 2 , and vice versa. This implies that, in stable configurations, #red(V ) = #red(V 1 ) = #red(V 2 ) and #blue(V ) = #blue(V 1 ) = #blue(V 2 ) hold. Since the number of agents in G is odd, #red(V ) -#blue(V ) = 1 or #blue(V ) -#red(V ) = 1 holds in stable configurations of Ξ. Thus, in stable configurations of Ξ , |#red(V ) -#blue(V )| = 2 holds. Since Ξ is globally-fair, this is a contradiction. Now we prove impossibility of an asymmetric protocol with three states. The outline of the proof is as follows. For the purpose of contradiction, we assume that there exists a protocol Alg that solves the problem with three states. From Lemma 6, in any globally-fair execution, some agents change their state infinitely often. Now, with three states, the number of red or blue states is at least one and thus, if we assume without loss of generality that the number of blue states is one, agents with the blue state change their color eventually after a stable configuration. This is a contradiction. Theorem 7. There exists no uniform bipartition protocol with three states and designated initial states over arbitrary communication graphs assuming global fairness.

Lower Bound for Symmetric Protocols under Global Fairness

In this section, we show that, with arbitrary communication graphs, designated initial states, and no base station assuming global fairness, there exists no symmetric protocol with four states. Recall that, with designated initial states and no base station, clearly any symmetric

= C 0 , C 1 , C 2 , . . . of Alg with G = (V , E ). For i ≤ t, when v x interacts with v y at C i → C i+1 , v x interacts with v y at C 4i → C 4i+1 , v x+3 interacts with v y+3 at C 4i+1 → C 4i+2 , v x+6 interacts with v y+6 at C 4i+2 → C 4i+3 , and v x+9 interacts with v y+9 at C 4i+3 → C 4i+4 .
After C 4t , make interactions between agents in V red until agents in V red converge and #ini(V red ) ≤ 1 holds. We call the configuration C t . After C t , make interactions so that Ξ satisfies global fairness.

Until C 4t , agents in V 1 , V 2 , V 3 , and V 4 behave similarly to agents in V from C 0 to C t . This implies that, in C 4t , every agent in V red has state ini r . From Lemma 12, since ini r is the initial state of agents, it is possible to make interactions between agents in V red until agents in V red converge and #ini(V red ) ≤ 1 holds. Moreover, since v 0 is the only agent that has ini r in C t , no agent in V i \V red (1 ≤ i ≤ 4) has state ini r or ini b in C 4t . Hence, #ini ≤ 1 holds in C t . By Corollary 13, if #ini ≥ 2 does not hold, no agent can change its color. Thus, since #ini ≤ 1 holds after C t by Lemma 11, no agent can change its color after C t . Since v 1 and v 2 are blue in C t , v 1 , v 2 , v 4 , v 5 , v 7 , v 8 , v 10 , and v 11 are blue in C t . In addition, #blue(V red ) = #red(V red ) holds. Hence, #blue(V ) -#red(V ) = 8 holds. Since no agent can change its color after C t and Ξ is globally-fair, this is a contradiction.

Next, consider the case of #red(V ) -#blue(V ) = 1. In this case, we can prove in the same way as the case of #blue(V ) -#red(V ) = 1. However, in the case, we focus on ini b instead of ini r . That is, we assume that agents in V red (i.e., v 0 , v 3 , v 6 , and v 9 ) have ini b in C 4t . From C 4t , we make v 0 (resp., v 6 ) interact with v 3 (resp., v 9 ) once. Then, by Lemma 10, all of them transition to ini r . After that, since all agents in V red have ini r , we can construct an execution such that only agents in V red interact and eventually #ini(V red ) ≤ 1 holds. As a result, we can lead to contradiction in the same way as the case of #blue(V ) -#red(V ) = 1.

Impossibility under Weak Fairness

In this subsection, assuming arbitrary communication graphs and designated initial states and no base station, we show that there is no protocol that solves the problem under weak fairness. Fischer and Jiang [21] proved the impossibility of leader election for a ring communication graph. We borrow their proof technique and apply it to the impossibility proof of a uniform bipartition problem.

The sketch of the proof is as follows: For the purpose of contradiction, let us assume that there exists such a protocol Alg. Consider an execution Ξ of Alg for a ring R 1 with three agents v 0 , v 1 , and v 2 . Without loss of generality, we assume that #red = 1 and #blue = 2 hold in a stable configuration of Ξ. After that, consider an execution Ξ of Alg for a ring R 2 with six agents v 0 , v 1 , v 2 , v 3 , v 4 , and v 5 (see Figure 3). We construct Ξ such that each agent behaves similarly to Ξ. Concretely, v i and v i+3 (0 ≤ i ≤ 3) behave similarly to v i . If v 0 interacts with v 1 (resp., v 2 ) in Ξ, v 0 interacts with v 1 (resp., v 2 ) and v 3 interacts with v 4 (resp., v 5 ) in Ξ . Similarly, If v 1 (resp., v 2 ) interacts with v 0 in Ξ, v 1 (resp., v 2 ) interacts with v 0 and v 4 (resp., v 5 ) interacts with v 3 in Ξ . If v 1 interacts with v 2 in Ξ, v 1 interacts with v 5 and v 4 interacts with v 2 in Ξ . Similarly, if v 2 interacts with v 1 in Ξ, v 5 interacts with v 1 and v 2 interacts with v 4 in Ξ . Observe that, if s(v i ) = s(v i ) = s(v i+3 ) holds before the interactions for 0 ≤ i ≤ 2, s(v i ) = s(v i ) = s(v i+3 ) holds even after the interactions. Thus, since s(v i ) = s(v i ) = s(v i+3 ) holds in the initial configuration, s(v i ) = s(v i ) = s(v i+3 ) continues to hold. Hence, in the stable configuration of Ξ , #red = 2 and #blue = 4 hold. This contradicts that Alg solves the problem. Therefore, we have the following theorem. Theorem 14. There exists no protocol that solves the uniform bipartition problem with designated initial states and no base station under weak fairness assuming arbitrary communication graphs.

Concluding Remarks

In this paper, we consider the uniform bipartition problem with designated initial states assuming arbitrary communication graphs. We investigated the problem solvability, and even provided tight bounds (with respect to the number of states per agent) in the case of global fairness.

Our work raises interesting open problems:

Is there a relation between the uniform bipartition problem and other classical problems such as counting, leader election, and majority? We pointed out the reuse of some proof arguments, but the existence of a more systematic approach is intriguing. What is the time complexity of the uniform bipartition problem?

4 Uniform

 4 studied space complexity under O P O D I S 2 0 2 0 33:Bipartition in the Population Protocol Model with Arbitrary Graphs

1 . 2 .

 12 ||H r | -|H b || ≤ 1 holds, and For every configuration C such that C * -→ C , each agent in H r (resp., H b ) remains red (resp., blue) in C .

Algorithm 1

 1 Uniform bipartition protocol with 3P + 1 states.

2 : 5 :

 25 if color x = ini and depth x = 1 then if depth x = ⊥ then depth x ← 1 6: when two agents x and y interact do 7: if depth y = ⊥ and depth x = ⊥ then depth x ← depth y + 1 8: else if depth x = ⊥ and depth y = ⊥ then depth y ← depth x + 1 9: if depth x < depth y and color y = ini then 10: color y ← color x 11: color x ← ini 12: if depth y < depth x and color x = ini then 13: color x ← color y 14: color y ← ini Note: If depth x = ⊥ holds, color x = ini holds.

Algorithm 2

 2 [21] used to show the impossibility of leader election. O P O D I S 2 0 2 0 33:10 Uniform Bipartition in the Population Protocol Model with Arbitrary Graphs Transition rules of the uniform bipartition protocol with four states.

Figure 1

 1 Figure 1 An example of communication graphs G and G (n = 5).

Figure 2

 2 Figure 2 An image of graphs G and G .

Figure 3

 3 Figure 3 Ring graphs R1 and R2.

Table 1

 1 The minimum number of states to solve the uniform bipartition problem with designated initial states over complete graphs[33, 35]. O(log log n) states and O(log n • log log n) expected time. Furthermore, the protocol of Gąsieniec et al.[23] is space-optimal for solving the problem in polylogarithmic time.

	base station	fairness	symmetry	upper bound lower bound
	initialized/non-initialized base station	global weak	asymmetric symmetric asymmetric symmetric	3 3 3 3		3 3 3 3
	no base station	global weak	asymmetric symmetric asymmetric symmetric	3 4 3	unsolvable	3 4 3
	a protocol with

In [29], Sudo et al. presented a leader election protocol with O(log n) states and O(log n) expected time. This protocol is time-optimal for solving the problem. Finally, Berenbrink et al. [15] proposed a time and space optimal protocol that solves the leader election problem with O(log log n) states and O(log n) expected time. In the case of arbitrary communication graphs, it turns out that self-stabilizing leader election is impossible [7]

Table 2

 2 The minimum number of states to solve the uniform bipartition problem with designated initial states over arbitrary graphs. P is a known upper bound of the number of agents, and l ≥ 3 and h are positive integers.

	base station	fairness	symmetry	upper bound	lower bound
	initialized/non-initialized	global	asymmetric symmetric	3* 3*		3 † 3 †
	base station	weak	asymmetric	3P + 1* 3l + 1 for no l • h cycle *	3 †
			symmetric	3P + 1* 3l + 1 for no l • h cycle *	3 †
	no base station	global weak	asymmetric symmetric asymmetric symmetric	4* 5*	unsolvable* unsolvable †	4* 5*
				* Contributions of this paper

† Deduced from Yasumi et al.

[35]

  An execution Ξ is weakly-fair if, for each pair of agents (v, v ) ∈ E, v (resp. v ) interacts with v (resp., v) infinitely often 1 . An execution Ξ is globally-fair if, for every pair of configurations C and C such that C → C , C occurs infinitely often when C occurs infinitely often. Intuitively, global fairness guarantees that, if configuration C occurs infinitely often, then every possible interaction in C also occurs infinitely often. Then, if C occurs infinitely often, C satisfying C → C occurs infinitely often, we can deduce that C satisfying C → C also occurs infinitely often. Overall, with global fairness, if a configuration C occurs infinitely often, then every configuration C * reachable from C also occurs infinitely often.

we say C is reachable from C, denoted by C every i (i ≥ 0).

We use this definition for the lower bound under weak fairness, but for the upper bound we use a slightly weaker version. We show that our proposed protocols for weak fairness works if, for each pair of agents (v, v ) ∈ E, v and v interact infinitely often (i.e., for interactions by some pair of agents v and v , it is possible that v only becomes an initiator and v never becomes an initiator).

Funding This work was supported by JSPS KAKENHI Grant Numbers 18K11167, 20H04140, 20J21849, and JST SICORP Grant Number JPMJSC1806. This work was partially funded by the ANR project SAPPORO, ref. 2019-CE25-0005-1.

protocol never solves the problem if the number of agents n is two. Thus, we assume that 3 ≤ n ≤ P holds, where P is a known upper bound of the number of agents. Note that the symmetric protocol proposed in subsection 4.1 solves the problem for 3 ≤ n ≤ P . Theorem 8. There exists no symmetric protocol for the uniform bipartition with four states and designated initial states over arbitrary graph assuming global fairness when P is twelve or more.

For the purpose of contradiction, suppose that there exists such a protocol Alg. Let R (resp., B) be a state set such that, for any s ∈ R (resp., s ∈ B), f (s) = red (resp., f (s ) = blue) holds. First, we show that the following lemma holds from Lemma 6. Let ini r and r (resp., ini b and b) be states belonging to R (resp., B). In addition, without loss of generality, assume that ini r is the initial state of agents. Then, we can prove the following lemma.

Lemma 10. There exists some

Without loss of generality, assume that (ini r , ini r ) → (ini b , ini b ) and (ini b , ini b ) → (ini r , ini r ) exist. For some population V , we denote the number of agents with ini r (resp., ini b ) belonging to V as #ini r (V ) (resp., #ini b (V )). Moreover, let #ini(V ) be the sum of #ini r (V ) and #ini b (V ). When V is clear from the context, we simply denote them as #ini r , #ini b , and #ini, respectively. Then, we can prove the following lemmas and corollary.

Lemma 11. There does not exist a transition rule such that #ini increases after the transition.

Lemma 12. Consider a globally-fair execution Ξ of Alg with some complete communication graph G. After some configuration in Ξ, #ini ≤ 1 holds.

Corollary 13. Consider a state set

From now on, we prove Theorem 8. Consider a globally-fair execution Ξ = C 0 , C 1 , C 2 , . . . of Alg with a ring communication graph G = (V, E) such that the number of agents is three, where

First, consider the case of #blue(V ) -#red(V ) = 1. By Lemma 6, red agents keep exchanging r for ini r in Ξ. Moreover, by Lemma 12, there exists a stable configuration in Ξ such that #ini ≤ 1 holds. From these facts, there exists a stable configuration C t of Ξ such that there exists exactly one agent that has ini r . Without loss of generality, we assume that the agent is v 0 .

Consider the communication graph G = (V , E ) that includes four copies of G. The details of G are as follows:

Let