Jean-Louis Kraus

From 'molecules of life' to new therapeutic approaches, an evolution marked by the advent of artificial intelligence: the cases of chronic pain and neuropathic disorders

The large families of the molecules of life are at the origin of the discovery of new compounds with which to treat disease. The arrival of artificial intelligence (AI) has considerably modified the search for innovative bioactive drugs and their therapeutic applications. Conventional approaches at different organizational research levels have emerged and, thus, AI associated with gene and cell therapies could supplant conventional pharmacotherapy and facilitate the diagnosis of pathologies. Using the examples of chronic pain and neuropathic disorders, which affect a large number of patients, I illustrate here how AI could generate new therapeutic approaches, why some compounds are seen as recreational drugs and others as medicinal drugs, and why, in some countries, psychedelic drugs are considered as potential therapeutic drugs but not in others.

Introduction

Scientists, social scientists, and humanists must communicate with and understand each other because the survival of human-kind requires the development of scientific programs the social implications and human consequences of which have to be taken into account.

Regardless of the applications of their discoveries ,scientists in general and medicinal chemists in particular as creators of new molecules, should always recall the wisdom of Indian Iroquois tribes: before taking a decision that could have consequences for the future of the tribe, Iroquois chiefs evoked the impact that this decision would have had on seven past Iroquois generations [START_REF] Dixon-Kennedy | Native American Myth & Legend[END_REF].Today, although new technology inventors think about the impact of their discovery on future human generations, most do not consider the negative impact they might have had on past generations. This statement holds true for the discovery of new molecules regardless of their fields of application, be it health, agriculture, or advanced materials for industrial purposes, among others. Thus, wisdom should be the prime quality of chemists creating new molecules, who should never forget that molecules atthe origin of life on Earth are at the base of the current pharmaco-peia used by humans.

Small molecules of life at the basis of the world pharmacopeia Starting from organic molecules derived from carbon and other elements, such as hydrogen, oxygen, sulfur, and nitrogen, millions of combinations exist in nature or have been synthesized, including those upon which life itself is based. The most significant are the molecules that constitute the code of life, which have revolutionized our understanding of biological phenomena. Nature has equipped every cell with a complete set of blueprints stored in the nucleus in the form of molecules of DNA, involved in genetics and protein synthesis [START_REF] Watson | Molecular Biology of the Gene[END_REF].Then come the so-called 'molecules of mercy', namely pain relievers. The most popular is perhaps acetyl salicylic acid (aspirin), medicinally used to alleviate common aches and pain. Many of the established organic molecule-based pain relievers occur naturally in plants, with morphine, which is 50 times as potent as aspirin, a notable example. Related to the morphine family, numerous structurally related analogs and other drugs, such as heroin, methadone, codeine, pentazocine, cocaine, procaine, atropine, and scopolamine, have been described. Sometimes addictive, some-times sedative, such drugs, including barbiturates and tranquilizers, have their place in medicine if used correctly [3].The fundamental problem related to such drugs is that they are open to abuse. Feel tense? Take a pill. Can't sleep? Take a pill. How many times do we hear such refrains? Humans take energizers, sedatives, analgesics, and even hypnotics to better cope with their pressure-filled lives. Even Cleopatra supposedly took sleeping pills while Mark Anthony was away on a trip! Medicinal chemists have synthesized specific drugs to satisfy increasingly pressing demands from society, resulting in compounds such as barbiturates and tranquilizers (e.g., phenothiazine, meprobamate or chlordiazepoxide). Unfortunately, drug-taking by itself is rarely a cure for psychological conditions, and some of these drugs can be dangerous if used without proper guidance. In addition to drugs for pain and psychological conditions, humans have also exploited naturally occurring compounds to create specific molecules to treat microbial disease. For example, quinine and other antimalarials, sulfanilamide, penicillin, streptomycin, chloramphenicol, and tetracyclines were developed against resistant strains of microorganisms. However, given the prevalence of multidrug-resistant organisms, there is a continuing need to create and synthesize new antibiotics to control such organisms [START_REF] Morris | Research needs in antibiotic stewardship[END_REF].The steroid family and related compounds represent a major breakthrough for medicinal chemistry development, because these compounds have various important biological functions, including as vitamins, sex hormones (testosterone, estradiol, and progesterone), contraceptives (norethindrone) and arteriosclerotics (cholesterol), which represent major areas of steroid involvement [5]. Another family of compounds with diverse hormone-like effects are prostaglandins, found in almost every tissue in humans and other animals, and which have a variety of effects, including as vasodilators, in platelet aggregation, inflammation, or smooth muscle contraction [6]Our unending search for life's meaning, deep psychological satisfaction, and insights into immortality have led us to collect, catalog, and even concoct substances that allow us to transcend normal physical limitations and routines. This is why humans have been interested in so-called 'molecules of mysticism': the mind changers [START_REF] Goodman | Organic Molecules in Action[END_REF]. Humans have eaten, imbibed, sniffed, and inject extracts of plant and animal origin to achieve altered consciousness. Four classes of molecule that affect mental processes can be distinguished. Most fit into the classification of hallucinogenic or psychomimetic dugs, or significant mind-altering molecules: (i) lysergic acid derivatives (LSD, alkaloids from ololiuqui, etc.); (ii) phenethylamine compounds (mescaline, amphetamines, etc.); (iii) tryptamine-based molecules (psilocin psilocybin, bufotenine, etc.); and (iv) cannabinoids from Cannabis sativa(hashish, marihuana, etc.)The suggestion that doctors should be paid for keeping people healthy, rather than curing them after they get sick, has been at the origin of the growing interest in vitamins and in so-called 'health foods'. It is also why medicinal chemists have been involved in the creation, synthesis, and biological studies of molecules of growth and health. These molecules are mainly vitamins [8], discovered primarily by scientists seeking to cure specific diseases, such as beriberi, facial tissue deterioration and related forms of dermatitis, pellagra, scurvy, and night blindness, which all arise from vitamin deficiencies, mainly vitamin B1 (thiamine), vitamin B2 (ribofla-vin), vitamin B6 (pyridoxine), nicotinic acid (niacin) and nicotinamide, vitamin C (ascorbic acid), vitamin A (retinol), and vitamin E (tocopherols). The structure and chemistry of these molecules of growth and health differ substantially from each other, but have important role as cofactors in regulating appropriate enzyme actions. Who among us cannot recall the effect of head colds or simply blocked nasal passages on our sense of taste? Thus, molecules of the senses (taste, odor, and attraction) have been isolated and synthesized by chemists: (i) taste molecules: monosaccharides(glucose and related analogs), disaccharides (maltose and lactose),amino acids and peptides that have a sweet taste.; (ii) odor molecules, which can belong to different types of fragrance: camphoraceous, (D-camphor); pungent, (formaldehyde, acetic acid, allyl alcohol); ethereal, (chloroform, propyl alcohol), floral, (geraniol,terpineol, ionones, benzyl acetate); peppermint (menthone, cyclohexanone, piperitol), musky (cyclohexadecanone, androstanol, muscone); and putrid (cadaverine, skatole, amylmercaptan, hydrogen sulfide); and (iii) molecules of attraction(pheromones), which are chemical substances that allow intraspecies communication. The structure and chemistry attraction pheromones, such as disparlure and propylure, differ substantially from each other depending on the species. The common denominator among these molecules is that they are volatile, long-lasting, and have a potential irritating quality. Terpenoids and related molecules are common types of molecule isolated from insects andants and which are used in defense, such as citronellal, geraniol, citral, farnesal, limonene, and perillene.

Benzoquinones and related analogs are among the most widely distributed arthropod defensive compounds. Other compounds, such as cresols, salicylaldehyde, benzoic acids, and benzaldehyde, have also been iso-lated. Synthetic organic chemists have focused on insect pheromones with the aim of controlling the destructive feature sof insect populations.

Numerous attractants and repellents have been discovered, such as trimediure against

Mediterranean fruit flies, methyl benzoate against mites, N-butylacetanilide against ticks, and 2-butyl-2-ethyl-1,3-propane diol against mosquitos. Although such compounds were designed to be effective, safe, and specific for the particular species, some are ineffective and can even be toxic.Given the earlier discussion of our exploitation of naturally occurring molecules, the resulting large numbers of approved pharmaceutical medicines worldwide, and the fact that their effects are sometimes suboptimal, would it now be better to search for new health treatments using gene or cellular therapies rather than to continue the research and development of small molecules? Most traditional drugs, as well as >90% of therapeutics current-ly marketed, are small molecules [START_REF] Hopkins | The druggable genome[END_REF]. The key drawbacks of conventional small-molecule therapeutics are that they can do only one thing and that they keep doing it, regardless of the physio-logical state of the patient, because they are not equipped to receive feed-back from the body. One significant example are beta-blocker drugs, which keep blocking the functioning of the heart regardless of the physiological state of the patient [START_REF] Frishman | Current Cardiovascular Drugs[END_REF]. One area where small molecules are, and will likely remain, the best possible therapeutic tools, is the fight against bacteria, fungi, and viruses. Small-molecule inhibitors are effective antimicrobials because they target enzymes specific to the target species. However, when our own proteins need to be regulated for therapeutic purposes, the 'single-mindedness' of enzyme inhibitors or receptor ligands, as well as their unresponsiveness to signals sent by the body, remain problematic. This is why new immunological or genomic therapies are emerging and beginning to replace existing standard small-molecule drugs.

