Don Perugini, Dennis Jarvis, Stefan Reschke, Don Gossink
Military operations typically involve cooperation of various military, government and commercial organizations from various nations. In order to coordinate these autonomous organizations, a social mechanism is required that facilitates deliberative planning and task allocation in decentralized, open and dynamic environments, and enables agreements via a legal contracting process. In this paper, we present (a component of) such a mechanism, called the legal agreement protocol (LAP). Agents that plan using LAP must plan with partial observability that is the customer is only aware of proposals (capabilities) that suppliers choose to send. This makes it difficult for the customer to determine the (minimum/average) expected cost of any unallocated sub-tasks in its search. In this paper, we present and compare various heuristics that allow the customer to dynamically determine the expected cost for sub-tasks as proposals are received during planning. We show that different heuristics have tradeoffs in terms of quality of solution and search effort (efficiency of search and quantity of communication). The number of distributed agents involved in planning also influences the effort required to search. More agents increase communication, but provide more information (observability) about agents' capabilities to be utilized by the heuristics
This paper is concerned with the integer quadratic multidimensional knapsack problem (QMKP) where the objective function is separable. Our objective is to determine which expansion technique of the integer variables is the most appropriate to solve (QMKP) to optimality using the upper bound method proposed by Quadri et al. (2007). To the best of our knowledge the upper bound method previously mentioned is the most effective method in the literature concerning (QMKP). This bound is computed by transforming the initial quadratic problem into a 0-1 equivalent piecewise linear formulation and then by establishing the surrogate problem associated. The linearization method consists in using a direct expansion initially suggested by Glover (1975) of the integer variables and in applying a piecewise interpolation to the separable objective function. As the direct expansion results in an increase of the size of the problem, other expansions techniques may be utilized to reduce the number of 0-1 variables so as to make easier the solution to the linearized problem. We will compare theoretically the use in the upper bound process of the direct expansion (I) employed in Quadri et al. (2007) with two other basic expansions, namely: (II) a direct expansion with additional constraints and (III) a binary expansion. We show that expansion (II) provides a bound which value is equal to the one computed by Quadri et al (2007). Conversely, we provide the proof of the non applicability of expansion (III) in the upper bound method. More specifically, we will show that if (III) is used to rewrite the integer variables into 0-1 variables then a linear interpolation can not be applied to transform (QMKP) into an equivalent 0-1 piecewise linear problem.
The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, internet, and the web.This issue consists of the paper "Reconstructing Paxos" by Romain Boichat, Partha Dutta, Svend Frølund, and Rachid Guerraoui. Many thanks to them for contributing to this issue.The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. In a companion paper [2], we presented a deconstruction of the algorithm by factoring out its fundamental algorithmic principles within two abstractions: an eventual leader election and an eventual register abstractions. Using those abstractions, we show in this paper how to reconstruct, in a modular manner, powerful variants of Paxos. In particular, we show how to (1) alleviate the need for stable storage access if some processes remain up for sufficiently long, (2) augment the resilience of the algorithm against unstable processes, (3) enable single process decision with shared commodity disks, and (4) reduce the number of communication steps during stable periods of the system.The Island of Paxos used to host a great civilisation which had developed a sophisticated parttime parliament protocol. Paxons codified various aspects of their parliament protocol which enabled them to easily adapt the protocol to specific functioning modes throughout the seasons. In particular, during winter, the parliament was heated and some legislators did never leave the chamber: their guaranteed presence helped alleviate the need for the writing of decrees on ledgers. This was easy to obtain precisely because the subprotocol used to "store and lock" decrees was precisely codified. In spring, and with the blooming days coming, some legislators could not stop leaving and entering the parliament. Their indiscipline prevented progress in the protocol. However, as the election subprotocol used to choose the parliament president was also precisely codified, the protocol could easily be adapted to cope with indisciplined legislators. During summer, very few legislators were in the parliament and it was hardly possible to pass any decree because of the lack of the necessary majority. Fortunately, it was easy to modify the subprotocol used to store and lock decrees and devise a powerful technique where a single legislator could pass decrees by directly accessing the ledgers of other legislators. Fall was a protest season and citizens wanted a faster procedure to pass decrees. Paxons noticed that, in most periods, messengers did not loose messages and legislators replied in time. They could devise a variant of the protocol that reduced the number of communication steps needed to pass decrees during those periods. Again, this optimisation was obtained through a simple refinement of the subprotocol used to propose new decrees.
A currently popular systems research project is to explore the possibilities and problems for computer system organization that arise from the rapidly falling cost of computing hardware. Interconnecting fleets of mini- or micro-computers and putting intelligence in terminals and concentrators to produce so-called "distributed systems " has recently been a booming development activity. While these efforts range from ingenious to misguided, many seem to miss a most important aspect of the revolution in hardware costs: that more than any other factor, the en_ ~ cost of acquiring and operating a free-standing, complete computer system has dropped and continues to drop rapidly. Where a decade ago the capital outlay required to install a computer system ranged from $150,000 up into the millions, today the low end of that range is below $15,000 and dropping. The consequence of this particular observation for system structure comes from the next level of analysis. In most organizations, decisions to make capital acquisitions tend to be more centralized for larger capita] amounts,