Dynamic Configuration of Agent Organizations

1 Introduction

It is useful to impose organizational structure over multiagent coalitions. Hierarchies, for instance, allow for compartmentalization of tasks: if organized correctly, tasks in disjoint subtrees of the hierarchy may be performed in parallel. Intuitively, the shallower the hierarchy the more subordinates per manager, leading to more potential for parallelism. The difficulty lies in determining a minimum depth hierarchy that is isomorphic to the problem being solved; in a business, for example, there is very little sense in assigning an accountant from the billing department as the superior of a marketing associate. Given a notion of the way in which the agents need to interact, the initial problem, then, is to determine the best hierarchy that might expedite the process of coordination. This is called the Dynamic Distributed Multiagent Hierarchy Generation (DynDisMHG) problem.

Solutions to the DynDisMHG problem currently have direct application in the field of multiagent systems, including distributed problem solving [Shehory and Kraus, 1998], cooperative multiagent systems [Sycara et al., 1996], distributed constraint reasoning (DCR), command and control, mobile ad hoc networks (MANETs), sensor nets, and manufacturing. For example, the computation time required by most complete DCR algorithms is determined by the topology of a hierarchical ordering of the agents [Silaghi and Yokoo, 2008]. The difficulty is that (1) most algorithms assume that an oracle exists to provide an efficient hierarchy; and (2) the few existing solutions to the Multiagent Hierarchy Generation problem are either centralized or do not deal well (or at all) with dynamic addition and removal of agents from the hierarchy.

One potential application of a solution to DynDisMHG is in MANETs. Protocols such as Fireworks [Law et al., 2007] overlay a communications structure onto a wireless network, which is highly dynamic as the nodes are constantly moving. There is the potential for cross-layer design: if the mobile nodes are executing a multiagent system, a communications structure could be created to exploit knowledge of both network and application layer properties.

There has been interest in DCR algorithms that are able to solve constantly changing problems [Petcu and Faltings, 2007], including those in which agents can dynamically enter and leave the hierarchy [Lass et al., 2008]. All existing provably superstabilizing (i.e., "complete") dynamic DCR algorithms, however, make a similar assumption to their static DCR counterparts: that a separate algorithm exists to generate and maintain the dynamically changing agent hierarchy.

Similar to dynamic DCR, there has been much interest in hierarchies of holonic multiagent systems (or holarchies), with wide ranging applications in distributed problem solving and manufacturing [Fischer et al., 2004]. Some have even claimed that a prerequisite for innovation in multiagent systems is the capability for subsets of agents to dynamically create ad hoc hierarchies, called "adhocracies" [van Aart et al., 2004]. Empirical evaluations have concluded that agents in a dynamic hierarchy are able to perform distributed problem solving better than agents in a static hierarchy [Yokoo, 1995]. It is anticipated that solutions to the problem of distributed multiagent hierarchy/holarchy/adhocracy generation will motivate many other applications.

Given a graph of expected interaction between the agents, this paper introduces an algorithm, called Multiagent Organization with Bounded Edit Distance (Mobed), for determining and maintaining an organizational hierarchy that is compatible with the problem being solved. It is shown that Mobed is correct and that it outperforms alternative approaches by as much as 300% in terms of edit distance between perturbations with little impact to computation and privacy.

2 Preliminaries

Let G = 〈A,E〉 be a graph consisting of an ordered set of agents, A, and a set of edges E. Each edge 〈ai, aj〉 ∈ E implies that agent ai will need to interact with aj. We shall hereafter call this an interaction graph. Let Ni denote the neighborhood of agent ai: the set of all agents that share an edge with ai. A multiagent hierarchy for a given graph G = 〈A,E〉 is an unordered, labeled, rooted tree denoted by the tuple T = 〈A, π : A → A〉, where π is a function mapping agents to their parent in the tree. The inverse of the parent function, π-1 (ai), shall be used to denote the set of children of agent ai. The notation "R+" shall be used to represent the transitive closure of a binary relation R. Agent aj is said to be the ancestor of an agent ai in a hierarchy if aj has the property (aj = π(ai))+. Let Ci be the set of ancestors of agent ai. Likewise, agent aj is a descendant of ai if (aj ∈ π-1 (ai))+. Let Di be the set of descendants of agent ai. Let v : P(A × A) → B be a validity testing function defined as:

