Narrow Results

Network robustness is a necessary prerequisite for the effective execution of resilient control in distributed multiple unmanned aerial vehicles (UAVs). However, it remains a challenging task to construct a communication graph that satisfies specific network robustness properties. This paper investigates robust formation control of multi-UAV systems using control barrier functions (CBFs). We first propose a novel formation law to drive groups of UAVs into formations with communication graphs that satisfy the $(r,s)$-robustness. With such a law, all the normal UAVs in the formation are capable of executing a given resilient consensus protocol, and achieving convergence in the presence of malicious attackers. Then, we present a control law that facilitates the establishment of UAV formations, in which the communication graphs satisfy p-fraction robustness. Finally, simulation examples are given to verify the effectiveness of the proposed formation control laws.

Checkpoint is a designated place in a program at which normal process is interrupted specifically to preserve the status information necessary to allow resumption of processing at a later time. A checkpoint algorithm for mobile distributed systems needs to handle many new issues like: mobility, low bandwidth of wireless channels, lack of stable storage on mobile nodes, disconnections, limited battery power and high failure rate of mobile nodes. These issues make traditional checkpointing techniques unsuitable for such environments. Minimum-process coordinated checkpointing is an attractive approach to introduce fault tolerance in mobile distributed systems transparently. This approach is domino-free, requires at most two checkpoints of a process on stable storage, and forces only a minimum number of processes to checkpoint. But, it requires extra synchronization messages, blocking of the underlying computation or taking some useless checkpoints. In this paper, we design a minimum-process checkpointing algorithm for mobile distributed systems, where no useless checkpoint is taken. We reduce the blocking of processes by allowing the processes to do their normal computations, send messages and receive selective messages during their blocking period.

The arrangement graph A_n,k is one of the attractive underlying topologies for distributed systems. Let f_m(n, k) be the minimum number of faulty links that make every sub-arrangement graph A_n-m,k-m faulty in A_n,k under link failure model. In this paper, we proved that , , and for 2 ≤ m ≤ k − 2.

Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g., probabilistic self-stabilization only guarantees probabilistic convergence to a correct behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self-stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self-stabilizing and probabilistic self-stabilizing counterparts.

The problem of two node-disjoint paths is to identify two paths ${{𝒬}}_1$ and ${{𝒬}}_2$ from source $s\in V$ to target $t\in V$ without any common intermediate node in a communication network $G=(V,E)$, where each node (vertex) in $V$ denotes a process and each edge $(p,q)\in E$ denotes a communication channel between nodes $p$ and $q$. In this paper, we present the first adaptive stabilizing algorithm for finding a pair of node-disjoint paths in a semi-anonymous arbitrary network in $O(D)$ rounds and the state-space complexity is $O(logD)$ bits per process, where $D$ is the diameter of the communication network. The algorithm assumes weakly fair distributed daemon and the knowledge of an upper bound on the number of processes by each process. If two disjoint paths exist between $s$ and $t$, two disjoint paths are guaranteed to be constructed. In addition, the algorithm detects if two node-disjoint paths exist or not. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. The proposed algorithm has a wide range of applications in ensuring reliability and security of sensor, mobile and fixed communication networks.

Reliability of interconnection networks is important to design multiprocessor systems. The extra edge connectivity and component edge connectivity are two parameters for the reliability evaluation. The $k$-extra edge connectivity ${\lambda }_k(G)$ is the cardinality of the minimum extra edge cut $F$ such that $G-F$ is not connected and each component of $G-F$ has at least $k$ vertices. The $t$-component edge connectivity ${\lambda }^t(G)$ of a graph $G=(V,E)$ is the minimum edge number of a set $F$ such that $G-F$ is not connected and $G-F$ has at least $t$ components. In this paper, we find the relation of extra edge connectivity and component edge connectivity for regular networks. As an application, we determine the component edge connectivity of BC networks, $k$-ary $n$-cubes, enhanced hypercubes.

We introduce a class of distributed systems called Communicating Sequential Agents (CSAs). Sound and complete axiomatizations are provided for various subclasses using a family of indexed temporal logics. Some of the important features of these logics are:

• Both the formulas and the structures for the logics reflect the fact that a system is composed out of a number of participating sequential agents.

• Formulas of the logics are interpreted only at local states.

• An agent makes a definite assertion about another agent only if it has received — directly or indirectly — some communication from that agent supporting that assertion.

In this paper, a self-stabilizing algorithm is presented for finding the articulation points of a connected undirected graph on a distributed or network model of computation after O(n²|E|) moves. The algorithm is resilient to transient faults and does not require initialization. A correctness proof of the algorithm is also presented. The paper concludes with remarks on issues such as the time complexity of the algorithm and open problems.

In this paper, we consider arbitrary tree networks where every processor, except one, called the root, executes the same program. We show that, to design a depth-first token circulation protocol in such networks, it is necessary to have at least configurations, where n is the number of processors in the network and Δ_i is the degree of processor p_i.

We then propose a depth-first token circulation algorithm which matches the above minimal number of configurations. We show that the proposed algorithm is self-stabilizing, i.e., the system eventually recovers itself to a legitimate state after any perturbation modifying the state of the processors. Hence, the proposed algorithm is optimal in terms of the number of configurations and no extra cost is involved in making it stabilizing.