New therapeutic cellular approaches: the use of large molecules Cellular behaviors, such as adhesion, migration, and cell death by apoptosis or other mechanisms, are mediated and regulated via protein-protein interactions (PPIs). The ability to selectively disrupt or enhance individual PPIs gives unprecedented leverage over the cell, essentially telling the cell what to do, and when to do it, in a language that it understands [11]. This could help to elucidate the intricacies of cell signaling, which is currently a significant challenge in biological research. By introducing a protein with modified signaling properties into a cell, it is possible to affect the behavior of that cell. Cancer cells and dying neurons represent obvious targets. Given that the biological function of signaling proteins is to deliver chemical messages, if one could tell cancer cells to stop proliferating and dying neurons to stay alive, crucial disease could be cured or prevented. Viral and non viral gene delivery systems, as well as the identification of promoters driving expression in specific cell types, are under development [START_REF] Bartel | Directed evolution of novel adeno-associated viruses fortherapeutic gene delivery[END_REF]. Arecent application of such a technique was the treatment of Leber congenital amaurosis (LCA), a rare inherited eye disease that appears at birth or during the first few months of life; using adeno-associated virus gene therapy, it was possible to restore vision in patients with LCA [START_REF] Imonelli | Gene therapy for Leber's congenital amaurosis is safe andeffective through 1.5 years after vector administration[END_REF].For therapeutic purposes, it is often necessary to selectively enhance or reduce only one interaction with a particular signaling protein, out of several that are normally engaged in the target reaction. Arrestins, a small family of proteins, important for regulating signal transduction at G-protein-coupled receptors, repre-sent a significant model for specific interaction approaches,because these elongated molecules have a variety of roles in several biological processes, such as the regulation and localization of phosphodiesterase, programmed cell death, infectious diseases, host-pathogen interactions, regulation of GTPases, airway epithelium and asthma, as well as pain and anesthesia [START_REF] Gurevich | The structural basis of arrestinmediatedregulation of G-protein-coupled receptors[END_REF]. Arrestin binding to a receptor blocks further G proteinmediated signaling, targets receptors for internalization, and redirects signaling to alternative G protein-independent pathways [START_REF] Smith | Biased signalling: from simple switches to allostericmicroprocessors[END_REF].

Drugs for medical use: the therapeutic context

