<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of hal-01135398</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-25T17:23:50+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">The Random Bit Complexity of Mobile Robots Scattering</title>
            <author role="aut">
              <persName>
                <forename type="first">Quentin</forename>
                <surname>Bramas</surname>
              </persName>
              <email type="md5">513a44d2d4cda00e73b8c1408273179c</email>
              <email type="domain">unistra.fr</email>
              <idno type="idhal" notation="string">quentin-bramas</idno>
              <idno type="idhal" notation="numeric">2043</idno>
              <idno type="halauthorid" notation="string">19110-2043</idno>
              <idno type="IDREF">https://www.idref.fr/197916139</idno>
              <idno type="ORCID">https://orcid.org/0000-0003-0612-5616</idno>
              <affiliation ref="#struct-389034"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Sébastien</forename>
                <surname>Tixeuil</surname>
              </persName>
              <email type="md5">46fb30964edb44afa6b5deecf5f673eb</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">tixeuil</idno>
              <idno type="idhal" notation="numeric">9380</idno>
              <idno type="halauthorid" notation="string">5657-9380</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-0948-7172</idno>
              <idno type="IDREF">https://www.idref.fr/121380661</idno>
              <affiliation ref="#struct-56663"/>
              <affiliation ref="#struct-160294"/>
              <affiliation ref="#struct-389034"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Sébastien</forename>
                <surname>Tixeuil</surname>
              </persName>
              <email type="md5">46fb30964edb44afa6b5deecf5f673eb</email>
              <email type="domain">lip6.fr</email>
            </editor>
            <funder>SMARTBAN</funder>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2015-03-25 12:19:50</date>
              <date type="whenModified">2026-01-19 16:46:18</date>
              <date type="whenReleased">2015-03-25 12:19:50</date>
              <date type="whenProduced">2015-06-29</date>
              <ref type="externalLink" target="http://arxiv.org/pdf/1309.6603"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="103492">
                <persName>
                  <forename>Sébastien</forename>
                  <surname>Tixeuil</surname>
                </persName>
                <email type="md5">46fb30964edb44afa6b5deecf5f673eb</email>
                <email type="domain">lip6.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">hal-01135398</idno>
            <idno type="halUri">https://hal.sorbonne-universite.fr/hal-01135398</idno>
            <idno type="halBibtex">bramas:hal-01135398</idno>
            <idno type="halRefHtml">&lt;i&gt;Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015&lt;/i&gt;, Jun 2015, Athènes, Greece. pp.210-224, &lt;a target="_blank" href="https://dx.doi.org/10.1007/978-3-319-19662-6_15"&gt;&amp;#x27E8;10.1007/978-3-319-19662-6_15&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015, Jun 2015, Athènes, Greece. pp.210-224, &amp;#x27E8;10.1007/978-3-319-19662-6_15&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="UPMC" corresp="SORBONNE-UNIVERSITE">Université Pierre et Marie Curie</idno>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LIP6" corresp="SORBONNE-UNIVERSITE">Laboratoire d'Informatique de Paris 6</idno>
            <idno type="stamp" n="UPMC_POLE_1" corresp="UPMC">UPMC Pôle 1</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="SU-SCI" corresp="SORBONNE-UNIVERSITE">Sciences - Sorbonne Université</idno>
            <idno type="stamp" n="INSTITUTS-TELECOM">composantes instituts telecom </idno>
            <idno type="stamp" n="SU-TI">Sorbonne Université - Texte Intégral</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="invited" n="0">No</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
            <note type="proceedings" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">The Random Bit Complexity of Mobile Robots Scattering</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Quentin</forename>
                    <surname>Bramas</surname>
                  </persName>
                  <email type="md5">513a44d2d4cda00e73b8c1408273179c</email>
                  <email type="domain">unistra.fr</email>
                  <idno type="idhal" notation="string">quentin-bramas</idno>
                  <idno type="idhal" notation="numeric">2043</idno>
                  <idno type="halauthorid" notation="string">19110-2043</idno>
                  <idno type="IDREF">https://www.idref.fr/197916139</idno>
                  <idno type="ORCID">https://orcid.org/0000-0003-0612-5616</idno>
                  <affiliation ref="#struct-389034"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Sébastien</forename>
                    <surname>Tixeuil</surname>
                  </persName>
                  <email type="md5">46fb30964edb44afa6b5deecf5f673eb</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">tixeuil</idno>
                  <idno type="idhal" notation="numeric">9380</idno>
                  <idno type="halauthorid" notation="string">5657-9380</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-0948-7172</idno>
                  <idno type="IDREF">https://www.idref.fr/121380661</idno>
                  <affiliation ref="#struct-56663"/>
                  <affiliation ref="#struct-160294"/>
                  <affiliation ref="#struct-389034"/>
                </author>
              </analytic>
              <monogr>
                <meeting>
                  <title>Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015</title>
                  <date type="start">2015-06-29</date>
                  <date type="end">2015-07-01</date>
                  <settlement>Athènes</settlement>
                  <country key="GR">Greece</country>
                </meeting>
                <imprint>
                  <publisher>Springer</publisher>
                  <biblScope unit="serie">Lecture Notes in Computer Science</biblScope>
                  <biblScope unit="volume">9143</biblScope>
                  <biblScope unit="pp">210-224</biblScope>
                  <date type="datePub">2015-06</date>
                </imprint>
              </monogr>
              <idno type="arxiv">1309.6603</idno>
              <idno type="doi">10.1007/978-3-319-19662-6_15</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <classCode scheme="halDomain" n="info.info-dc">Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]</classCode>
              <classCode scheme="halDomain" n="info.info-cg">Computer Science [cs]/Computational Geometry [cs.CG]</classCode>
              <classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode>
              <classCode scheme="halDomain" n="info.info-iu">Computer Science [cs]/Ubiquitous Computing</classCode>
              <classCode scheme="halDomain" n="info.info-rb">Computer Science [cs]/Robotics [cs.RO]</classCode>
              <classCode scheme="halDomain" n="info.info-ni">Computer Science [cs]/Networking and Internet Architecture [cs.NI]</classCode>
              <classCode scheme="halTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halOldTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halTreeTypology" n="COMM">Conference papers</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>We consider the problem of scattering $n$ robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering.We first prove that $n \log n$ random bits are necessary to scatter $n$ robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem.Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in $o(\log \log n)$ rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific  protocol of this family that is random bit optimal ($n \log n$ random bits are used) and time optimal ($\log \log n$ rounds are used). This improves the time complexity of previous results in the same setting by a $\log n$ factor.Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes its time complexity gap with and without strong multiplicity detection (that is, $O(1)$ time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach it as needed otherwise).</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-389034" status="OLD">
          <orgName>Networks and Performance Analysis</orgName>
          <orgName type="acronym">NPA</orgName>
          <date type="start">2004-01-01</date>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-233" type="direct"/>
            <relation active="#struct-93591" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-56663" status="VALID">
          <idno type="IdRef">03442945X</idno>
          <idno type="ISNI">0000000119314817</idno>
          <idno type="ROR">https://ror.org/055khg266</idno>
          <idno type="Wikidata">Q1665127</idno>
          <orgName>Institut universitaire de France</orgName>
          <orgName type="acronym">IUF</orgName>
          <desc>
            <address>
              <addrLine>Maison des Universités 103 Boulevard Saint-Michel 75005 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://iuf.amue.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-301855" type="direct"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-160294" status="OLD">
          <orgName>Laboratory of Information, Network and Communication Sciences</orgName>
          <orgName type="acronym">LINCS</orgName>
          <desc>
            <address>
              <addrLine>23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lincs.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-93591" type="direct"/>
            <relation active="#struct-300009" type="direct"/>
            <relation active="#struct-302102" type="direct"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-233" status="OLD">
          <idno type="RNSR">199712651U</idno>
          <idno type="ROR">https://ror.org/05krcen59</idno>
          <orgName>Laboratoire d'Informatique de Paris 6</orgName>
          <orgName type="acronym">LIP6</orgName>
          <date type="start">1997-01-01</date>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lip6.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-93591" type="direct"/>
            <relation name="UMR7606" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-93591" status="OLD">
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Université Pierre et Marie Curie - Paris 6</orgName>
          <orgName type="acronym">UPMC</orgName>
          <date type="end">2017-12-31</date>
          <desc>
            <address>
              <addrLine>4 place Jussieu - 75005 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.upmc.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-301855" status="VALID">
          <orgName>Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche</orgName>
          <orgName type="acronym">M.E.N.E.S.R.</orgName>
          <desc>
            <address>
              <addrLine>1 rue Descartes - 75231 Paris cedex 05</addrLine>
              <country key="FR"/>
            </address>
          </desc>
        </org>
        <org type="institution" xml:id="struct-300009" status="VALID">
          <idno type="ROR">https://ror.org/02kvxyf05</idno>
          <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
          <orgName type="acronym">Inria</orgName>
          <desc>
            <address>
              <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.inria.fr/en/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-302102" status="VALID">
          <idno type="IdRef">192427156</idno>
          <idno type="ISNI">000000012202567X</idno>
          <idno type="ROR">https://ror.org/025vp2923</idno>
          <idno type="Wikidata">Q27962533</idno>
          <orgName>Institut Mines-Télécom [Paris]</orgName>
          <orgName type="acronym">IMT</orgName>
          <date type="start">2012-03-01</date>
          <desc>
            <address>
              <addrLine>19 Place Marguerite Perey, 91120 Palaiseau</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.imt.fr/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>