Technical Report HW-MACS-TR-0072
|Title||Title: Reducing Redundant Autonomous Mobile Program Movements by Negotiation.|
|Authors||Natalia Chechina, Peter King, 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 using simulation.
AMPs suffer from greedy effects, which introduce 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 identify two forms of greedy effects and 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 a cooperative/competitive scheme (cNAMPs), i.e. cNAMPs announce their intentions to move and compete with each other for permission to transfer to the new location. An analysis of simulated cNAMP results shows that even this simple negotiation significantly decreases both the number of redundant movements and the time to rebalance. For example, cNAMPs make no redundant movements during initial distribution, which makes initial balancing at least 3 times faster in comparison with AMPs.