The search continues for new drugs or molecules with improvedbiological properties, which ideally would only have beneficialhealth benefits. To address this challenge, several questions arise,such as: (i) in what therapeutic context can drugs be used and inwhat form? (ii) How can we measure the benefit-risk ratio of themedical use of drugs? (iii) How can we supervise the productionand sale of drugs for medical use? (iv) What is the differencebetween a drug and a medicinal drug? (v) Why are certain mole-cules for recreational use struck by pharmacological infamy? Let usconsider first the case of psychoactive drugs.Thirty countries have legalized cannabis for therapeutic use.France remains resistant to the commercialization of treatmentsinvolving cannabinoid derivatives for certain forms of epilepsy,multiple sclerosis, or chronic pain. However, behind the possibleuse of cannabinoids, there is a whole family of molecules that arebeginning to be researched and used for such conditions, the so-called 'molecules of mysticism' or 'mind changers' [START_REF]The HealthEffects of Cannabis and Cannabinoids: The Current State of Evidence andRecommendations for Research[END_REF].Can we legalize those drugs for medical use? Questions abouttheir use, the lack of legislation, and reluctance around theirtherapeutic application, too often considered as recreational, arestill questions that need to be addressed, because some of thesecompounds could be helpful for patients with chronic pain,spasms (notably linked to multiple sclerosis), or certain childhoodepilepsies.Hallucinogens and psychedelic drugs are being investigated todiscover possible new therapeutic applications. Researchers arestudying the action of hallucinogenics on certain treatment-resis-tant pathologies, such as chronic depression, alcohol and drugdependence, post-traumatic stress disorder, and obsessive-compul-sive disorder (OCD). In France and other countries, some psychedel-ic drugs are illegal, such as ketamine, LSD, MDMA (ecstasy),psilocybin mushrooms, ayahuasca, and ibogaine [17]. Such com-pounds, similar to chemotherapeutic drugs for cancer, or morphinefor pain, would need to be administrated cautiously. Although suchpsychedelic drugs are listed as illegal because they alter states ofconsciousness, they could be also interesting as medical treatments.As an example, A. Huxley took mescaline, the active alkaloid ofpeyote, the Indian cactus, resulting in colorful visions accompaniedby various psychological phenomena [START_REF] Huxley | The Doors of Perception[END_REF]. However, the use ofhallucinogens and narcotics as 'antiintellectual' drugs would bean inappropriate way to find answers for medical conditions currently lacking effective treatments [19,[START_REF] Griffitths | Psilocybin produces substantial and sustained decreasesin depression and anxiety in patients with life-threatening cancer: a randomizeddouble-blind trial[END_REF].A recent study reported that psilocybin was effective at reducingsymptoms in humans with treatment-resistant depression [START_REF] Carhart-Harris | Psilocybin for treatment-resistant depression: fMRImeasured brain mechanisms[END_REF].Psilocybin can help patients become more optimistic and could bean effective way to treat tobacco [START_REF] Johnson | Long-term follow-up of Psilocybin-facilitated smokingcessation[END_REF] and alcohol abuse [START_REF] Bogenschutz | Psilocybin-assisted treatment for alcoholdependence: a proof of concept study[END_REF].Patients who used psychedelics have lower rates of psychologicaldistress and suicidality compared with those who do not usepsychedelics; for example, psilocybin made patients living withlung cancer more comfortable compared with control groups [START_REF] Griffitths | Psilocybin produces substantial and sustained decreasesin depression and anxiety in patients with life-threatening cancer: a randomizeddouble-blind trial[END_REF].Even if results from clinical trials with psilocybin were promising,psychotherapy trials confirming its efficacy and safety are stillneeded.

Nevertheless, the potential effects of psilocybin on de-pression, anxiety, and palliative care should be considered infuture studies.

The case of drugs for chronic pain

Research is beginning to focus on searching for new syntheticmolecules and new immunopharmacological approaches to re-place conventional drug therapies. The development of therapiesfor chronic pain is an example of research duality between newsynthetic molecules (small molecules) and immunologicalapproaches involving large molecules (proteins, chemokines,and neurokines). Chronic pain is a major problem for humanhealth, affecting 20% of the world's population; it also has aconsiderable economic impact and its impact will continue toincrease with increasing life expectancy; in addition, chronic painis the number one cause of long-term disability in the USA; 27% ofchronic pain is related to low back pain; 77% of patients withchronic pain report feeling depressed because of their condition;and 66% of patients seek treatment from medical doctors, 25%from chiropractors, and 15% from pain specialists [. Opioids continue to be prescribed to patients with chronic paindespite the fact that their use is broadly accepted to be mosteffective for acute pain, cancer pain, and palliative care. Addition-ally, only 23% of patients with chronic pain found opioids to beeffective [START_REF] Dalhamer | Prevalence of chronic pain and high-impact chronic painamong adults-United States[END_REF]. Chronic and neuropathic pain treatments mainlyrely on chemotherapeutic agents. Chronic (nociceptive) pain fromtissue inflammation or damage (as in rheumatoid arthritis andcancer pain) is best treated with opioids, such as opiorphin [START_REF] Rougeot | Systemically active human opiorphin is a potent yet nonaddictive analgesic without drug tolerance effects[END_REF],whereas neuropathic pain (caused by a damaged or dysfunctionalnervous system) is treated more effectively by drugs such as tricy-clic antidepressants [START_REF] Gilman | Tricyclic antidepressant pharmacology and therapeutic druginteractions updated[END_REF], serotoninnorepinephrine reuptake inhi-bitors, and anticonvulsants [START_REF] Wright | An update on the pharmacologic managementand treatment of neuropathic pain[END_REF][START_REF] Cashman | Inhibition of serotonin and norepinephrinereuptake and inhibition of phosphodiesterase by multi-target inhibitors as potentialagents for depression[END_REF]. For example, lacosamide [a USFood and Drug Administration (FDA)-approved drug] abolishesthe disease-specific phenotype by blocking induced pluripotentstem cell (iPSC)-derived nociceptors [START_REF] Namer | Pain relief in a neuropathy patient by lacosamide: proof ofprinciple of clinical translation from patient-specific iPS cell-derived nociceptors[END_REF].

Unfortunately, the use ofmost standard chemical synthetic drugs, including paracetamol-like drugs, acetyl salicylic analogs, noramidopyrine, floctafenin,nefopam, codeine derivatives, and other potent antalgic drugs,including morphine-related analogs, often induce adverse effects;thus, new immunological treatment approaches are under inves-tigation.One such approach reported was the injection of a chemokine-like protein TAFA4, in animal models of inflammatory or nerveinjury-induced pain. TAFA4, a chemokine-like protein, was shownto modulate injury-induced mechanical and chemical pain hyper-sensitivity in mice [START_REF] Delfini | TAFA4, a chemokine-like protein, modulates injury-induced mechanical and chemical pain hypersensitivity in mice[END_REF].

Another approach was based on thedevelopment of molecular-specific sodium channel (NAV 1.7,NAV 1.8) blockers [START_REF] Hameed | Nav1.7 and Nav1.8: role in the pathophysiology of pain[END_REF][START_REF] Siu | Voltage gated sodium channels as therapeutic targets for chronicpain[END_REF]. Natural toxins, such as saxitoxin [START_REF] Cusick | An overview on the marine neurotoxin,saxitoxin: genetics, molecular targets, methods of detection and ecologicalfunctions[END_REF]and aryl sulfonamide [START_REF] Kim | Synthesis and T-type calcium channel-blocking effects of aryl(1,5disubstituted-pyrazol-3-yl) methyl sulfonamides for neuropathic paintreatment[END_REF], show promise for treatment of neuro-pathic pain with minimal adverse effects.

Role of AI in the development of new drugs anddiagnostics for chronic pain and neuropathic disorders The use of AI in the health sector research has considerablymodified conventional approaches at different levels in the drugdiscovery process.Design, synthesis, identification, and screening of newtherapeutic moleculesThe synthesis of molecules remains one of the most importantchallenges for organic and medicinal chemists. Performing algo-rithms, such as the Chematica Computer Program [START_REF] Kluczick | Efficient synthesis of diverse medicinally relevant targetsplanned by computer and executed in the laboratory[END_REF], has shownthe effectiveness of AI in providing chemists with realistic solu-tions for molecule synthesis. For several decades, software allow-ing predictive structural drug and protein determination havebeen available, such as predictive nuclear magnetic resonance(NMR), and mass spectrometry (MS)/liquid chromatography(LC) software [START_REF] Berg | Three-dimensional protein structure can be determined byNMR spectroscopy and X-ray crystallography[END_REF]. Some software provides support for developingmolecular models de novo, whereas others directly support aspectsrelated to constructing molecular models, including moleculargraphics, interactive drawing and conformational editing. Suchsoftware is now frequently used by medicinal chemists and struc-tural biologists [37]. Using AI techniques with robot algorithmsenables researchers to quickly conduct millions of chemical, ge-netic, and pharmacological tests to rapidly identify active com-pounds, antibodies, or genes that modulate a particular pathway;such highthroughput screening is increasingly the technology ofchoice in drug discovery and is relevant to both the biology andchemistry fields [START_REF] Macarron | Impact of high-throughput screening in biomedicalresearch[END_REF]. AI in medicinal biology, diagnostic assistance programs, andpersonalized patient treatment programsThe 'omics revolution requiring Big Data mining has been themajor driving force behind the development of AI. The firstcomprehensive systems-biology dynamical model explaining pat-terning in planarian regeneration provided an automated, highlygeneralizable framework for identifying the underlying controlmechanisms responsible for the dynamic regulation of growth andform [START_REF] Lobo | Inferring regulatory networks from experimentalmorphological phenotypes: a computational method reverse-engineers planarianregeneration[END_REF]. Such systems could be helpful for clinical research inregenerative medicine.The first aim of health-related AI applications is to analyzerelationships between prevention or treatment techniques andpatient outcomes.

Various specialties have shown increased use ofAI to this end, such as disease diagnosis using computed tomogra-phy (CT), and magnetic resonance imaging (MRI) techniques [40];deep learning algorithms have been developed to search reportsand detect patterns that imply drug-drug interactions [START_REF] Xu | Incorporating user generated content for drug interactionextraction based on full attention mechanism[END_REF]; skincancer was detected more accurately using an AI system that used adeep learning convolutional neural network compared withdermatologist-based assessments [START_REF] Haenssle | Man against machine: diagnostic performance of a deeplearning convolutional neural network for dermoscopic melanoma recognition incomparison to 58 dermatologists[END_REF]; and in radiology, an algo-rithm was created that could better detect pneumonia in patients [START_REF] Rajpurkar | CheXNet: radiologist-level pneumonia detection on chestX-rays with deep learning[END_REF][START_REF] Bahl | High-risk breast lesions: a machine learning model topredict pathologic upgrade and reduce unnecessary surgical excision[END_REF].The ability to monitor patients using AI could allow for directcommunication to physicians in terms of whether possible diseaseactivity might have occurred [START_REF] Wahl | Artificial intelligence (AI) and global health: how can AIcontribute to health in resource-poor settings?[END_REF]. In addition, an AI tool that scanselectronic health record (her) data can accurately predict thecourse of disease in a person [46]. The primary aim of health-related AI applications is to analyze relationships between preven-tion or treatment techniques and patient outcomes. Among theseapplications, personalized medicine, and patient monitoring andcare represent the major challenges to be addressed [START_REF] Lu | Personalized medicine and human genetic diversity[END_REF]. AI appli-cation for the development of treatment protocols, such astreatmentbiomarker combinations in colon cancer (Erbitux-EFGR) and lung cancer (Xalkori-ALK), good examples of person-alized treatments [START_REF] Vincent | Biomarkers that currently affect clinical practice: EGFR,ALK, MET, KRAS[END_REF]. Other successful example of AI applicationis the prediction of correct personalized dosing treatments.AI applications in chronic painTechnologies to accurately evaluate a patient's pain level arenecessary given that half of patients with chronic pain also expe-rience anxiety or depression at some point because of their pain.Difficulties arise when carers try to ascertain a pa ent's pain levels,because sensa ons are inherently hard for pa ents to e press. owever, di erent I op ons are available for this purpose:The y Intelligent ssistant I so ware was developed by aFrench start-up ante et (www.mia-software.com) incorporatedin a bot. It regularly asks patients with chronic pain questionsabout their pain intensity, fatigue, and how frequently they aretaking medication. This allows patients to spontaneously notepain as it occurs, relaying the information to their carer andkeeping them informed. It also allows medical professionals toclearly identify when a patient needs to take a sleeping pill. Thisalso helps to combat the over-reliance on powerful and highlyaddictive analgesics, such as morphine. This algorithm also allows Patients to manage their pain autonomously with personalizedtherapeutic advice based on the data that they provide.AI can be used to assess pain levels through facial recognitiontechnology, which notes movements such as furrowed eyebrows,squeezed lips, and raised cheeks, to calculate pain levels. Thistechnology can also be used by anesthetists when determiningthe dose of morphine required for a patient. However, suchtechnology is only used for treating sharp, short-lasting pain.For patients who endure pain for a long time, the body alarmsystem stops working in a way which cannot be monitored by suchtechnology.AI can also be applied to neuropathic pain measurement basedon brain imaging. For example, brain images from individualpatients with chronic low back pain were collected when theirpain was at a low (baseline) state. The patients then performedphysical maneuvers intended to temporarily increase their pain,including movements such as sit-ups and back-arching motions,and then underwent repeated imaging. By using a machine-learning (ML) approach to compare brain images from individualpatients in the two states, researchers identified other specificbrain areas that were activated by exacerbated pain; by contrast,in normal pain, brain activity was increased only in the thalamus,a sensoryprocessing station in the brain [49].AI can also be exploited as an imaging biomarker for clinicalpain measurement. A specific biomarker that could be used fordiagnostic purposes to prove whether someone has chronic painwould be of value [START_REF] Long | Sustained effects of acupuncture stimulation investigated withcentrality mapping analysis[END_REF]. Although in the early stages of develop-ment, methods including structural and functional MRI andelectroencephalography, are being used. These methodologieshave already produced encouraging predictive models that havebeen tested on clinical populations [START_REF] Van Der Miesen | Neuroimaging-based biomarkers for pain: State of the fielding current directions[END_REF].

AI applications in neuropathic disorders

Disruptive technologies, such as ML algorithms, are especiallyrelevant to the discovery of compounds targeting neuropsychi-atric disorders, in which current therapies lead to many off-targeteffects. Leveraging AI technologies, new molecules are beingderived from psychoactive small-molecule compounds (SMC),such as psilocybin or LSD, to tackle unmet medical needs inmental healthcare. The development of sophisticated ML algo-rithms provides a set of tools that can improve discovery anddecision-making for specific questions based on sufficient, high-quality data. A typical application of SMC technology is psylo-cibin therapy [19], which aims to develop compounds with thetherapeutic benefits of psilocybin for depression, but with im-proved characteristics, such as quicker drug release and absorption or the absence of hallucinogenic effects typical topsychedelics. These technologies do not aim to replace classicalpsychedelics completely. Instead, the reformulation of psychoactive seed SMCs endeavors to make psychedelic therapy moreaccessible to a larger proportion of the population, such as thosewho react unfavorably to the hallucinatory effects or thoseindividuals with cardiac problems .Concluding remarks ' ature invents and man tries to copy it'. From the formation andevolution of initial molecules that gave rise to families of increas-ingly complex natural molecules with extraordinary biologicalproperties, organic chemists in general and medicinal chemistsin particular, have never stopped trying to create molecular struc-tures with improved biological properties for use in the clinic. Toachieve this, research chemists have teamed up with biologists,doctors, physicists, and mathematicians to respond as effectivelyas possible to the major challenges of keeping humans healthy.Technologies offered by AI have been used at all levels of research,from the development of new methods of synthesis to methods ofapplication leading to personalized medicine. Although suchapproaches are likely to lead to exciting developments in humanhealthcare, they are likely to come at a cost, and it is currentlyunclear whether all those who would benefit from them will beable to afford to do so.

Declaration of Competing Interest

The authors declare that they have no known competing financialinterests or personal relationships that could have appeared toinfluence the work reported in this paper.

Acknowledgments

Financial support is acknowledged from the Ins tut de Biologie duDe veloppement de Marseille (IBDM), Aix-Marseille-University andCNRS-UMR 7288. Drs Le Bivic and Kodjabachian are acknowledged for research facilities offered.


domain: sde sdv

text:
Alexandre Fruleux
email: alexandre.fruleux@nancy.inra.fr

Damien Bonal

Marie-Béatrice Bogeat-Triboulot

Fruleux Alexandre

Bonal Damien

Bogeat-Triboulot Marie-Béatrice

Effect of

come

Background and Aims

European beech (Fagus sylatica) is the most abundant deciduous tree species in Europe and suffers from strong intraspecific competition and drought (Packham et al, 2012, Journal of Ecology). Mixing functionally different tree species has been proposed as a way to increase wood productivity and forests resistance to drought. We investigated beech performances under drought and in competition with different species and we tested the following hypothesis: (1) Presence and identity of competitor impact performances of saplings, and (2) Water availability influences the nature and strength of interactions.

Conclusion and perspectives

Strong belowground competition occurred and reduced beech saplings growth. Yet, the developmental and morphological root traits showed weak responses to competition. What about about root functioning?

Mixing ecologically and functionally different species does not necessarily alleviate competition intensity even for species known to experience strong intraspecific competition. Drought decreased the importance of negative interactions between saplings and positive interaction occurred between beech and oak saplings. Tree mixtures seem to be particularly dependent on species identity.

Under expected dryer climates, natural regeneration of European beech may be advantageous for beech sapling survival and growth in mixture with oak. In contrast, favoring regeneration or developing plantations that include beech and pine young trees may be less advantageous.

Material and Methods

Beech saplings were grown alone (B), with a competitor, being a beech (BB), a sessile oak (BO) or a scots pine (BP). A drought treatment (20-25% of the relative extractable water) was applied on half of the pots and the other half was well-watered (55-80% of the REW). After one growing season, saplings were harvested and a range of above-and belowground growth and functional traits were measured.

Fig. 2. Leaf mass to area ratio (LMA) , leaf dry matter content (LDMC), leaf carbon isotope composition (δ 13 C), specific root hydraulic conductivity (Ks), specific root length in the 20-30 cm deep section (SRL20-30) and maximum root length of beech saplings in the well-watered (white) and the drought (black) treatment (mean ± SE). (Letters and asterisks as in Table 1.) Table 1. Total biomass, fine root-to-leaf ratio, relative growth rate in height (RGR H ) and diameter (RGR D ) of beech (mean ± SE). Different letters indicate significant difference between competition treatments within the well-watered and the drought treatments (p < 0.05). Asterisks indicate significant differences between water treatments within a competition treatment (* p < 0.05; ** p < 0.01, *** p < 0.001)

Fig. 1 .

 1 Fig. 1. Vertical distribution of fine roots of beech saplings expressed as root mass density (RMD) under well-watered (a) and drought (b) treatments (mean ± SE) in B (), BB(), BP () and BO ().

Acknowledgments: We thank Nathalie Aubry, Sandrine Breteau-Amores, Cyril Buré, David Cohen, Mathilde Colombat, Bruno Garnier, Christine Gehin, Maryline Harroué, Christian Hossann, Irène Hummel, Pierre Montpied and Julien Ruelle for their help and advices. This work is supported by the French National Research Agency (ANR) as part of the "Investissements d'Avenir" program (ANR-11-LABX-0002-01, Laboratory of Excellence ARBRE).

Effects of competition and water availability on above-and belowground growth and functional traits of European beech


JOINT WORK WITH Steve Lawford
email: steve.lawford@enac.fr

Yll Mehmeti

CLIQUES AND A NEW MEASURE OF CLUSTERING

INTRODUCTION

One widely used measure of clustering is the overall clustering coefficient, or "transitivity", on three nodes:

C(3) =
3 × number of triangles in the network G number of connected triples of nodes in G , which quantifies the relative frequency with which two neighbours of a node are themselves neighbours.

Many real-world networks display higher levels of clustering than if those networks were random [START_REF] Albert | Statistical mechanics of complex networks[END_REF][START_REF] Strogatz | Exploring complex networks[END_REF].

Clustering related to cooperative social behaviour and beneficial information and reputation transfer [START_REF] Jackson | Social and Economic Networks[END_REF].

Significant topological structures, on more than three nodes, can be found in real-world networks, and may perform precise specialized functions [START_REF] Milo | Network motifs: Simple building blocks of complex networks[END_REF].

A generalized clustering coefficient could provide new insight into such higher-order network structure.

OBJECTIVES

a) Propose a higher-order generalization of C(3), to any number of nodes, that nests standard clustering.

