Looking for a Common View for Mobile WorldsMaria Gradinariu, Michel RaynalIRISA/INRIA-CNRS, Universit´e Rennes 135000 Rennes, FranceGwendal SimonFrance Telecom R & D92794 Issy Moulineaux, FranceAbstractThis paper considers central issues of distributed com-puting in a mobile environment. Its aim is to light on thefirst brick of a common view for mobile systems. We pooltogethermobile systems and analyze them from different an-gles including architecture and computability aspects. Weshow that mobile systems (i.e., cellular systems, ad hoc net-works, peer-to-peer systems, virtual reality systems or co-operative robotics) are basically confronted with the sameproblems, hence it is useless to maintain the actual “mis-leading” barriers. Due to important similarities betweenthe different mobile systems we claim that the next logi-cal step in building a common view is to design a modelwhich conceptually should unify them by providing an ab-stract description of the parameters which distinguish thesesystems from classic distributed systems. Moreover, in thenew model, the fundamental problems of distributed com-puting (i.e., (k-)mutual exclusion, leader election or groupcommunication) should find appropriate specifications.1 IntroductionThe distributed computing area includes henceforth mo-bile systems (i.e., cellular and ad-hoc networks, peer-to-peer systems, mobile virtual reality and cooperativerobotics). The classic models and solutions are not adaptedto mobile worlds hence new models, new problems and ob-viously new solutions should be designed. This paper advo-cates for the creation of a common view for mobile worldsbased on the similarities between them. In the sequel wepresent in an informal manner the main characteristics ofwhat are usually referred as mobile systems, then we de-scribe the elements on which should be based the design ofa mobile system model and finally present in an exhaustivemanner the models proposed so far in the mobile systemsliterature. We continue our investigation with the problemssolved in mobile systems starting with specific problems.Then we present solutions provided so far for some funda-mental problems in distributed computing (i.e., (k-)mutualexclusion and leader election). We conclude by presentingour opinion on open problems or possible future researchdirections in mobile systems.2 Mobile WorldsIn this Section, we show that the Mobile System appel-lation is not restricted to wireless mobile systems, but in-cludes several research areas. Typically, we observe thatdifferent research communities converge towards an archi-tecture design of systems characterized by the notions ofposition and mobility.2.1 Mobile SystemsIn this Section, we present characteristics of some popu-lar mobile systems.Cellular Networks In Cellular Networks, a base sta-tion manages an area of world called cell. Mobile hosts areconnected with the base station of the cell to which theybelong. Moreover, the mobile hosts cannot establish a di-rect connection between them, they rely on a base station tocommunicate. Interconnected base stations and cell shapesare traditionally fixed in mobile phone systems.Ad-Hoc Networks Ad-Hoc Networks differ from Cel-lular Networks in not relying on any specific infrastructure.Each mobile host can send messages to the nodes withinits transmission range. Moreover, it can route messages onbehalf of others. That is, two mobile hosts can communi-cate either over a direct wireless link or over a sequence ofwireless links including one or more intermediate nodes.Peer-to-Peer Systems A Peer-to-Peer system is a dy-namic and scalable set of peers that distributes the cost ofsharing data. Each peer can join or leave the system at anymoment and can communicate with any other peer underthe only hypothesis that the two peers are aware of eachother. The main characteristics of peer-to-peer systems arethe ability to pool together and harness large amount of re-sources, self-organization, load-balancing, adaptation andfault-tolerance.Proceedings of the 9th International Workshop on Future Trends of Distributed Computing Systems, IEEE, 2003, pp. 159–165Shared Virtual Reality Systems In general, a VirtualWorld means a technology for moving through and interact-ing with a three-dimensional computer-generated environ-ment such that the experience is perceivedto be real. SharedVirtual Environments are inhabited by interconnected Enti-ties driven by users (avatars) or by computer (virtual ob-jects). Entities, characterized by a position in the virtualworld, enter and leave the world, move from one virtualplace to another and interact in real-time. In the real world,which virtual environments emulate, entities have a limitedarea of interest. Thus, a walking person typically has anarea of interest of only several hundred meters. So, in avirtual environment, entities need only to be aware of eachother within immediate surroundings.Cooperative Robotics and Nanorobotic Systems Acooperative robotic system is a collection of robots whichare organized in a single coherent team. The main differ-ence between classic distributed mobile systems and coop-erative robotic systems is the requirement that robots shouldcontrol their own motion. The fundamental difference be-tween the nanorobots and the cooperative robots is theirability to reproduce themselves (i.e. produce at any mo-ment physical copies of themselves). [7] surveys cooper-ative (nano)robotics systems pointing out similarities be-tween these systems and ad-hoc networks.2.2 Mobile ArchitecturesFrom the architectural point of view, we distinguish puresystems (also called uniform systems) and hybrid systems(also referred as hierarchical systems).Pure Systems A mobile system is referred as pure whenall participants have equal or similar role. Nodes haveidentical capabilities and responsibilities, and all commu-nications are symmetric. Among the different mobile sys-tems, peer-to-peer implementations like Gnutella [12] orFreenet [6] are relevant examples of pure systems. Despitethe heterogeneity in transmission ranges, ad-hoc networksare pure systems, in which all nodes are simultaneouslyserver, router and client. An example of virtual reality sys-tem based on a pure architecture is Solipsis [18].In pure systems only a local view is accessible, hencethe application design is more fastidious due to the systemsymmetry. Instead, a pure system offers as main advantagesits scalability, no additional cost for the