We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship. In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ? In this paper we address these questions, focusing on two sub-models of LUMI: FSTA, where the robots have a constant-size persistent memory but are silent; and FCOM, where the robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler Fsynch, while they are incomparable under the semi-synchronous scheduler Ssynch.


    Access

    Download


    Export, share and cite



    Title :

    On Memory, Communication, and Synchronous Schedulers When Moving and Computing


    Contributors:

    Publication date :

    2020-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    SARDA Surface Schedulers

    Malik, Waqar | NTRS | 2016



    Design and Evaluation of Automotive Test Schedulers

    Peters, M. | British Library Conference Proceedings | 1996


    Analysis of power efficiency of schedulers in LTE

    Chiumento, Alessandro / Pollin, Sofie / Desset, Claude et al. | IEEE | 2012