b) Develop and test a fast, practical, implementation based on analytic subgraph enumeration formulae.

HIGHER-ORDER CLUSTERING

We define the generalized clustering coefficient as:

C(b) = a(b) × number of b-cliques K b in G number of b-spanning trees in G , b ≥ 3, where Cayley's formula a(b) = b b-2 gives the number of spanning trees in K b , ensuring that 0 ≤ C(b) ≤ 1.
We use analytic subgraph enumeration formulae to count cliques and spanning trees [START_REF] Agasse-Duval | Subgraphs and motifs in a dynamic airline network[END_REF][START_REF] Lawford | Counting five-node subgraphs[END_REF]: a | is the count of subgraphs of "type" a on b nodes. For example, the 5-arrow subgraph count is:

C(4) = 16 |K 4 | |M (4) 11 |+|M (4
|M (5) 77 | = (i,j) ∈E k i -1 2 (k j -1) -2|M (4)
15 |, where edge (i, j) ∈ E is summed in both directions, k • is the node degree, and

|M ( 4
)
15 | is the tadpole count.

An alternative measure was developed in 2018 by Yin-Benson-Leskovec (YBL), using clique expansion [START_REF] Yin | Higher-order clustering in networks[END_REF]:

C b-1 = (b 2 -b) |K b | |L(b -1, 1)| , b ≥ 4,

THEORETICAL RESULTS ON RANDOM GRAPHS

(n, p) is E G [C b-1 ] -E G [C(b)] = p b-2 (1 -p (b-2)(b-3)/2
), with edge-formation probability p.

EMPIRICAL RESULTS ON REAL-WORLD NETWORKS

Data on eight small, sparse, U.S. domestic airline route networks, 1999Q1 to 2013Q4 (most are small-world).

Heterogeneity in clustering dynamics across carriers.

Small values of b capture much of the higher-order clustering present in these real-world networks. Some higher-order clustering left if control for lower-orders.

DISCUSSION AND FUTURE DIRECTIONS

a) Our work complements YBL: (theory) with C(b), we develop the other natural generalization of C(3) to more nodes, (computational) we derive analytic higher-order clustering formulae, while YBL use numerical methods, (empirical) we apply C(b) to airline networks, a classical example that is not covered by YBL. Our statistic avoids several undesirable properties of YBL's statistic, namely its invariance on some graphs with vanishing density, and its lack of applicability (when undefined) to even some connected graphs.

b) It is hard to derive analytic count formulae for subgraphs as b increases e.g. C(8) has 23 denominator terms. There may be a role for computer-assisted (or automated) theorem proving in working towards this goal. c) Airline carriers are increasingly developing small groups of highly-connected airports. The concept of a "hub" (or central) node in real-world networks can be extended to "multi-node hubs" (or central groups of nodes).

  where L(•, •) is the lollipop graph formed by joining a (b -1)-clique by a bridge to a single node. Critical difference between C(b) and C b-1 is in their definitions of the "relative frequency" of cliques.

Figure 1 :

 1 Figure 1: Theoretical difference in expectation for the Erd ős-Rényi random graph G(n, p) is E G [C b-1 ] -E G [C(b)] = p b-2 (1 -p (b-2)(b-3)/2), with edge-formation probability p.

Figure 2 :

 2 Figure 2: Simulated expected clustering E G [C(b)] from 250 replications of a small-world graph with n = 50 nodes, each of which has degree 14, and edge-rewiring probability p.

Figure 3 :

 3 Figure 3: Descriptive statistics for 2013Q4. The average path lengths (apl) for real-world networks are close to those from connected Erdős-Rényi random graphs (apl conn rand ). The clustering coefficients C(b) are typically higher than those from Erdős-Rényi random graphs (C(b) rand ). Connected % gives the percentage of connected realizations across 1,000 replications.


Line Van Den Berg
email: line.van-den-berg@inria.fr

Malvin Gattinger
email: malvin@w4eg.eu

Dealing with Unreliable Agents in Dynamic Gossip

Gossip describes the spread of information throughout a network of agents. It investigates how agents, each starting with a unique secret, can efficiently make peer-to-peer calls so that ultimately everyone knows all secrets. In Dynamic Gossip, agents share phone numbers in addition to secrets, which allows the network to grow at run-time. Most gossip protocols assume that all agents are reliable, but this is not given for many practical applications. We drop this assumption and study Dynamic Gossip with unreliable agents. The aim is then for agents to learn all secrets of the reliable agents and to identify the unreliable agents. We show that with unreliable agents classic results on Dynamic Gossip no longer hold. Specifically, the Learn New Secrets protocol is no longer characterised by the same class of graphs, so-called sun graphs. In addition, we show that unreliable agents that do not initiate communication are harder to identify than agents that do. This has paradoxical consequences for measures against unreliability, for example to combat the spread of fake news in social networks.

Introduction

The internet has led to great changes in the distribution of news. Recently, 'fake news' received attention, possibly having influenced the 2016 US presidential election [START_REF] Allcott | Social media and fake news in the 2016 election[END_REF]. Besides the challenge to identify fake news, a question is how to treat it: should false information be removed or is marking it as false sufficient?

Dynamic Gossip is a formal model how information can spread throughout a changing network of agents. It investigates how agents, each with a unique secret, decide, based on their own knowledge about the network, what calls to make so that ultimately everyone knows all the secrets. A gossip protocol can help agents to decide on a call sequence to perform. Examples from the literature are ANY ("call any agent"), CMO ("call me once") and LNS ("learn new secrets") [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]. In a dynamic setting, additional to secrets, agents share phone numbers, allowing the network to grow at run-time.

Traditionally these systems assume that everybody is reliable, but this assumption is not justified for many practical applications. Therefore, we adapt Dynamic Gossip to account for unreliable agents. Of course, the possibilities for agents to be unreliable are numerous: agents can lie about their own secret or about secrets of others, agents can have a memory of whom they have lied to or not, agents can always lie or with a certain probability, and agents can lie merely about secrets or also about phone numbers, etc. With any such form of unreliability, the aim of the reliable agents should still be to learn all the secrets (of the reliable agents) and, in addition, to identify the unreliable agents.