Given an interaction graph G = 〈A, E〉, a multiagent hierarchy T is said to be valid for a given problem if v(E) = TRUE. A valid hierarchy inherently has the property that each pair of neighboring agents in the interaction graph are either ancestors or descendants of each other in the hierarchy. This ensures that no interaction will necessarily occur between agents in disjoint subtrees. Therefore, interactions in disjoint subtrees may occur in parallel.

3 ExistingWork

It is relatively trivial to prove that a simple depth-first traversal of the interaction graph will produce a valid hierarchy. Distributed algorithms for performing such a DFS traversal are known [Hamadi et al., 1998; Collin and Dolev, 1994]. A general problem with DFS-based approaches, though, is that they will often produce sub-optimal hierarchies (i.e., trees that are unnecessarily deep). For example, the hierarchy in Figure 1(b) might have been generated using a DFS traversal, however, the best-case hierarchy in Figure 1(c) could not have been generated using DFS. One metric for the amount of possible parallelism in a tree is induced-width; in general, the problem of finding a minimum-induced-width spanning tree of a graph is NP-HARD [Arnborg, 1985].

Agent hierarchies, often called "variable orderings," are employed in many DCR algorithms, usually as a means to parallelize computation for portions of the constraint graph. Most provably optimal DCR algorithms require a special hierarchy in the form of pseudotree. A decentralized algorithm for creating valid pseudotrees has been proposed [Chechetka and Sycara, 2005], however, its efficiency relies upon a priori knowledge about the maximum block size of the interaction graph, and it is also unclear how it might be extended to dynamic hierarchies. Some DCR algorithms construct a DFSbased pseudotree as the problem is being solved [Hamadi et al., 1998; Silaghi and Yokoo, 2008], however, it is likewise unclear how these algorithms might be extended to handle the intricacies of concurrency imposed by dynamic hierarchies. A number of algorithms based on asynchronous backtracking have been developed that dynamically reorder the agents within the hierarchy as the problem is being solved [Yokoo, 1995; Zivan and Meisels, 2006], but this approach has only been explored in terms of static DCR problems and it is unclear how it might be extended to problems in which agents can dynamically be added and removed.

DFS-based algorithms are relatively inexpensive (most require only a linear number of rounds), so an argument might be made that DFS could simply be re-run every time the tree changes, possibly through the use of a self-stabilizing algorithm. In certain instances, however, such an approach might cause a large disparity between the original hierarchy and the hierarchy resulting after the perturbation, as pictured in Figure 1. Continuing the corporation example, the marketing department should not necessarily have to change its managerial structure every time a new accountant is hired in the billing department. An approach with a minimal number of edits to the existing hierarchy is therefore desirable. One way to ensure a constant number of edits is to simply add new agents as a parent of the root of the hierarchy. The problem with this method, however, is that if many new agents are added then the hierarchy will tend toward a chain, which is the worst case topology in terms of parallelism. What is ultimately desirable, then, is an approach that both minimizes edit distance between successive hierarchies and also minimizes tree depth.

4 The Algorithm

