{"id":331,"date":"2019-03-08T17:25:56","date_gmt":"2019-03-08T16:25:56","guid":{"rendered":"https:\/\/wp-systeme.lip6.fr\/estate\/?page_id=331"},"modified":"2019-03-27T16:22:02","modified_gmt":"2019-03-27T15:22:02","slug":"work","status":"publish","type":"page","link":"https:\/\/wp-systeme.lip6.fr\/estate\/work\/","title":{"rendered":"Workshop ANR DESCARTES\/ESTATE — Abstracts"},"content":{"rendered":"

in conjonction with Workshop Complexit\u00e9 et Algorithmes (GT CoA\/GDR CNRS IM)<\/a><\/p>\n

Roscoff Apr. 1st–2nd, 2019<\/h3>\n

Details \/ Abstracts of Talks<\/h3>\n
    \n
  1. <\/a>Byzantine Gathering in Polynomial Time<\/em>
    \nS\u00e9bastien Bouchard<\/span>, with Yoann Dieudonn\u00e9 and Anissa Lamani<\/p>\n
    \n

    Gathering a group of mobile agents is a fundamental task in the field of distributed and mobile systems. This can be made drastically more difficult to achieve when some agents are subject to faults, especially the Byzantine ones that are known as being the worst faults to handle. In this paper we study, from a deterministic point of view, the task of Byzantine gathering in a network modeled as a graph. In other words, despite the presence of Byzantine agents, all the other (good) agents, starting from {possibly} different nodes and applying the same deterministic algorithm, have to meet at the same node in finite time and stop moving. An adversary chooses the initial nodes of the agents (the number of agents may be larger than the number of nodes) and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label. The agents move in synchronous rounds and can communicate with each other only when located at the same node. Within the team, f of the agents are Byzantine. A Byzantine agent acts in an unpredictable and arbitrary way. For example, it can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. Besides its label, which corresponds to a local knowledge, an agent is assigned some global knowledge denoted by GK that is common to all agents. In literature, the Byzantine gathering problem has been analyzed in arbitrary n-node graphs by considering the scenario when GK=(n,f) and the scenario when GK=f. In the first (resp. second) scenario, it has been shown that the minimum number of good agents guaranteeing deterministic gathering of all of them is f+1 (resp. f+2). However, for both these scenarios, all the existing deterministic algorithms, whether or not they are optimal in terms of required number of good agents, have the major disadvantage of having a time complexity that is exponential in n and L, where L is the value of the largest label belonging to a good agent. In this paper, we seek to design a deterministic solution for Byzantine gathering that makes a concession on the proportion of Byzantine agents within the team, but that offers a significantly lower complexity. We also seek to use a global knowledge whose the length of the binary representation (that we also call size) is small. In this respect, assuming that the agents are in a strong team i.e., a team in which the number of good agents is at least some prescribed value that is quadratic in f, we give positive and negative results. On the positive side, we show an algorithm that solves Byzantine gathering with all strong teams in all graphs of size at most n, for any integers n and f, in a time polynomial in n and the length |l_{min}| of the binary representation of the smallest label of a good agent. The algorithm works using a global knowledge of size O(log log log n), which is of optimal order of magnitude in our context to reach a time complexity that is polynomial in n and |l_{min}|. Indeed, on the negative side, we show that there is no deterministic algorithm solving Byzantine gathering with all strong teams, in all graphs of size at most n, in a time polynomial in n and |l_{min}| and using a global knowledge of size o(log log log n). <\/p>\n<\/div>\n

    \n<\/li>\n
  2. <\/a>Deterministic Treasure Hunt in the Plane with Angular Hints<\/em>
    \nS\u00e9bastien Bouchard<\/span>, with Yoann Dieudonn\u00e9, Andrzej Pelc, and Franck Petit<\/p>\n
    \n

    A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most D>0 from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than 2 pi whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent’s trajectory. It is well known that without any hint the optimal (worst case) cost is Theta(D^2). We show that if all angles given as hints are at most pi, then the cost can be lowered to O(D), which is optimal. If all angles are at most beta, where beta0. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than 2 pi, then we show that cost Theta(D^2) cannot be beaten.<\/p>\n<\/div>\n

    \n<\/li>\n
  3. <\/a>Gracefully Degrading Gathering in Dynamic Rings<\/em>
    \nMarjorie Bournat<\/span>, with Swan Dubois and Franck Petit<\/p>\n
    \n

    Gracefully degrading algorithms [Biely et al., TCS 2018] are designed to circumvent impossibility results in dynamic systems by adapting themselves to the dynamics. Indeed, such an algorithm solves a given problem under some dynamics and, moreover, guarantees that a weaker (but related) problem is solved under a higher dynamics under which the original problem is impossible to solve. The underlying intuition is to solve the problem whenever possible but to provide some kind of quality of service if the dynamics become (unpredictably) higher.In this paper, we apply for the first time this approach to robot networks. We focus on the fundamental problem of gathering a squad of autonomous robots on an unknown location of a dynamic ring. In this goal, we introduce a set of weaker variants of this problem. Motivated by a set of impossibility results related to the dynamics of the ring, we propose a gracefully degrading gathering algorithm.<\/p>\n<\/div>\n

    \n<\/li>\n
  4. <\/a>Acyclic Strategy for Silent Self-Stabilization in Spanning Forests<\/em>
    \nSt\u00e9phane Devismes<\/span>, with Karine Altisen and Ana\u00efs Durand<\/p>\n
    \n

    We formalize design patterns, commonly used in self-stabilization, to obtain general statements regarding both correctness and time complexity. Precisely, we study a class of algorithms devoted to networks endowed with a sense of direction describing a spanning forest whose characterization is a simple (i.e., quasi-syntactic) condition. We show that any algorithm of this class is (1) silent and self-stabilizing under the distributed unfair daemon, and (2) has a stabilization time polynomial in moves and asymptotically optimal in rounds. To illustrate the versatility of our method, we review several works where our results apply. <\/p>\n<\/div>\n

    \n<\/li>\n
  5. <\/a>Contention-related crash failures<\/em>
    \nAna\u00efs Durand<\/span>, with Michel Raynal and Gadi Taubenfeld<\/p>\n
    \n

    A new notion of process failure explicitly related to contention has recently been introduced by Gadi Taubenfeld (NETYS 2018). More precisely, given a predefined contention threshold \u03bb, this notion considers the execution in which process crashes are restricted to occur only when process contention is smaller than or equal to \u03bb. If crashes occur after contention bypassed \u03bb, there are no correctness guarantees. It was shown that, when \u03bb = n-1, consensus can be solved in an n-process asynchronous read\/write system despite the crash of one process, thereby circumventing the well-known FLP impossibility result.
    \nIn this talk, I will present k-set agreement and renaming algorithms that are resilient to two types of process crash failures: \u00ab\u00a0\u03bb-constrained\u00a0\u00bb crash failures (as previously defined) and classical crash failures.<\/p>\n<\/div>\n

    \n<\/li>\n
  6. <\/a>Byzantine Reliable Broadcast in Dynamic Networks<\/em>
    \nGiovanni Farina<\/span>, with Silvia Bonomi and S\u00e9bastien Tixeuil<\/p>\n
    \n<\/li>\n
  7. <\/a>Local Verification of Global Proofs<\/em>
    \nLaurent Feuilloley<\/span>, with Juho Irvonen<\/p>\n
    \n

    In distributed decision, a classic mechanism is to label every node of the network with a proof, to certify the current configuration. These proofs are local in the sense that every node is given its own proof. In this talk I will present our results on global proofs, that is, proofs that every node can access.<\/p>\n<\/div>\n

    \n<\/li>\n
  8. <\/a>Soyez Efficace, Rembobinez<\/em>
    \nColette Johnen<\/span>, with St\u00e9phane Devismes<\/p>\n
    \n

    Nous proposons un algorithme, appel\u00e9 SDR, qui r\u00e9initialise de mani\u00e8re auto-stabilisante et totalement distribu\u00e9e un r\u00e9seau anonyme, lorsque c’est n\u00e9cessaire, c’est \u00e0 dire que chaque processus, d\u00e9tectant localement une anomalie, peut d\u00e9clencher une r\u00e9initialisation.
    \nSDR est coop\u00e9ratif au sens o\u00f9 il coordonne les r\u00e9initialisations concurrentes afin de gagner en efficacit\u00e9. Nous utilisons SDR pour rendre auto-stabilisant des algorithmes distribu\u00e9s. Notre approche permet de r\u00e9soudre efficacement \u00e0 la fois les probl\u00e8mes statiques et dynamiques, comme le montrent les deux exemples d’algorithme utilisant SDR que nous proposons.
    \nEn effet, nous avons, tout d’abord, con\u00e7u un algorithme\u00a0auto-stabilisant silencieux calculant une (f, g)-alliance 1-minimale dans les r\u00e9seaux identifi\u00e9s.\u00a0 Aucun algorithme auto-stabilisant ne r\u00e9solvait auparavant ce probl\u00e8me sans aucune restriction sur f et g.
    \nNous avons ensuite propos\u00e9 un algorithme auto-stabilisant d’unisson. Ce dernier stabilise en O(n) rondes et O(Dn^2)\u00a0 mouvements (D est le diam\u00e8tre et n est le nombre de processus dans le r\u00e9seau). Par rapport aux algorithmes pr\u00e9c\u00e9dents, notre algorithme\u00a0am\u00e9liore le temps de stabilisation en mouvements sans p\u00e9nalit\u00e9 sur\u00a0 le temps de stabilisation en rondes, ni l’espace m\u00e9moire utilis\u00e9.<\/p>\n<\/div>\n

    \n<\/li>\n
  9. <\/a>On restricted-use objects and beyond<\/em>
    \nAlessia Milani<\/span>, with Corentin Travers, Danny Hendler, and Ahad Mirza Baig<\/p>\n
    \n<\/li>\n
  10. <\/a>Decidability of distributed complexity of locally checkable problems on paths<\/em>
    \nMickael Rabie<\/span>, with Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, and Jukka Suomela<\/p>\n
    \n

    More than 20 years ago, Naor and Stockmeyer introduced the Locally Checkable problems (LCL). On a bounded degree graph, nodes need to find an output such as each node can check locally that it is coherent. If no node disagree, then the output is good. Such problems can be about coloring, maximal independent set… In their original paper, they prove that such problems on paths and cycles have 3 possible complexities: constant, log* and linear. Moreover, they prove that, given the acceptable outputs, the complexity can be decided in polynomial time. However, they only considered the case where the nodes do not have inputs.
    \nIn this talk, I will first introduce those results, and then present recent results about what happens when the nodes are given some input. In the latter case, the complexities remain the same, and it is still decidable to figure it out. However, it is more complicated, as in it at least PSPACE hard to decide it.<\/p>\n<\/div>\n

    \n<\/li>\n
  11. <\/a>Anonymous Shared-Memory Computability<\/em>
    \nSergio Rajsbaum<\/span>, with Carole Delporte, Hugues Fauconnier, and Nayuta Yanagisawa<\/p>\n
    \n

    I describe some of the history and our results on computability in
    \nthe anonymous shared-memory model, and its relation to
    \nthe combinatorial topology approach to distributed computability.<\/p>\n<\/div>\n

    \n<\/li>\n
  12. <\/a>Plus faible d\u00e9tecteur de d\u00e9faillances pour l\u2019exclusion mutuelle en m\u00e9moire partag\u00e9e<\/em>
    \nMichel Raynal<\/span>, with Carole Delporte and Hugues Fauconnier<\/p>\n
    \n

    Failure detectors are devices that provides the processes
    \nwith information on failures. They were introduced to enrich
    \nasynchronous systems so that it becomes possible to solve problems (or
    \nimplement concurrent objects) that are otherwise impossible to solve
    \nin pure asynchronous systems where processes are prone to crash
    \nfailures. The most famous failure detector (which is called
    \n\u00ab\u00a0eventual leader\u00a0\u00bb and denoted $\\Omega$) is the weakest failure
    \ndetector which allows consensus to be solved in $n$-process
    \nasynchronous systems where up to $t=n-1$ processes may crash in the
    \nread\/write communication model, and up to $t<n\/2$ processes may crash
    \nin the message-passing communication model.
    \nWhen looking at the mutual exclusion problem (or equivalently the
    \nconstruction of a lock object), while the weakest failure detectors
    \nare known for both asynchronous message-passing systems and read\/write
    \nsystems in which up to t<n processes may crash, for the
    \nstarvation-freedom progress condition, it is not yet known for weaker
    \ndeadlock-freedom progress condition in read\/write systems. This paper
    \nextends the previous results, namely, it presents the weakest failure
    \ndetector that allows mutual exclusion to be solved in asynchronous
    \n$n$-process read\/write systems where any number of processes may
    \ncrash, whathever the progress condition (deadlock-freedom or
    \nstarvation-freedom).<\/p>\n<\/div>\n

    \n<\/li>\n
  13. <\/a>Formal proofs on Mobile Robots Swarms<\/em>
    \nLionel Rieg<\/span>, with Thibault Balabonski, Pierre Courtieu, S\u00e9bastien Tixeuil, and Xavier Urbain<\/p>\n
    \n

    Mobile robot networks emerged in the past few years as a promising distributed computing model ensuring more resiliency. Existing work in the literature typically ensures the correctness of mobile robot protocols via ad hoc handwritten proofs, which are both cumbersome and error-prone. Formal methods approaches, such as model-checking, program synthesis, and proof assistants, try to overcome these limitations.
    \nIn this talk, I will present our work on the third approach : the Pactole library for the Coq proof assistant. We designed it to accommodate all existing model variants, so that a unified framework may express all results and proofs, allowing to compare them. In particular, it can express both correctness and impossibility results. If proving requires expertise, specifying a protocol with Pactole is rather easy, thanks to familiar mathematical notations. Time permitting, I will illustrate this on several case studies.<\/p>\n<\/div>\n

    \n<\/li>\n<\/ol>\n

     <\/p>\n

    \u00a9 \"\"  <\/a><\/pre>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    in conjonction with Workshop Complexit\u00e9 et Algorithmes (GT CoA\/GDR CNRS IM) Roscoff Apr. 1st–2nd, 2019 Details \/ Abstracts of Talks Byzantine Gathering in Polynomial Time S\u00e9bastien Bouchard, with Yoann Dieudonn\u00e9 and Anissa Lamani Gathering a group of mobile agents is a fundamental task in the field of distributed and mobile systems. This can be made … Continuer la lecture de Workshop ANR DESCARTES\/ESTATE — Abstracts<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":37,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-331","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/pages\/331","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/users\/37"}],"replies":[{"embeddable":true,"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/comments?post=331"}],"version-history":[{"count":49,"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/pages\/331\/revisions"}],"predecessor-version":[{"id":393,"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/pages\/331\/revisions\/393"}],"wp:attachment":[{"href":"https:\/\/wp-systeme.lip6.fr\/estate\/wp-json\/wp\/v2\/media?parent=331"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}