We show that, already with relatively simple unreliable agent a known result in Dynamic Gossip from [START_REF] Van Ditmarsch | Dynamic gossip[END_REF] breaks down. Specifically, the Learn New Secrets protocol is no longer characterised by sun graphs. This emphasises the need to discard the assumption that everyone is reliable for any practical application. In addition, we show that unreliable agents that do not initiate communication are harder to identify than those that do. This has seemingly paradoxical consequences for security measures taken against unreliable agents: blocking as a measure against false information has the adverse effect of securing the anonymity of the unreliable agents. New protocols are needed to properly cope with unreliable agents in Dynamic Gossip.

Our article is structured as follows. We give a short summary of related work in Section 2. In Section 3 we recall the definitions of Dynamic Gossip. We then define Unreliable Gossip and unreliable agents in Section 4 and 5, respectively. The new setting then motivates a new notion of success which we define and examine in Section 6. We conclude with future work ideas and a discussion the relevance of Unreliable Gossip for social networks in Section 7.

Related Work

Gossip has first been studied in combinatorics and graph-theory [START_REF] Hedetniemi | A survey of gossiping and broadcasting in communication networks[END_REF]. The classical question, also known as the "telephone problem" is: Given n agents who each start with a unique secret, how many phone calls are needed to spread all secrets? For n > 3 agents that all have the phone number of all other agents, 2n -4 calls are necessary and sufficient to make everyone learn all secrets [START_REF] Tijdeman | On a telephone problem[END_REF]. For networks in which not every agent has the phone number of all other agents, these numbers are naturally higher [START_REF] Harary | The communication problem on graphs and digraphs[END_REF]. Besides communication networks, gossip has also been used for the study of epidemics [START_REF] Eugster | Epidemic information dissemination in distributed systems[END_REF], power grids [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF] and neural networks [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF].

Most results on classical gossip assume a central and all-knowing scheduler deciding who should call whom and when. This is not realistic for practical applications in which agents have to decide autonomously what (communication) action to take. Hence, distributed gossip has been studied in which agents decide autonomously, on their own, whom to call using epistemic protocols [START_REF] Apt | Epistemic protocols for distributed gossiping[END_REF]3].

More recently, another assumption has been lifted, namely the assumption that the graph representing who can call whom is constant, i.e. agents have a static phone book or contact list. In dynamic gossip agents also exchange phone numbers, adding edges in the reachability graph [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]. This means that the network may grow at run-time. This is the setting which we use and extend here.

Most work on the classical telephone problem and on Dynamic Gossip assumes that all agents are reliable and follow the same protocol. However, gossip with unreliability has been studied extensively in other areas. One direction of research is about settings where communication links are unreliable, as studied in [START_REF] Shi | Randomized gossiping with unreliable communication: Dependent or independent node updates[END_REF] and [START_REF] Wang | Distributed parameter estimation in unreliable sensor networks via broadcast gossip algorithms[END_REF]. In contrast, here we assume that communication works perfectly but that agents are unreliable. Our setting is thus more comparable to having faulty or malicious agents, as in distributed storage [START_REF] Castro | Practical byzantine fault tolerance[END_REF] or consensus protocols [START_REF] Baird | The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance[END_REF].

Similar to our work is also the proposal of 'corrected gossip' in [START_REF] Hoefler | Corrected gossip algorithms for fast reliable broadcast on unreliable systems[END_REF]. The authors study failing nodes and define a gossip protocol which tries to reduce latency of the total group communication. A big difference to our setting is that their networks are static and no links are added at run-time.

Dynamic Gossip

We now give a short introduction to Dynamic Gossip, following [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]. We assume a finite set of agents, A. Initially, each agent knows only their own secret and some set of phone numbers including their own. If an agent a has the phone number of an agent b, then the phone call ab can take place. During a call, the two agents exchange secrets and phone numbers -including those they learned in previous calls. One might wonder what else agents learn in such a call, but for all results we discuss here higher-order knowledge such as "a knows that b knows the secret of c" is irrelevant, hence we will not model it and refer to [START_REF] Van Ditmarsch | Strengthening gossip protocols using protocol-dependent knowledge[END_REF]. We formally define gossip graphs, calls and sequences as follows.

Definition 1 (Gossip Graph). For any set A, let

I A := {(a, a) | a ∈ A}. A gossip graph is a triple G = (A, N, S) where A is a finite set of agents, N ⊆ A × A and S ⊆ A × A such that I A ⊆ N and I A ⊆ S. Given any G, let S a := {b ∈ A | (a, b) ∈ S} and N a := {b ∈ A | (a, b) ∈ N }. A graph is initial iff S = I A . A graph is complete iff S = A × A. An agent a is an expert iff S a = A. An agent a is terminal iff N a = {a}.
We say that "agent a knows the number of agent b" iff (a, b) ∈ N . Similarly, we say "agent a knows the secret of agent b" iff (a, b) ∈ S.

We now define calls ab, in which agent a and b share all their information. A call sequence σ is a sequence of calls. We use the following notation: is the empty sequence and σ; τ is the concatenation of two sequences σ and τ ; Moreover, σ τ denotes that σ is a prefix of τ . We say that call ab is possible on a graph G = (A, N, S) iff (a, b) ∈ N . The call sequence is possible on any graph, and a call sequence ab; σ is possible on G iff the call ab is possible on G and σ is possible on G ab . If a call sequence σ is possible on a graph G, then G σ is defined by: G := G and G ab;σ := (G ab ) σ .

It is an easy exercise to show by induction on σ that "if a knows the secret of b, then a also knows the number of b" is an invariant when making calls.

Lemma 1. For any initial graph G = (A, N, S) and any call sequence σ that is possible on G, we have in the resulting graph G σ = (A, N σ , S σ ) that S σ ⊆ N σ .

A protocol for Dynamic Gossip is a rule how agents decide whom they should call. The goal of a gossip protocol is to reach a complete graph, where everybody knows all secrets. Moreover, good protocols will use fewer calls and avoid superfluous or redundant calls. Here we will focus on the LNS protocol from [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]. For a general definition of protocols in a formal language, see [START_REF] Van Ditmarsch | Strengthening gossip protocols using protocol-dependent knowledge[END_REF]. We now define when a protocol is successful on a graph. Intuitively, this means all possible executions of the protocol lead to a complete graph.

Definition 5 (Success). Let P G bet the set of all call sequences possible on G and permitted by protocol P . We also call such call sequences P -permitted.

Let a graph G = (A, N, S) and a protocol P be given. A finite call sequence σ ∈ P G is successful iff G σ is complete. A sequence σ is P -maximal on G iff σ is P -permitted on G and there is no call P -permitted on G σ , i.e. no call ab can be added to σ such that σ; ab is still P -permitted.

-P is strongly successful on G if all P -maximal σ ∈ P G are successful.

-P is weakly successful on G if there is a σ ∈ P G that is successful.

-P is unsuccessful on G if there is no σ ∈ P G that is successful.
Given a certain class G of networks (graphs) and a protocol P , we can ask the question: is P (strongly, weakly, un-) successful on G. That is, does P lead to a complete network? This question, the gossip problem, is used to characterise networks both by their graph-theoretical properties and by the protocols that are (strongly, weakly, un-) successful on them.

It is easy to see that on any graph that consists of disconnected parts no protocol is successful. Hence, graphs need to be weakly connected to allow any of the protocols to be successful [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]. Definition 6. A graph G = (A, N, S) is weakly connected iff for all agents a, b ∈ A there is a undirected N -path between a and b. We say that G is strongly connected iff for all agents a, b ∈ A there is an N -path from a to b.

A graph G = (A, N, S) is a sun graph iff N is strongly connected on s(G), where s(G) is the result of removing all terminal agents from G.

Informally, one can think of sun graphs as 'almost' strongly connected graphs.

Example 2. The following graph is a sun graph: if we remove the only terminal agent a, then we obtain a strongly connected graph (consisting of b and c).

a b c
Theorem 1 (Theorem 13 in [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]). Suppose G is an initial gossip graph. Then LNS is strongly successful on G iff G is a sun graph.

Considering the notion of weak success instead of strong success, the authors of [START_REF] Van Ditmarsch | Dynamic gossip[END_REF] also show the following result.

Theorem 2 (Theorem 33 in [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]). Suppose G is an initial weakly-connected gossip graph. Then LNS is weakly successful on G iff G is neither a bush nor a double bush.

Combining the two theorems we can see that LNS is weakly but not strongly successful exactly on those graphs which are neither bush nor double bush and not sun graphs. A smallest example of such a graph is the following.

Example 3. The following graph is not a bush, not a double bush and not a sun graph. Note that the only difference to Example 2 is that we now have an edge

a → b instead of b → a. a b c
The five maximal LN S call sequences here are the following, of which the first three are successful and the other two are unsuccessful.

ab; ac; bc successful ab; bc; ac successful ab; cb; ac successful bc; ab unsuccessful cb; ab unsuccessful

Unreliable Gossip

It is easy to define reliable agents: they do exactly what they are expected to do. In particular, reliable agents communicate truthfully about their own secret, about secrets of others and share all the phone numbers they have. However, when unreliability is allowed, there are numerous different options. There may be noise on the communication channel causing the communication between agents to fail; agents may (intentionally or unintentionally) follow a different protocol; agents may actively spread lies, either about their own secret, about other agents' secrets or both; agents may sabotage connections between other agents; unreliable agents may form coalitions to manipulate the network; the degree of unreliability may evolve over time, via peer pressure or other mechanisms; unreliable agents might have a memory of whom they have lied to; etc. This gives rise to many different types of unreliable behaviour.