We assume that the communications network provides guaranteed delivery of messages, however, there may be arbitrary latency (i.e., an asynchronous network [Lynch, 1997]). We furthermore assume that all agents are honest and correct and thus need not consider the problem of Byzantine failure. The agents are non-adversarial insofar as their primary goal is to optimize the utility of the entire coalition, however, the individual agents may have data that they wish to keep private from others. Agents' perceptions of the interaction graph are consistent, possibly through the use of a distributed consensus algorithm [Lynch, 1997]. Each agent has a unique identifier with a globally agreed ordering. Each agent, however, may not know of all of the other agents in the network; it is only assumed that ai knows the existence of all aj ∈ Ni. Each agent that has already been placed in the hierarchy only knows its parents, children, and interaction graph neighbors. Agents also know the relative location of interaction graph neighbors (i.e., ancestor or descendant).

As Mobed applies to DCR, it should be noted that our notion of an interaction graph can be equated to DCR's notion of a constraint graph. In this sense, though, our formalization is then in the context of constraint graphs of agents as opposed to constraint graphs of variables (the latter of which is the norm for DCR). This presentation was chosen for sake of both brevity and accessibility. Nothing precludes this algorithm from being applied to constraint graphs with multiple variables per agent; in such a case the work herein may be read such that "agents" are instead "variables."

With these assumptions in mind, there are a number of challenges in devising a DynDisMHG algorithm (complicated by the fact that there is no central server and agents act asynchronously in an asynchronous network): To what extent can privacy be maintained? What if a new agent has neighbors in disjoint hierarchies? How are multiple, concurrent requests for addition and removal handled? How is the hierarchy initialized? To what extent can the perturbation of an existing hierarchy be minimized subsequent to agent addition or removal? The remainder section introduces Mobed: an algorithm that addresses all of these challenges.

4.1 Theory

Given an existing hierarchy and a new agent, the first problem is to determine where in the hierarchy that agent should be added such that the hierarchy remains valid. We shall now propose and prove a series of lemmas that define such an insertion point. We first define Equation 2 that tests whether or not a given agent already in the hierarchy is a valid insertion point. In Lemmas 1 and 2 we prove, respectively, that such an insertion point must exist and that it must be unique. In Lemmas 3 and 4 we prove that the new agent can be inserted either as the parent or child of the insertion point.

Let h : A × P(A) → B be a function defined as

We shall hereafter refer to an agent ai that satisfies h(ai, I) as an insertion point for the set I. h(ai, I) will be TRUE if all of the following are true: ai is an ancestor or descendant of all agents in I \ {ai}; ai either has no descendants in I or ai has more than one child whose subtree has agents in I; and none of ai's ancestors are insertion points for I.

Lemma 1. Given a valid hierarchy T = 〈A, π〉 and an agent ai /∈ A, then

Proof. Let us assume, on the contrary, that Ni ⊆ A but there does not exist an agent aℓ such that h(aℓ,Ni). This means that either ∀aj ∈ A : Ni \ {aj} ⊈ Dj ∪ Cj; every agent has exactly one child whose subtree contains an agent in Ni; or every agent has at least one ancestor that is an insertion point for Ni. The first case contradicts Ni ⊆ A. The second case implies that the hierarchy T is cyclic (and therefore invalid) which is a contradiction. The third case either means that an aℓ must exist or it means that the hierarchy T is cyclic, both of which are contradictions.

Lemma 2. The insertion point must be unique.

Proof. Let us assume, on the contrary, that there are at least two agents in A that satisfy the existential quantification of aℓ in Equation 3; let us call two such agents a1 and a2. h(a1, Ni) and h(a2, Ni) both must be TRUE, which implies that neither a1 nor a2 is an ancestor of the other, further implying that a1 and a2 must be in disjoint subtrees. Since the hierarchy is valid it must not be cyclic, and there must be some agent a3 that is the deepest common ancestor of a1 and a2. Since a1 and a2 are both insertion points for Ni, all of the agents in Ni \ {a3} must be in C3, which by Equation 2 means that h(a3,Ni) must be TRUE, contradicting the fact that both a1 and a2 are insertion points for Ni.