This paper defines a group partitioning model with the view to improving the load balancing in a distributed system. Using modelling and simulation, we analyze the impact of this new partitioning technique on load balancing strategies. We show that a strategy based on group preference gives efficient results.

In this paper we present a scenario for the grid immersion of the procedures that solve the protein structural similarity determination problem. The emphasis is on the way various computational components and data resources are tied together into a workflow to be executed on a grid. The grid deployment has been organized according to the bag-of-service model: a set of different modules (with their data set) is made available to the application designers. Each module deals with a specific subproblem using a proper protein data representation. At the design level, the process of task selection produces a first general workflow that establishes which subproblems need to be solved and their temporal relations. A further refinement requires to select a procedure for each previously identified task that solves it: the choice is made among different available methods and representations. The final outcome is an instance of the workflow ready for execution on a grid. Our approach to protein structure comparison is based on a combination of indexing and dynamic programming techniques to achieve fast and reliable matching. All the components have been implemented on a grid infrastructure using Globus, and the overall tool has been tested by choosing proteins from different fold classes. The obtained results are compared against SCOP, a standard tool for the classification of known proteins.

In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.

In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement (O(log(n)) bits per processor where n is the number of processors). Our algorithm is silent and must be composed with a silent self-stabilizing algorithm computing a Depth-First Search (DFS) Spanning Tree of the network. So, in the paper, we will prove that the composition of our algorithm with any silent self-stabilizing DFS algorithm is self-stabilizing. Finally, we will show that our algorithm needs O(n²) moves to reach a terminal configuration once the DFS spanning tree is computed. Note that this time complexity is equivalent to the best proposed solutions.

In this paper we investigate the problem of designing load balancing protocols in distributed systems involving self-interested participants. These participants have their own requirements and objectives and no a-priori motivation for cooperation. Their selfish behavior may lead to poor performance and inefficiency. To address this problem we design a load balancing mechanism with verification that provides incentives to participants to report their true parameters and follow the given algorithm. We prove that our load balancing mechanism is truthful (i.e., agents will be better off by reporting their true parameters) and satisfies the voluntary participation condition (i.e., truthful agents never incur a loss). We present a simulation study to show the performance of our load balancing mechanism.

In this paper we derive a lower bound for the total communication volume when mapping arbitrary task graphs onto a distributed processor system. For a K processor system this lower bound can be computed with only the K (possibly) largest eigen values of the adjacency matrix of the task graph and the eigen values of the adjacency matrix of the processor graph. We also derive the eigen values of the adjacency matrix of the processor graph for a hypercube multiprocessor and illustrate the concept with a simple example for the two processor case.

We introduce the notion of Update-Last scheme as a distributed method of storing an index, and derive exact bounds on their space complexity.

We present a class of efficient algorithms for global combine operations in k-port message-passing systems. In the k-port communication model, in each communication round, a processor can send data to k other processors and simultaneously receive data from k other processors. We consider algorithms for global combine operations in n processors with respect to a commutative and associative reduction function. Initially, each processor holds a vector of m data items and finally the result of the reduction function over the n vectors of data items, which is also a vector of m data items, is known to all n processors. We present three efficient algorithms that employ various trade-offs between the number of communication rounds and the number of data items transferred in sequence. For the case m=1, we have an algorithm which is optimal in both the number of communication rounds and the number of data items transferred in sequence.

Timestamps have been used for designing and analyzing a number of algorithms in distributed systems. The reusability of timestamps is investigated in the setting of a message-passing system and a simple implementation is presented for bounded timestamps.

In this paper, we consider arbitrary tree networks where every processor, except one, called the root, executes the same program. We show that, to design a depth-first token circulation protocol in such networks, it is necessary to have at least configurations, where n is the number of processors in the network and Δ_i is the degree of processor p_i.

We then propose a depth-first token circulation algorithm which matches the above minimal number of configurations. We show that the proposed algorithm is self-stabilizing, i.e., the system eventually recovers itself to a legitimate state after any perturbation modifying the state of the processors. Hence, the proposed algorithm is optimal in terms of the number of configurations and no extra cost is involved in making it stabilizing.

In a multi-agent system, an agent may utilize its idle time to assist other agents in the system. Intent recognition is proposed to accomplish this with minimal communication. An agent performing recognition observes the tasks other agents are performing and, unlike the much studied field of plan recognition, the overall intent of an agent is recognized instead of a specific plan. The observing agent may use capabilities that it has not observed. A conceptual framework is proposed for intent recognition systems. An implementation of the conceptual framework is tested and evaluated. We hypothesize that using intent recognition in a multi-agent system increases utility (where utility is domain specific) and decreases the amount of communication. We test our hypotheses using the domain of Cow Herding, where agents attempt to herd cow agents into team corrals. A set of metrics, including task time and number of communications, is used to compare the performance of plan recognition and intent recognition. In our results, we find that intent recognition agents communicate fewer times than plan recognition agents. In addition, unlike plan recognition, when agents use the novel approach of intent recognition, they select unobserved actions to perform. Intent recognition agents were also able to outperform plan recognition agents by consistently scoring more points in the Cow Herding domain. This research shows that under certain conditions, an intent recognition system is more efficient than a plan recognition system. The advantage of intent recognition over plan recognition becomes more apparent in complex domains.