In this article we only consider a basic form of unreliability: unreliability in the form of unintended random memoryless noise. A real-world example for this kind of unreliability could be a network of sensors that communicate with each other, but where one or more of the sensors are faulty. We therefore assume:

-Agents all follow the same protocol; -Unreliable agents only lie about their own secret; -Connections are not sabotaged; -Unreliability does not evolve; -Unreliable agents do not remember to whom they lied; -Agents consider all new information as true until proven otherwise.

In the standard model of (dynamic) gossip, an agent either knows a secret or not. For settings with unreliable agents we need more: agents can also have obtained a wrong secret and thus have a false belief.

To model this, we let secrets be bits and replace the former set of secrets S a with two sets: X a for agents of which a received secret 1, and Y a for agents of which a received secret 0. When an agent is in either X a or Y a , then a considers that agent to be reliable. But when an agent is both in X a and Y a , then a will consider that agent unreliable.

Definition 7 (UG Graph).

A gossip graph with unreliable agents, short Unreliable Gossip graph or UG graph, is a quadruple G = (A, R, N, S) where A is a finite set of agents, R ⊆ A is the set of reliable agents, N ⊆ A × A is the network relation and S : A → P(A) × P(A) assigns to each agent a ∈ A a pair (X a , Y a ). We say that a has a positive secret of b iff b ∈ X a , that a has a negative secret of b iff b ∈ Y a , and that a knows that b is unreliable iff b ∈ X a ∩ Y a .

We also write S a for X a ∪ Y a , which intuitively is the set of all agents of which a knows any secret. When all agents are reliable (R = A), a UG graph can be identified with a gossip graph by setting S a := X a ∪ Y a for each a ∈ A.

Definition 8 (Initial UG Graph). A UG graph G = (A, R, N, S) is initial iff for all a ∈ A we have X a ∪ Y a = {a}.
In a regular call ab, where both agents speak the truth, information is shared as follows. This means that both agents update their contact lists (N a and N b , respectively) and update their sets X, Y by taking unions. In particular, if before the call agent a had a positive and secret agent b had a negative secret of some agent c, then after the call both a and b know that agent c is unreliable. Definition 9 (UG Call between reliable agents). Let G = (A, R, N, S) be a UG Graph and let a, b ∈ A such that (a, b) ∈ N . The call ab maps G to G ab = (A, R, N ab , S ab ) where N ab is as in Definition 2 and

S ab c := (X a ∪ X b , Y a ∪ Y b ) if c ∈ {a, b} (X c , Y c ) otherwise
Analogous to Definition 3 we write G σ for the result of executing a sequence of calls σ on a UG graph G.

Note that in the definition of a call, agents are naive: they consider all new information completely trustworthy and update their knowledge accordingly. In other settings where unreliable agents may lie about secrets of other agents, one can imagine that agents would adopt a more sceptic approach or prefer first hand information (an agent sharing their own secret) over second hand information (and agent sharing a secret of another agent).

Unreliable Agents

We now formally define unreliable agents that satisfy the constraints given in Section 4. An unreliable agent may report a wrong value of their own secret in a call. We do not assume any rules about when and how often an unreliable agent reports the wrong value of their secret, only that the probability to lie is non-zero (for when the probability is zero, it is a reliable agent).

In addition to the call ab from Definition 9, we now define three calls Ab, aB or AB in which respectively a, b or both agents report the wrong value of their own secret. That is, the agents denoted with a capital letter are lying about their own secrets in this call. For example, in a call Ab all secrets are shared normally, apart from agent a's secret. More specifically, if a ∈ X a then the new set of secrets for b is not given by merging X a with X b , and Y a with Y b , but by merging X a \ {a} with X b , and Y a ∪ {a} with Y b . The lying of agent a is thus represented by acting as if her own secret was in Y a and not in X a (or vice versa).

Note that Ab, Ba and AB can only occur if, respectively, a, b or both agents do not belong to the set of reliable agents R. On the other hand, note that in the call Ab agent b does not necessarily belong to R, but might still be unreliable and just happen to speak the truth in this call.