Lemma 3. Given a valid hierarchy T = 〈A, π〉, the addition of a new agent ai /∈ A inserted between aℓ ∈ A and π(aℓ) will produce a valid new hierarchy T ′ = 〈A∪{ai}, π∪ {〈aℓ, ai〉, 〈π(ai), aℓ〉} \ {〈π(ai), ai〉}〉 if h(aℓ, Ni).

Proof. Since aℓ will be the only child of ai, ai will share all of aℓ's previous ancestors and descendants. Since aℓ was already a valid insertion point, ai must also remain valid.

Lemma 4. Given a valid hierarchy T = 〈A, π〉, the addition of new agent ai /∈ A as a child of aℓ ∈ A will produce a valid new hierarchy T ′ = 〈A∪{ai}, π∪{〈ai, aℓ〉}〉 if Ni ∩Dℓ = ∅ and aℓ is the insertion point for Ni.

Proof. Assume, on the contrary, that the addition of ai as a child of aℓ will produce an invalid hierarchy. By Equation 1, this means that there is at least one pair of neighboring agents that are neither ancestors nor descendants of each other. Since the original hierarchy T was valid, we know that such a pair of agents must be in {ai} ×Ni. Since v({aℓ} ×Ni) is true, we know that all of ai's interaction graph neighbors are either ancestors or descendants of aℓ. Since ai is added as a child of aℓ and therefore shares all of aℓ's ancestors, it must be true that ∃aj ∈ Ni : aj ∈ Dℓ, which contradicts Ni∩Dℓ = ∅.

4.2 General Principles

Based upon the results of the previous section, Mobed adds an agent ai to an existing hierarchy by the following procedure:

• 1: find a valid insertion point aℓ /* one must exist accord-

ing to Lemmas 1 and 2 */ 2: if Dℓ ∩Ni = ∅ then /* Lemma 4 */ 3: π(ai) ← aℓ 4: else /* Lemma 3 */ 5: π(ai) ← π(aℓ) 6: π(aℓ) ← ai

Figure 2: An execution of the algorithm for addition of a agent a5 to an existing hierarchy. Solid edges represent edges in the existing hierarchy. Dashed edges represent message passing.

Determining aℓ (step one in the procedure) can be performed by recursively passing messages up the tree starting from all agents in Ni. Without loss of generality, let us assume that all agents in Ni are already present in the same hierarchy; this assures that there must be some agent aj that will eventually receive |Ni| messages from its children. Then,

• 1: while aj received exactly one message regarding the addition of ai do
• 2: aj ← the child fromwhich aj received the message
• 3: aℓ ← aj

Using this method it is trivial to check whether Dℓ ∩Ni = ∅ (step two in the procedure): if aℓ did not receive any messages from its children then we know Dℓ ∩Ni = ∅ is true. Figure 2 provides an example execution of this algorithm.

4.3 Merging Hierarchies

We shall now consider the case when a new agent's neighborhood contains agents in disjoint hierarchies. This may happen if ai is an articulation point of the interaction graph. The approach for this case is simply to add ai as the new parent of the roots of T1 and T2. The problem, however, is that no agent in Ni necessarily knows that they are in disjoint hierarchies and the addition process as described above will deadlock.

The solution is as follows: whenever a root of a hierarchy (e.g., a1 and a3) receives an addition request regarding a new agent ai-regardless of whether that addition request was sent directly to the root or whether it was propagated up the hierarchy-and that root has received fewer than |Ni| such addition requests, then that root will additionally send a Rootmessage to ai stating that it is the root of a hierarchy. If ai ever receives |Ni| such messages then ai will become the new parent of all agents from whom it received the messages.

4.4 Preventing Race Conditions

