Listing 1 - 10 of 13 | << page >> |
Sort by
|
Choose an application
Distributed Computing by Mobile Entities is concerned with the study of the computational and complexity issues arising in systems of decentralized computational entities operating in a spatial universe Encompassing and modeling a large variety of application environments and systems, from robotic swarms to networks of mobile sensors, from software mobile agents in communication networks to crawlers and viruses on the web, the theoretical research in this area intersects distributed computing with the fields of computational geometry (especially for continuous spaces), control theory, graph theory and combinatorics (especially for discrete spaces). The research focus is on determining what tasks can be performed by the entities, under what conditions, and at what cost. In particular, the central question is to determine what minimal hypotheses allow a given problem to be solved. This book is based on the lectures and tutorial presented at the research meeting on “Moving and Computing" (mac) held at La Maddalena Island in June 2017. Greatly expanded, revised and updated, each of the lectures forms an individual Chapter. Together, they provide a map of the current knowledge about the boundaries of distributed computing by mobile entities.
Data transmission systems. --- Software engineering. --- Computer network architectures. --- Computer Communication Networks. --- Robotics. --- Operating systems (Computers). --- Input/Output and Data Communications. --- Special Purpose and Application-Based Systems. --- Computer System Implementation. --- Operating Systems. --- Architectures, Computer network --- Network architectures, Computer --- Computer architecture --- Computer software engineering --- Engineering --- Data communication systems --- Transmission of data --- Digital communications --- Electronic data processing --- Electronic systems --- Information theory --- Telecommunication systems --- Computer operating systems --- Computers --- Disk operating systems --- Systems software --- Automation --- Machine theory --- Operating systems --- Distributed processing. --- Input-output equipment (Computers). --- Special purpose computers. --- Architecture, Computer. --- Computer communication systems. --- Communication systems, Computer --- Computer communication systems --- Data networks, Computer --- ECNs (Electronic communication networks) --- Electronic communication networks --- Networks, Computer --- Teleprocessing networks --- Data transmission systems --- Information networks --- Telecommunication --- Cyberinfrastructure --- Network computers --- Architecture, Computer --- Special purpose computers --- Computer hardware --- Computer I/O equipment --- Electronic analog computers --- Electronic digital computers --- Hardware, Computer --- I/O equipment (Computers) --- Input equipment (Computers) --- Input-output equipment (Computers) --- Output equipment (Computers) --- Computer systems --- Distributed processing --- Input-output equipment --- Computer input-output equipment. --- Computers, Special purpose. --- Computer systems. --- Computer networks. --- ADP systems (Computer systems) --- Computing systems --- Systems, Computer
Choose an application
jointly with the GRAAL meeting. We thank the Management Committee of GRAAL, and especially their past and present Chairs Xavier Munoz and Arie Koster, for supporting the idea of this joint event and for their generous support. June 2007 Giuseppe Prencipe Shmuel Zaks Conference Organization Steering Committee Paola Flocchini Andrzej Pelc Pierre Fraigniaud, Chair David Peleg Leszek Gasieniec Giuseppe Prencipe Lefteris Kirousis Michel Raynal Rastislav Kr´ alovi?c Nicola Santoro Evangelos Kranakis Paul Spirakis Danny Krizanc Shmuel Zaks Bernard Mans Program Committee Christoph Ambuhl ¨ Giuseppe Prencipe, Co-chair Ioannis Caragiannis Guido Proietti Lenka Carr-Motyckova Andrzej Proskurowski Bogdan Chlebus Geppino Pucci Thomas Erlebach Tomasz Radzik Rastislav Kr´ alovi?c Sergio Rajsbaum Evangelos Kranakis Michel Raynal Jan van Leeuwen Tami Tamir Euripides Markou Savio Tse Toshimitsu Masuzawa Peter Widmayer Yves M´etivier Shmuel Zaks, Co-chair Local Organization Vincenzo Gervasi, Dipartimento di Informatica, Universitad ` i Pisa Sponsoring Institutions Universit`adi Pisa EU COST 293 action (GRAAL) VIII Organization External Reviewers Ittai Abraham Dariusz Kowalski Hagit Attiya Richard Kral ´ ovi?c Alberto Bertoldo Danny Krizanc Vittorio Bil` o Qin Lv Davide Bil` o Francesca Martelli Maria Blesa Russell Martin Anat Bremler-Barr Valia Mitsou Marco Bressan Gianpiero Monaco Alfred Bruckstein Mohamed Mosbah Keren Censor Luca Moscardelli Milind Dawande Alfredo Navarra Xavier Defago Francesco Nidito Stefan Dobrev Fukuhito Ooshita Frederick Ducatelle Aris Pagourtzis Toby Ehrenkrantz Evi Papaioannou Michael Elkin Dana Pardubska Angelo Fanelli Susanna Pelagatti Arthur Farley Andrzej Pelc Laura Feeney David Peleg Michele Flammini Enoch Peserico Paola Flocchini Andrea Pietracaprina Luca Forlizzi Katerina Potika Leszek Gasieniec
Complex analysis --- Discrete mathematics --- Computer science --- Computer architecture. Operating systems --- discrete wiskunde --- complexe analyse (wiskunde) --- informatica --- database management --- programmatielogica --- algoritmen --- computernetwerken
Choose an application
Choose an application
Complex analysis --- Discrete mathematics --- Computer science --- Artificial intelligence. Robotics. Simulation. Graphics --- discrete wiskunde --- complexe analyse (wiskunde) --- grafische vormgeving --- informatica --- database management --- programmatielogica --- KI (kunstmatige intelligentie)
Choose an application
Complex analysis --- Discrete mathematics --- Computer science --- Computer architecture. Operating systems --- discrete wiskunde --- complexe analyse (wiskunde) --- informatica --- database management --- programmatielogica --- algoritmen --- computernetwerken
Choose an application
The study of what can be computed by a team of autonomous mobile robots, originally started in robotics and AI, has become increasingly popular in theoretical computer science (especially in distributed computing), where it is now an integral part of the investigations on computability by mobile entities. The robots are identical computational entities located and able to move in a spatial universe; they operate without explicit communication and are usually unable to remember the past; they are extremely simple, with limited resources, and individually quite weak. However, collectively the robots are capable of performing complex tasks, and form a system with desirable fault-tolerant and self-stabilizing properties. The research has been concerned with the computational aspects of such systems. In particular, the focus has been on the minimal capabilities that the robots should have in order to solve a problem. This book focuses on the recent algorithmic results in the field of distributed computing by oblivious mobile robots (unable to remember the past). After introducing the computational model with its nuances, we focus on basic coordination problems: pattern formation, gathering, scattering, leader election, as well as on dynamic tasks such as flocking. For each of these problems, we provide a snapshot of the state of the art, reviewing the existing algorithmic results. In doing so, we outline solution techniques, and we analyze the impact of the different assumptions on the robots' computability power. Table of Contents: Introduction / Computational Models / Gathering and Convergence / Pattern Formation / Scatterings and Coverings / Flocking / Other Directions.
Choose an application
Electronic data processing --- Distributed operating systems (Computers) --- Traitement réparti --- Systèmes d'exploitation répartis --- Distributed processing --- Congresses. --- Congrès --- Computer Science --- Telecommunications --- Engineering & Applied Sciences --- Electrical & Computer Engineering --- Information Technology --- Computer Science (Hardware & Networks) --- Computer science. --- Computer communication systems. --- Special purpose computers. --- Architecture, Computer. --- Computer programming. --- Software engineering. --- Operating systems (Computers). --- Computer Science. --- Computer System Implementation. --- Computer Communication Networks. --- Software Engineering. --- Programming Techniques. --- Operating Systems. --- Special Purpose and Application-Based Systems. --- Computer operating systems --- Computers --- Disk operating systems --- Systems software --- Computer software engineering --- Engineering --- Architecture, Computer --- Special purpose computers --- Electronic computer programming --- Electronic digital computers --- Programming (Electronic computers) --- Coding theory --- Communication systems, Computer --- Computer communication systems --- Data networks, Computer --- ECNs (Electronic communication networks) --- Electronic communication networks --- Networks, Computer --- Teleprocessing networks --- Data transmission systems --- Digital communications --- Electronic systems --- Information networks --- Telecommunication --- Cyberinfrastructure --- Network computers --- Informatics --- Science --- Operating systems --- Programming --- Operating systems (Computers) --- Computer network architectures. --- Architectures, Computer network --- Network architectures, Computer --- Computer architecture --- Electronic data processing - Distributed processing - Congresses. --- Distributed operating systems (Computers) - Congresses. --- Computer systems. --- Computer networks. --- Computers, Special purpose. --- ADP systems (Computer systems) --- Computing systems --- Systems, Computer
Choose an application
Computer algorithms --- Graph theory --- Algorithmes --- Théorie des graphes --- Congresses. --- Congrès --- Computer algorithms -- Congresses. --- Electronic books. -- local. --- Graph theory -- Congresses. --- Computer Science --- Engineering & Applied Sciences --- Computer science. --- Software engineering. --- Data structures (Computer science). --- Computers. --- Algorithms. --- Computer science --- Computer graphics. --- Computer Science. --- Software Engineering/Programming and Operating Systems. --- Algorithm Analysis and Problem Complexity. --- Data Structures. --- Computation by Abstract Devices. --- Discrete Mathematics in Computer Science. --- Computer Graphics. --- Mathematics. --- Automatic drafting --- Graphic data processing --- Graphics, Computer --- Computer art --- Graphic arts --- Electronic data processing --- Engineering graphics --- Image processing --- Computer mathematics --- Discrete mathematics --- Algorism --- Algebra --- Arithmetic --- Automatic computers --- Automatic data processors --- Computer hardware --- Computing machines (Computers) --- Electronic brains --- Electronic calculating-machines --- Electronic computers --- Hardware, Computer --- Computer systems --- Cybernetics --- Machine theory --- Calculators --- Cyberspace --- Information structures (Computer science) --- Structures, Data (Computer science) --- Structures, Information (Computer science) --- File organization (Computer science) --- Abstract data types (Computer science) --- Computer software engineering --- Engineering --- Informatics --- Science --- Digital techniques --- Mathematics --- Foundations --- Computer software. --- Data structures (Computer scienc. --- Computational complexity. --- Complexity, Computational --- Software, Computer --- Computer science—Mathematics. --- Artificial intelligence—Data processing. --- Discrete mathematics. --- Software Engineering. --- Data Science. --- Theory of Computation. --- Discrete mathematical structures --- Mathematical structures, Discrete --- Structures, Discrete mathematical --- Numerical analysis
Choose an application
The9thInternationalConferenceonPrinciplesofDistributedSystems(OPODIS 2005) was held during December 12-14, 2005 in Pisa, Italy. It continued a t- dition of successful conferences with friendly and pleasant atmospheres. Pre- ous OPODIS conferences were held in Chantilly (1997), Amiens (1998), Hanoi (1999), Paris (2000), Mexico (2001), Reims (2002), La Martinique (2003), and Grenoble (2004). TheOPODISconferenceconstitutesanopenforumfor theexchangeofsta- of-the-art knowledge on distributed computing and systems among researchers from around the world. Following the tradition of the previous events, the 2005 program was composed of high-quality contributed papers by experts of int- national caliber in this scienti?c area. Papers were sought soliciting original research contributions to the theory, speci?cations, design and implementation of distributed systems, including: - communication and synchronization protocols - distributed algorithms, multiprocessor algorithms - distributed collaborative environments - embedded systems - fault-tolerance, reliability, availability - grid and cluster computing - location- and context-aware systems - mobile computing and networks - peer-to-peer systems, overlay networks - performance analysis of distributed algorithms and systems - real-time systems - security issues in distributed computing and systems - sensor networks - speci?cation veri?cation and testing of distributed systems This year, a particular focus was placed on real-time systems and wireless networks. In response to the call for papers for OPODIS 2005, 109 papers in the above areas were submitted from 30 countries from around the world. Each paper was reviewed by at least three reviewers, and judged according to scienti?c and p- sentationquality,originalityandrelevancetotheconferencetopics. TheProgram Committee selected 30 papers for presentation at the conference.
Programming --- Computer architecture. Operating systems --- Computer. Automation --- informatica --- programmeren (informatica) --- software engineering --- OS (operating system) --- computernetwerken
Choose an application
ThisvolumecontainsthepaperspresentedattheFourthInternationalConf- enceonFunwithAlgorithms(FUN2007),heldJune3-5,2007inthebeautiful TuscaniancoastaltownofCastiglioncello,Italy. FUN is a three-yearly conference dedicated to the use, design, and ana- sisofalgorithmsanddatastructures,focusingonresultsthatprovideamusing, witty but nonetheless originaland scienti?cally profound contributions to the area. ThepreviousthreemeetingswereheldonElbaIsland,Italy,andspecial issuesofthejournals Theoretical Computer Science (FUN1998), Discrete - plied Mathematics(FUN2001),andTheory of Computing Systems(FUN2004) featureextendedversionsofselectedpapersfromthethreeconferenceprograms. InresponsetotheCallforPapersforFUN2007,wereceived41submissions from 25 countries. Each submission was reviewed by at least three Program Committeemembers. Attheendoftheselectionprocess,thecommitteedecided toaccept20papers. TheprogramalsoincludesthreeinvitedtalksbyGiuseppe Di Battista (U. Rome III, Italy), Nicola Santoro (Carleton U. , Canada), and LucaTrevisan(U. C. Berkeley,USA). WewishtothankalltheauthorswhosubmittedtheirpaperstoFUN2007 andthuscontributedtothecreationofahigh-qualityprogramandentertaining meeting,aswellasthecolleagueswhoacceptedtoserveontheProgramC- mitteeandprovidedinvaluablehelpwiththereviewingprocess. Wealsowishto thanktheexternalreviewers(listedonthefollowingpages)includingthosewho completedurgentreviewsduringthediscussionphase. Papersubmission,sel- tion,andgenerationoftheproceedingswasgreatlyeasedbytheuseofthepubl- domainEasyChair ConferenceSystem(http://www. easychair. org). Wewish tothanktheEasyChaircreatorsandmaintainersfortheirsel?esscommittment tothescienti?ccommunity. Finally,specialthanksgotoVincenzoGervasi,whose constanthelpanddedicationwascrucialinmakingFUN2007asuccessfulevent. April2007 PierluigiCrescenzi GiuseppePrencipe GeppinoPucci Conference Organization Program Chairs PierluigiCrescenzi(UniversityofFirenze,Italy) GeppinoPucci(UniversityofPadua,Italy) Program Committee NancyAmato(TexasA&MUniversity,USA) NinaAmenta(UniversityofCaliforniaatDavis,USA) MarcellaAnselmo(UniversityofSalerno,Italy) AnnaBernasconi(UniversityofPisa,Italy) PaoloBoldi(UniversityofMilano,Italy) IreneFinocchi(UniversityofRoma LaSapienza ,Italy) LuisaGargano(UniversityofSalerno,Italy) SandyIrani(UniversityofCaliforniaatIrvine,USA) ChristosKaklamanis(UniversityofPatras,Greece) ShayKutten(Technion,Haifa,Israel) FabrizioLuccio(UniversityofPisa,Italy) BernardMans(MacquarieUniversity,Australia) PaoloPenna(UniversityofSalerno,Italy) AndreaRicha(ArizonaStateUniversity,Tempe,USA) IainStewart(UniversityofDurham,UK) ErkkiSutinen(UniversityofJoensuu,Finland) DenisTrystram(ID-IMAGGrenoble,France) PeterWidmayer(ETHZurich,Switzerland) Local Organization VincenzoGervasi(UniversityofPisa,Italy) GiuseppePrencipe(UniversityofPisa,Italy) External Reviewers LucaBecchetti HajoBroersma ValentinaCiriani DavidCoudert StefanDantchev AnnalisaDeBonis GianlucaDeMarco VIII Organization MiriamDiIanni PaolaFlocchini TomFriedetzky GiuliaGalbiati GoranKonjevod ZviLotker OrnellaMenchi FilippoMignosi ManalMohammed MelihOnus LindaPagli FannyPascual AndreaPietracaprina SrinivasaRao AdeleRescigno AndreaRicha GianlucaRossi MassimoSantini ErikSaule MarinellaSciortino RiccardoSilvestri CorinneTouati DenisTrystram SebastianoVigna IvanVisconti DonglinXia MicheleZito RosalbaZizza Table of Contents On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 GiuseppeDiBattista,FabrizioFrati,andMaurizioPatrignani Close Encounters With a Black Hole or Explorations and Gatherings in Dangerous Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 NicolaSantoro Fun with Sub-linear Time Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 LucaTrevisan Wooden Geometric Puzzles: Design and Hardness Proofs. . . . . . . . . . . . . . 16 HelmutAlt,HansBodlaender,MarcvanKreveld,Gu ¨nterRote,and GerardTel HIROIMONO Is NP-Complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 DanielAndersson Tablatures for Stringed Instruments and Generating Functions. . . . . . . . . 40 DavideBaccherini,DonatellaMerlini,andRenzoSprugnoli Knitting for Fun: A Recursive Sweater. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Complex analysis --- Discrete mathematics --- Computer science --- Artificial intelligence. Robotics. Simulation. Graphics --- discrete wiskunde --- complexe analyse (wiskunde) --- grafische vormgeving --- informatica --- database management --- programmatielogica --- KI (kunstmatige intelligentie)
Listing 1 - 10 of 13 | << page >> |
Sort by
|