Technical Report HW-MACS-TR-0070
|Title||Greedy Effect in Autonomous Mobility: Complete Experimental Investigation and Theoretical Analysis.
|Authors||Natalia Chechina, Peter King, Rob Pooley, Phil Trinder|
|Abstract||Autonomous 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.