The algorithm as it is presented above will work correctly if there is exactly one agent being added at a time. Due to the possibility of arbitrary message latency, there is a chance that concurrent additions could result in inconsistent modifications to the hierarchy among the agents. To address this we introduce a concept of active blocks of the hierarchy. When an agent aj receives an add request regarding a new agent ai, then aj goes into active mode and proceeds as normal. If aj is already in active mode, however, it will immediately reply to ai with an AlreadyActive message. Such an error condition implies that another agent in the subtree rooted at aj (or an agent on the path from aj to the root) is in the process of either being added or removed; we shall call this agent ak. aj will also send an AlreadyActive message to ak. These messages contain a field stating whether k > i. If an agent ever receives such a message it will inform all agents in its neighborhood that it is cancelling its addition. If the agent's identifier is lower priority than the other sent in the AlreadyActive message then that agent will perform an exponential backoff before restarting its addition. Otherwise, the agent will only sleep for a constant time period. Once the algorithm is complete, all agents that received an addition message regarding ai become inactive.

4.5 Initial Generation

The special cases addressed in the previous sections are sufficient to generate and maintain hierarchies as long as a hierarchy already exists. How should the initial hierarchy be generated? Which agent should become the first root?

The solution is to construct the initial hierarchy semisynchronously: an agent will not attempt addition of itself to a hierarchy until all of its higher-priority neighbors are already members of a valid hierarchy. A new agent to be added to the hierarchy, ai, will send an AddMe to all aj ∈ Ni, as described above, however, ai will send them one-by-one in order of decreasing priority of j. After each AddMe is sent, ai will block until receipt of a reply from aj before proceeding to the next, lower-priority neighbor. The neighbor's reply can be one of three possibilities: an AlreadyActive message as described in §4.4, a NoTree message (meaning the neighbor has not yet been added to a tree), or a AdditionStarted message (meaning that the neighbor does have a tree and has started the addition process for ai as described above). If ai receives a NoTree message from aj and j > i then ai will send a CancelSearch message to all ak ∈ Ni where k > j and ai will block until it receives an AddRequest message from another agent. If, on the other hand, a NoTree message is received from an aj where j < i then it is ignored. The addition will then proceed as in §4.2. Pseudocode for the entire algorithm-implementing the constructs in §4.2-4.5is given in Algorithm 1.

Algorithm 1 Mobed's distributed addition of a new agent, regardless of whether or not any of the agent's neighbors are already in hierarchies or whether those hierarchies are disjoint.

Note that the t argument is used as a type of logical clock to avoid processing messages that have expired. If a message is ever received with a t value that is lower than any other message that has been received from the sender then the message is discarded.

1: procedure ADD-AGENT(ai, t = 0)

Require: ai is the agent to be added. t is a counter for this addi-

tion attempt, initially set to zero. 2: H ←Ni 3: for all aj ∈ Ni in order of descending j do 4: SEND-MESSAGE(HasTree?) to aj 5: wait for a reply from aj 6: if the reply is AlreadyActive then 7: handle as described in §4.4. 8: else if the reply is NoTree then 9: if j > i then 10: send a CancelSearch(t) message to all am ∈ Ni where am > aj . 11: wait to receive an AddRequest message 12: return ADD-AGENT(ai, t + 1) 13: else 14: H ← H \ {aj} 15: else if the reply is a success then 16: do nothing 17: for all aj ∈ H do 18: SEND-MESSAGE(AddMe, ai, |H|, t) to aj 19: R ← ∅ /* R is a set and therefore does not allow duplicates */ 20: while |R| < |H| do 21: if the next message is a Root message from aj then 22: R ← R ∪ {aj } 23: if |R| = |H| then /* |Ni| contains agents in disjoint hierarchies */ 24: for all ar ∈ R do 25: π(ar) ← ar /* Become the new parent of ar */ 26: Tell ar that we are its new parent and that it can become inactive. 27: else if the next message is Added(p, c) from aj then 28: π(ai) ← p /* our new parent is p */ 29: π(c) ← ai /* our new child is c */ 30: R ← H

• 31: send an AddRequest to all lower-priority agents to whom ai has ever sent a NoTree message.