S Ab a := (X a ∪ X b , Y a ∪ Y b ) (1)
S Ab b :=      ((X a \ {a}) ∪ X b , Y a ∪ {a} ∪ Y b ) if a ∈ X a \ Y a (X a ∪ {a} ∪ X b , (Y a \ {a}) ∪ Y b ) if a ∈ Y a \ X a (X a ∪ X b , Y a ∪ Y b ) if a ∈ X a ∩ Y a (2
S AB a :=      (X a ∪ (X b \ {b}), Y a ∪ Y b ∪ {b}) if b ∈ X b \ Y b (X a ∪ X b ∪ {b}, Y a ∪ (Y b \ {b})) if b ∈ Y b \ X b (X a ∪ X b , Y a ∪ Y b ) if b ∈ X b ∩ Y b (3)
S AB b :=      ((X a \ {a}) ∪ X b , Y a ∪ {a} ∪ Y b ) if a ∈ X a \ Y a (X a ∪ {a} ∪ X b , (Y a \ {a}) ∪ Y b ) if a ∈ Y a \ X a (X a ∪ X b , Y a ∪ Y b ) if a ∈ X a ∩ Y a (4)
and S AB c := (X c , Y c ) for all other agents c / ∈ {a, b}.

Analogous to Definition 3 we write G σ for the result of executing a sequence of reliable or unreliable calls σ on a UG graph G.

We stress that an unreliable agent will not always report the wrong value. In fact, then it would be the same as a reliable agent with the opposite secret value, and the other agents would never find out that the unreliable agent is lying.

To illustrate the different types of calls, consider the following example.

(X a , Y a ) (X b , Y b ) (X c , Y c ) (X d , Y d ) ({a}, ∅) ({b}, ∅) ({c}, ∅) ({d}, ∅) AB → ({a}, {b}) ({b}, {a}) ({c}, ∅) ({d}, ∅) ac → ({a, c}, {b}) ({b}, {a}) ({a, c}, {b}) ({d}, ∅) Ad → ({a, c, d}, {b}) ({b}, {a}) ({a, c}, {b}) ({c, d}, {a, b}) cd → ({a, c, d}, {b}) ({b}, {a}) ({a, c, d}, {a, b}) ({a, c, d}, {a, b}) bc → ({a, c, d}, {b}) ({a, b, c, d}, {a, b}) ({a, b, c, d}, {a, b}) ({a, c, d}, {a, b})
In particular, after the fourth call cd the agents c and d learn that a is unreliable. However, even after the last call, agent d does not know this about b and no more call is permitted according to the LNS protocol.

Interestingly, a consequence of Definition 10 is that agents may find out themselves that they are unreliable. This is what happens after the call bc in Example 4 for agent b: after this call, b ∈ X b ∩ Y b , hence she considers herself unreliable. But this also informs her that she is uncovered by agent c, who learns the same information about the unreliability of b. If now another agent e enters the network and the call be (or Be) takes place, e will be informed by agent b of her own unreliability. This results from Definition 10: the last clauses of equations 2, 3 and 4 enforce that, in a call between a and b, whenever a is uncovered, i.e. a ∈ X a ∩Y a , the sets X a and X b and Y a and Y b are merged without adjustments. Hence afterwards a ∈ X b ∩ Y b , i.e. b learns that a is unreliable.

In our setting where unreliability is unintended random memoryless noise this definition is not problematic, but in fact can help the network to perform better. In a network of sensors for instance, the unreliable sensor could then give a signal that it needs to be fixed.

If agents are intentionally unreliable, it might be more realistic to change their behavior once they learn they are uncovered. To model this we could easily change the last clauses of equations 2, 3 and 4 in Definition 10 to

(X a ∪ X b , Y a \ {a} ∪ Y b ) (2') (X a ∪ X b , Y a \ {a} ∪ Y b ) (3') (X a ∪ X b , Y a ∪ Y b \ {b}) (4')
respectively. Similarly, we could do the same but remove a (resp. b) from X a (resp. X b ) instead of Y a (resp. Y b ), but the effect would be analogous. In that situation, an uncovered agent will only continue to communicate one value of her secret (here X a ). In other words, once uncovered she will change her behavior.

A simple example of an unreliable agent is an alternating bluffer that "lies" in every second call. It provides a first approach to random unintended noise, but it is deterministic and thus easier to simulate and reason about. We note that agent a in Example 4 behaves as an alternating bluffer.

In our model there is no "curing" or "going back" from unreliability. Once an agent is unreliable and consequently (possibly) uncovered, there is no way for agents to change their behavior. This is sufficient to introduce unreliability into Dynamic Gossip and explore whether the known results continue to hold. But of course, for practical applications, it would be desirable to enable agents to be cured. For example for the application of this framework to the spread of diseases [START_REF] Eugster | Epidemic information dissemination in distributed systems[END_REF]. An important question is then how agents can convince others that they have improved their behavior, from unreliable to reliable.

Unreliable Success

We now define what it means to be successful in Unreliable Gossip. Completeness on UG graphs is reached when all agents know all secrets, now in the sense that each agent knows at least one secret of each other agent. We note that this is equivalent to completeness on gossip graphs as defined in Definition 1 with S a = X a ∪ Y a . Definition 11. A UG graph G = (A, R, N, S) is complete iff for all agents a ∈ A we have X a ∪ Y a = A.

However, for Unreliable Gossip this kind of completeness and success according to Definition 5 is not a useful goal. Instead, the aim of the reliable agents should be to reach completeness among themselves and to identify all unreliable agents. We now define reliable completeness formally and argue that it is a more intuitive goal in the setting of Unreliable Gossip than (mere) completeness.

Definition 12. A UG graph G = (A, R, N, S) is reliably complete iff for all a ∈ R we have (i) X a ∪ Y a \ (X a ∩ Y a ) = R, and (ii) X a ∩ Y a = A \ R.
That is, a graph is reliably complete iff each reliable agent (i) knows the secrets of all reliable agents and (ii) knows for all unreliable agents that they are unreliable. We note that in the presence of (ii) the condition (i) is equivalent to X a ∪ Y a = A. To make it easier to refer to the second condition we also say that an agent a identifies the unreliable agents iff X a ∩ Y a = A \ R.

Note that reliably complete does not imply complete, because in a reliably complete graph the unreliable agents do not have to know all secrets. Reliable agents should learn all secrets and identify all unreliable agents, but we do not care at all about what unreliable agents learn. Also vice versa, completeness does not imply reliable completeness, because completeness says nothing about knowing which other agents are unreliable.

In order to compare completeness on unreliable networks to completeness on normal networks, we define reliable counter-graphs and reliable subgraphs. A sanity check shows that indeed both G * and G| R are gossip graphs. Definition 13 allows us to rephrase the definition of reliable completeness: a graph G is reliably complete if and only if the reliable subgraph of G is complete and all reliable agents identify the unreliable agents.

To conclude this section, we define success for Unreliable Gossip, both for the original notion of completeness and reliable completeness. Definition 14. Suppose we have a UG graph G and a call sequence σ which can be executed on G. We say that σ is successful on G iff G σ is complete and we say that σ is reliably successful on G iff G σ is reliably complete.

A protocol is (reliably) weakly / strongly / un-successful on a graph G iff all / some / no sequences permitted by the protocol and executable on G are (reliably) successful on G.

LNS is not strongly reliably successful on sun graphs

Here we show that, already with a small amount of unreliability, for example in the form of the alternating bluffer, a known result about LNS [START_REF] Van Ditmarsch | Dynamic gossip[END_REF] fails to hold. Specifically, we show that on UG graphs that are sun graphs with only terminal unreliable agents, LNS fails to identify the unreliable agents in the sense that it is not reliably successful as defined in the previous section. Before the general result we give an example where the classification of LNS fails to hold.

Example 5. Consider again the sun graph from Example 2 and suppose a is unreliable. Now consider the sequence bc; ba; cA. This is an LNS sequence resulting in a complete graph. However, if a is an alternating bluffer, then b will learn one value of the secret a and c the other. Formally, in the resulting graph G bc;ba;cA we have a ∈ X c \ Y c and a ∈ Y b \ X b . Unfortunately, LNS allows no further calls. Hence b and c may no longer communicate and will not notice that a is unreliable.

Consider ba; Ac; bc. This is also an LNS sequence which can be executed on the graph above. But in this case b and c talk to each other after having learned different values from a and will thus find out that a is unreliable. Formally, in the resulting graph G ba;Ac;bc we have a ∈

(X b ∩ Y b ) and a ∈ (Z c ∩ Y c ).
Hence, whether b and c find out that a is unreliable depends on the sequence.

Example 5 already suffices to show that LNS is not reliably successful on all sun graphs when we have unreliable agents. However, we now prove something slightly stronger, namely that for all graphs of a similar shape there is a maximal sequence which is not successful.

Theorem 3. Consider any initial UG graph with at least one unreliable agent. If all unreliable agents are terminal then LNS is not reliably strongly successful.

Intuitively, Theorem 3 holds because there are call sequences in which the unreliable agents are called too late, so that the reliable agents cannot verify the secrets of these unreliable agents with each other. This is the case in Example 5: the reliable agents b and c first learn each others' secrets before calling the unreliable agent a. But then b and c cannot call each other again in LNS and hence cannot verify the secret of a with each other. That is why they fail to identify c as unreliable.

We now first prove a lemma.

Lemma 2. Suppose G = (A, R, N, S) is an initial UG graph with at least one unreliable agent. Moreover, suppose that all unreliable agents in G are terminal.

Then for any LNS-permitted call sequence σ we have: if there is a prefix τ σ such that G τ | R is complete but G τ is not reliably complete, then also G σ is not reliably complete and thus σ is not reliably successful on G.

Lemma 2 states that any LNS sequence cannot become reliably successful any more as soon as it reaches a complete reliable subgraph. Intuitively, once the reliable subgraph becomes complete, the reliable agents can no longer call each other to compare secrets they received from the unreliable agents.

Proof (of Lemma 2). Let G be an initial UG graph with at least one unreliable agent and where all unreliable agents are terminal. Let σ be an LNS-permitted call sequence with a prefix τ σ such that G τ | R is complete. Then ∀r ∈ R : X τ r ∪ Y τ r ⊇ R and therefore also ∀r ∈ R : X σ r ∪ Y σ r ⊇ R because no contradictory information can be learned about reliable agents. Now note that after the call sequence τ no more calls from an unreliable agent to a reliable agent can take place: just after τ the unreliable agents are still terminal, and in all later calls where they learn the number of a reliable agent they will also learn the secret of that same agent (because G τ | R is complete). Moreover, we can ignore calls between unreliable agents because they do not affect reliable completeness.

Hence, let ab be the last call to take place in σ from a reliable agent a to an unreliable agent b. Let σ \ ab denote the sequence without this last call. That means before the call a knew no secret of b,

i.e. b / ∈ X σ\ab a ∪ Y σ\ab a
. But then, because a will not be involved in any later calls, we have that b ∈ X σ a ∪ Y σ a . Hence agent b will not be identified by agent a and σ is not reliably successful on G.

Proof (of Theorem 3). Let G = (A, R, N, S) be an initial UG graph that is a sun graph where all unreliable agents are terminal. Because all unreliable agents are terminal, the reliable subgraph G| R of G must be a sun graph too. By Theorem 1, any maximal LNS-permitted call sequence τ consisting of calls ab with a, b ∈ R will complete G| R , i.e. G τ | R is complete. Now by Lemma 2, any LNS-permitted call sequence σ extending τ will fail to identify all unreliable agents and hence fail to reliably complete the network. Thus, we cannot extend the sun graph characterisation of LNS to Unreliable Gossip. This already holds for a small amount of unreliability: one terminal alternating bluffer. Of course, this is because we now also demand that reliable agents identify the unreliable agents. If we only care about completeness in the original sense, then LNS is still strongly successful on UG graphs with respect to the reliable agents. In particular, even if unreliable agents are involved in earlier calls (i.e. if there is no τ as in the proof above), the reliable subgraph will still be completed.

LNS is not weakly reliably successful on non-bushes

We now look at the second characterization result about LNS that was shown in [START_REF] Van Ditmarsch | Dynamic gossip[END_REF]. For this, consider again Example 3, and suppose that agent c is unreliable. We also saw in the example that the only successful LNS call sequences end are those where C is involved in both last calls. Hence, if now c behaves as an alternating bluffer then a and b will learn different values of the secret of c. Because LNS allows no more calls it is impossible for a and b to learn that c is unreliable.

TODO: show the results after the five sequences with alternating C

Blocking unreliable agents hides and helps them

How can we "repair" LNS to deal with unreliable agents? Intuitively, blocking unreliable agents seems a good measure against the spread of false information in networks because it would prevent unreliable agents from spreading their false information. This would mean that, when an unreliable agent performs a call to another agent, her call will be rejected. By blocking unreliable agents, their communicative power is restricted: they will not be able to initiate calls -whenever they do, they are rejected. Of course, conceptually, there is a difference between blocked agents and agents that are not able to initiate communication. The latter may rather occur whenever their communicating device is broken. Yet, mathematically, these situations are analogous: in both situations, the unreliable agents cannot successfully make a call to another agent. Therefore we evaluate the following protocol that limits the unreliable agents in their ability to make calls to discuss whether blocking unreliable agents is indeed a good measure.

Definition 15 (Protocol LNSR). A call ab is LNSR-permitted iff (a, b) ∈ N , a ∈ R and (a, b) ∈ S.
But, against the intuition, the protocol LNSR does not only prevent false information from spreading, it might also prevent unreliable agents from being detected by the reliable agents. Specifically, we prove that unreliable agents that are not allowed to initiate any form of communication are harder to identify than unreliable agents that are. In other words, unreliability can be easier detected when it is spread more. Therefore the restriction to disable, via blocking, the unreliable agents from initiating calls is not desirable. Theorem 4. LNSR is a proper strengthening of LNS in the following sense:

(i) For any UG graph G we have: If LNSR is (reliably) weakly successful on G, then also LNS is (reliably) weakly successful on G. (ii) There is a UG graph G where LNSR is not reliably weakly unsuccessful, but where LNS is reliably weakly successful.

Proof. (i) Note that any LNSR-permitted call sequence σ is also LNS-permitted.

If LNSR is (reliably) weakly successful on some UG graph G, then there is an LNSR-permitted call sequence σ such that G σ is (reliably) complete. But then σ is also LNS-permitted, and hence LNS is also (reliably) weakly successful on G. Then the following are all the LNS-permitted call sequences on G. For each sequence we list four variants, depending on where c is lying. It is crucial in part (ii) of Theorem 4 that reliable agents are the last to communicate in order to identify the unreliable agent as such. Thus the success of the protocol is dependent on the call sequence, and in particular on the position of calls between reliable agents: they need to verify the secrets of the unreliable agents. But, agents do not know which agents are the unreliable agents (this is the goal of the protocol), hence they do not know which secrets need to be verified nor with whom to verify this. This problem of verification is similar to the Byzantine Generals Problem [START_REF] Lamport | The byzantine generals problem[END_REF] developed to describe a situation in which agents must agree on a joint strategy to avoid catastrophic failure of the system, but where some of the agents or some are unreliable. In a simple form, multiple generals are threatened by a common enemy and they each have to decide whether to attack or to retreat with a preferred outcome of a coordinated attack or coordinated retreat. A good solution to the problem is an algorithm that can both guarantee that all reliable generals decide upon the same plan and that a small number of unreliable generals cannot cause the reliable generals to adopt a bad strategy. Such solutions have been studied in the literature under the name of Byzantine Fault Tolerance, starting with [START_REF] Castro | Practical byzantine fault tolerance[END_REF] and more recently including [START_REF] Baird | The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance[END_REF].

Theorem 4 illustrates that there are networks on which unreliable agents remain unidentified when they are not allowed to initiate calls, but can be identified when they do initiate calls. This has direct consequences for the security measure to block unreliable agents and raises questions about their effectiveness for real-life applications and gossip-like settings. For example, a faulty sensor should not be shut down immediately but continue to communicate such that it will be identified as faulty by a larger number of other sensors. As another example, fake news articles shared in social networks will be easier to uncover and identify if they are not removed or blocked, but instead marked as fake and continued to be actively shared.

Formally, we define the ideas of blocking and deleting as follows. Deleting means that an agent removes those agents she knows to be unreliable from her own phone book. Blocking means that, in addition to deleting, the agent removes her own number from the phone book of agents she knows to be unreliable. Definition 16 (Delete and Block). Let G = (A, R, N, S) be a UG graph and let a ∈ A. The delete action λ a maps G to G λa = (A, R, N λa , S) and the block action µ a maps G to G µa = (A, R, N µa , S), which are defined by

N λa c := N c if c = a N c \ (X c ∩ Y c ) if c = a N µa c =      N c if c = a and c / ∈ X a ∩ Y a N c \ {a} if c = a and c ∈ X a ∩ Y a N c \ (X c ∩ Y c ) if c = a
As Theorem 4 shows, blocking unreliable agents, though seemingly a good approach to prevent the spread of false information, comes at a cost. Blocking unreliable agents seems analogous to restricting their communicative power because the effects are the same: unreliable agents will not be able to initiate communication. This is exactly what has been shown to help them remain unidentified.

However, in contrast to LNSR, let us now assume that agents only block other agents once they have identified them as unreliable. They will then be able to forward the information that agents are unreliable to others. The following example illustrates how this can prevent the unwanted effect of hiding unreliable agents. Suppose that the reliable agents block the unreliable agents as soon as they identify them. Consider the LNS-permitted call sequence ab; cB; ac; cd. After the subsequence ab; cB; ac the agents a and c will identify agent b as unreliable and this will then be communicated to agent d in the final call cd. Hence also agent d will block b after this and the whole sequence is reliably successful.

A disadvantage of both LNSR and blocking known-to-be-unreliable agents is that it might exclude other reliable agents "behind" unreliable ones. Whenever there is a reliable agent a that is only able to communicate with an unreliable agent, blocking this unreliable agent also prevents agent a to contact the rest of the network. She is therefore excluded from the rest of the network. Consider the following example.

Example 7. Let G = (A, R, N, S) be the network drawn below where R = A \ {b} and A \ {a, b} forms a complete cluster, i.e. ∀r ∈ A \ {a, b}: X r ∪ Y r = A \ {b}. Suppose further that all agents in the cluster consider b unreliable, i.e. ∀r ∈ A \ {a, b} : b ∈ X r ∩ Y r , and have no information about a, that b has all the information about A \ {a} and that a only has the phone number of b, as drawn below. Then blocking agent b effectively blocks agent a and the network will not be reliably completed. We argue that this is a realistic scenario for LNS: the call ab might come too late in the call sequence. Then, because the other reliable agents block agent b, agent a is also blocked indirectly.

A \ {a, b} b a

Discussion and Conclusion

We extended the formal model of Dynamic Gossip from [START_REF] Van Ditmarsch | Dynamic gossip[END_REF] to include unreliable agents. To better capture success in Dynamic Gossip with unreliable agents we defined the notion of reliable success: all reliable agents should learn all secrets and they should identify the unreliable agents. We have then shown that, already with a single unreliable agent, we cannot extend the results about the success of the LNS protocol: LNS is successful in the old sense, but not reliably successful on sun graphs with unreliable terminal agents. This shows that the assumption that everybody is reliable is crucial for the success of LNS and that LNS should be adapted for practical applications where agents might fail.

We then examined a way to counter the spread of false information, namely to restrict communication of unreliable agents. It turns out that unreliable information that is not actively spread is harder to identify than unreliable information that is actively spread. This has seemingly paradoxical consequences for measures against unreliable agents: blocking can have a contrary effect and help unreliable agents to remain unidentified. Thus, there is a pay-off between identifying and containing false information.

Our framework and in particular the alternating bluffer are of course simplistic and there are many ways to extend this work: agents can also be unreliable or (with intent) lie about other agents' secrets, about phone numbers, about their own knowledge, etc. Yet, we see this work as a starting point for the discussion of reliability and unreliability in dynamic gossip and its real life applications. We thus end this article with the following open questions.

-What is the class of unreliable gossip graphs characterized by LNS? -Is there any limitation on the position of unreliable agents in this class? -Is there an LNS weakening or strengthening (in the sense of [START_REF] Van Ditmarsch | Strengthening gossip protocols using protocol-dependent knowledge[END_REF]) that performs better in situations with unreliability?

Further research will show how Dynamic Gossip protocols can be adapted to deal with other forms of unreliability. Finally, we want to stress that this work is not purely theoretical: social media and the spread of fake news can be seen as an instance of gossip with unreliable agents. Some social networks already use hybrid strategies where false information is not blocked but just marked as such.

Example 1 .

 1 Suppose agent a knows the number of b, and agents b and c know each other's number and no other numbers are known. We draw this situation below. Note that we use dashed arrows for the binary relation of knowing the number of someone (N ). Now if a calls b then a and b learn each other's secret, which we draw with solid arrows (S). We also add another dashed arrow: in the call ab agent a also learns the number of c.

Definition 2 (

 2 Call). Suppose G = (A, N, S), a, b ∈ A and (a, b) ∈ N . The call ab maps G to G ab := (A, N ab , S ab ) where N ab c := N a ∪ N b if c ∈ {a, b} N c otherwise and S ab c := S a ∪ S b if c ∈ {a, b} S c otherwise Definition 3 (Call sequences).

Definition 4 (

 4 LNS Protocol). A call ab is LNS-permitted iff (a, b) ∈ N and (a, b) ∈ S.

Definition 10 (

 10 UG Call with unreliable agents). Let G = (A, R, N, S) be a UG Graph and let a, b ∈ A such that (a, b) ∈ N . We define four calls. ab ab ab The call ab maps G to G ab = (A, R, N ab , S ab ) from Definition 2. Ab Ab Ab Suppose a ∈ R. The call Ab maps G to G Ab = (A, R, N Ab , S Ab ) where N Ab := N ab from Definition 2, and for agents a and b:

  ) and S Ab c := (X c , Y c ) for all other agents c / ∈ {a, b}. aB aB aB Vice versa, suppose b ∈ R. The call aB maps G to G aB which is defined symmetrically, i.e. the same as G Ba . AB AB AB Finally, suppose a ∈ R and b ∈ R. The call AB maps G to G AB = (A, R, N AB , S AB ) where N AB := N ab from Definition 2 and for a and b:

Example 4 .

 4 Consider the UG graph G = (A, R, N, S) where A = {a, b, c, d}, R = {c, d}, N = A × A and S x = (X x , Y x ) = ({x}, ∅) for each x ∈ A. The (LNS-permitted) call sequence AB; ac; Ad; cd; bc changes G as follows:

Definition 13 .

 13 Let G = (A, R, N, S) be a UG Graph. Then we define its reliable counter-graph G * := (A, N, S * ) where S * a := (X a ∪ Y a ) \ (X a ∩ Y a ). And we define its reliable subgraph G| R := (A| R , N | R , S| R ) where A| R := R, N | R := N ∩(R×R) and (S| R ) a := (X a ∪ Y a ) ∩ R.

  (ii) Consider the UG graph G = (A, R, N, S) below with A = {a, b, c}, R = {a, b}, N = {(b, a), (b, c)} and S x = ({x}, ∅) for all x ∈ A. a b c

Example 6 .

 6 Consider the following network of four agents with one unreliable agent, agent b, i.e. A = {a, b, c, d} and R = {a, c, d}:

  Only the call sequences under 1 and 2 are LNSR-permitted. But only the sequence marked with * reliably completes the network: first the agents a and b need to learn different values from agent c and after that they should communicate with each other to learn that c is unreliable. None of the other sequences reliably complete the network and in particular no LNSR-permitted call sequence reliably completes G. Hence LN S is reliably weakly successful on G, but LN SR is not.

	1. ba; ac; bc or ba; aC; bc or ba; ac; bC or ba; aC; bC
	2. ba; bc; ac or ba; bC; ac or ba; bc; aC or ba; bC; aC
	3. bc; ca; ba or bC; ca; ba ( * ) or bc; Ca; ba or bC; Ca; ba
	4. bc; ba; ca or bC; ba; ca or bc; ba; Ca or bC; ba; Ca

Acknowledgements. This work is based on the master's thesis of the first author [5], supervised by Jan van Eijck. We thank Hans van Ditmarsch and the anonymous reviewers at the DaLí workshop for helpful feedback.