Tech Reports Home Contact
Technical Report Series
Submit Report
Browse Reports
Information for Authors
Contact Details

Technical Report HW-MACS-TR-0070

TitleGreedy Effect in Autonomous Mobility: Complete Experimental Investigation and Theoretical Analysis.
AuthorsNatalia Chechina, Peter King, Rob Pooley, Phil Trinder
AbstractAutonomous mobile programs (AMPs) aim to balance computational loads in dynamic networks. AMPs periodically recalculate network parameters to seek a better execution environment and intend to both reduce execution time and better exploit the network. AMP behaviour has previously been investigated using mobile languages like Java Voyager and simulated. Both real and simulated AMPs suffer from greedy effects, which introduce by redundant movements during balancing. The greedy effects are a result of the locally optimal choice made by each AMP. The majority of redundant moves are due to the lack of information about intended moves of other AMPs. In this paper we propose the concept of negotiating AMPs (NAMPs) that communicate their intentions with the view to reduce redundant moves. While a number of negotiation schemes are possible, we have designed and simulated AMPs with cooperative/competitive scheme (cNAMPs), i.e. cNAMPs announce about intentions to move and compete with each other for permission to transfer to the new location. An analysis of simulated cNAMP results show that the negotiation in cNAMPs significantly decreases the number of both redundant movements and the time to rebalance. For example, cNAMPs have no redundant movements during initial distribution, which makes initial balancing at least 3 times faster in comparison with AMPs.


Email Technical Report's Administrator
|MACS Home| Top of the Page

Department of Computer Science, Heriot-Watt University, Riccarton, Edinburgh, EH14 4AS, +44 (0) 131 4514152

Last Updated: 02 September 2003 Copyright Heriot-Watt University, Disclaimer