32: procedure HANDLE-ADDME(an, q, t) sent from aj Require: an is the agent requesting to be added and ai is the agent that received (and is processing) the message. m : V → N, r : V → P(π-1 (ai)), and s : V → B are all maps retained in memory. mmaps variables to an integer, r maps variables to the power set of ai's children, and s maps variables to a boolean. If a key does not exist in s then its value is taken to be FALSE. av is the agent for whom ai is currently active, or ∅ if ai is inactive. 33: if ai is not yet in the hierarchy then 34: SEND-MESSAGE(NoTree, t) to an 35: return 36: else if av ̸= ∅ ̸= an then 37: SEND-MESSAGE(AlreadyActive, v > n, t) to an and av 38: av ← ∅ 39: Clear all of the maps in memory and tell aj to cancel its search, forwarding the message to all agents in the current active block. 40: return 41: else 42: av ← an /* make ai active for an */ 43: if aj = an then /* aj is the variable requesting to be added */ 44: m(an) ← 1, r(an) ← ∅, and s(an) ←TRUE 45: else if aj ∈ π-1 (ai) then /* aj is one of our children */ 46: m(an) ←m(an) +1 47: r(an) ← r(an) ∪ {aj } 48: if m(an) = q then /* ai satisfies Equation 1 for Nn */ 49: if |r(an)| = 1 then /* ai is not the deepest */ 50: q′ ← q 51: if s(an) ↦→TRUE then /* ai was originally sent a message from an (meaning ai ∈ Nn) */ 52: q′ ← q′ - 1 53: ak ← the single variable in r(an) 54: SEND-MESSAGE(AddMe, an, q′ , t) to ak 55: av ← ∅ 56: remove m(an), r(an), and s(an) from memory 57: else /* ai is the deepest vertex satisfying Equation 1 */ 58: if r(an) ̸= ∅ then /* we have at least one descendant that is in Nn (Lemma 3) */ 59: π(an) ← π(ai) 60: π(ai) ← an 61: SEND-MESSAGE(Added, π(an), ai) to an 62: else /* Lemma 4 */ 63: π(an) ← ai 64: SEND-MESSAGE(Added, ai, ∅) to an 65: av ← ∅ 66: Tell all of the agents in r(an) that the search is over and clear all of the maps in memory. 67: else if our vertex ai is not the root of the pseudotree then 68: SEND-MESSAGE(AddMe, an, q, t) to π(ai) /* Forward the message to our parent */ 69: else /* This situation may occur if there are two or more variables in Nn from disjoint hierarchies */

70: SEND-MESSAGE(Root, ai, t) to an

4.6 Changes to Constraints and Agent Removal

Changes to constraints can be handled by removing and readding all affected agents. Removal of an agent ai can be accomplished by making ai, π(ai), and all aj ∈ π-1 (ai) active. All of the children are then made the children of π(ai) and ai is removed. The hierarchy will remain valid.

5 Analysis

This section analyzes-both theoretically and empiricallythe performance of Mobed. For the empirical analysis, a series of random, connected graphs were randomly generated from a uniform distribution with varying numbers of vertices and edge densities 1 . 100 such random graphs were generated for each pair of number of vertices and edge density. For each graph both DFS and Mobed were run to generate a valid hierarchies. A new vertex was then randomly added in such a way as to maintain the given edge density. DFS and Mobed were then re-run to produce a new valid hierarchy. Various metrics including the average number of rounds of computation (i.e., the length of the longest causal chain of synchronous messages required for the algorithm to reach quiescence) and the edit distance between hierarchy perturbations were recorded.

5.1 Computational Complexity

Let us consider the computational complexity of adding a new agent ai to an existing valid hierarchy T = 〈AT , π〉. We assume that Ni ⊆ AT and there are no other agents attempting to be concurrently added. ai will first send one message to each neighbor in Ni. Each aj ∈ Ni will then forward the message up the tree. In the worst case in terms of synchrony, each of the |Ni| messages will have to traverse up the tree to the root, followed by the root propagating a single message back down to the insertion point. The addition of a single agent therefore requires worst case O(|Ni|dT ) rounds, where dT is the depth of the deepest agent in T. In the worst case in terms of existing hierarchy topology, T will be a chain and the worst case number of rounds for a single insertion is O(|Ni||AT |). Construction of a hierarchy from scratch for a worst-case fully-connected interaction graph therefore requires O (∑|A| i=1 i· |A|) = O (|A|3 ) rounds. The best-case runtime, however, is O(|Ni|), which in the real world will often be quite small. Therefore, the runtime in terms of number of rounds will always be polynomial and-if Ni is boundedindividual additions will run in amortized linear time. This theory is supported by the empirical results (Figure 3).

5.2 Edit Distance

The edit distance between two hierarchies, T1 = 〈A1, π1〉 and T2 = 〈A2, π2〉, is defined as 2

1 Edge density, ranging in [0, 1], is the percentage of possible edges that exist in the graph. A density of 0.0 means that the graph has no edges while a density of 1.0 means that the graph is complete.

2 i.e., the minimum number of child-parent relationships that must be reassigned in order for the two trees to become isomorphic.

Ideally, after a single addition of an agent the edit distance between the original hierarchy and the resulting hierarchy will be minimized. The worst case edit distance for DFS will occur whenever the existing hierarchy T = 〈AT , π〉 consists of a root with |AT | - 1 children and the agent being added, ai /∈ AT , has the property Ni = AT . In this case |A| edits may occur. In contrast, Mobed bounds the number of edits for each agent addition at two.

During our empirical analysis, edit distance according to the metric formalized above was noted for both DFS and Mobed between the initial and post-vertex-addition hierarchies. Figure 4 gives the percentage difference between the edit distance of DFS and Mobed; positive percentages mean that DFS had a worse edit distance. DFS performed worse for sparse graphs (density ≤ 0.5). Although DFS performed better on dense graphs, it was only ever one edit better.

Our definition of edit distance is quite favorable to DFS; in some domains a better metric may be the number of ancestordescendant relationships that are modified as a result of each change to the interaction graph. Such perturbations in the context of DCR might cause large portions of the previously explored search space to be expanded again. With this stricter metric, Mobed still has a bounded edit distance of two, while DFS may perform much worse.

6 Conclusions and FutureWork

This paper has two primary contributions: a formal generalization of the DynDisMHG problem and introduction of Mobed: an algorithm for distributedly constructing and maintaining multiagent hierarchies with bounded edit distance between hierarchy perturbations. Mobed was compared-both theoretically and empirically-to the only other viable solution to the DynDisMHG problem: distributed DFS. It was shown that Mobed will always reach quiescence in a linear number of rounds for each agent addition with respect to the total number of agents, but under certain circumstances it can theoretically run in constant time. Re-running DFS after such a perturbation would also require a linear number of rounds, but may have arbitrarily bad edit distance. The edit distance of Mobed is always bounded at two edits, which is very low. For sparse graphs (density less than 0.5) Mobed has at least as good an edit distance as DFS, and exhibited as much as a 300% benefit. For those instances when Mobed exhibited a higher edit distance than DFS (i.e., when the graph is dense) its edit distance was no more than one edit worse. Privacy is also maintained in Mobed insofar as agents only ever have knowledge of their interaction graph neighbors, hierarchy parents, and hierarchy children. Therefore Mobed is a viable replacement for DFS as a solution to the DynDisMHG problem, especially for sparse interaction graphs.

In the future we will empirically analyze the use of Mobed in distributed problem solving algorithms. There is also much work to be done in studying hierarchy generation techniques that better balance the tradeoff between computational efficiency/messaging, edit distance, and privacy, and also methods to maintain other invariants on the hierarchy's topology.