We study the dispersion problem for k mobile agents on an n-node anonymous, memory-less graph with maximum degree Δ. Agents must autonomously relocate so that no two agents occupy the same node. While an optimal O(k)-time, O(log(k + Δ))-memory algorithm is known under synchronous settings, the best known asynchronous algorithm requires O(k log min {k, Δ}) time due to the difficulty of distinguishing unvisited nodes from nodes temporarily vacated by agents. We close this gap by presenting the first fully asynchronous algorithm achieving asymptotically optimal O(k) time and O(log(k + Δ)) memory. Our main technical contribution is the Port-1 Tree (P1Tree), a novel structural property of a port-labeled graph. By forcing the DFS traversal to prioritize edges locally labeled with port 1, P1Tree allows agents to verify the status of neighboring nodes in O(1) asynchronous epochs without relying on timing assumptions or oscillations used in synchronous settings. We show that this approach yields optimal bounds for both rooted and general initial configurations.

The dispersion problem has received much attention recently in the distributed computing literature. In this problem, k ≤ n agents placed initially arbitrarily on the nodes of an n-node, m-edge anonymous graph of maximum degree Δ have to reposition autonomously to reach a configuration in which each agent is on a distinct node of the graph. Dispersion is interesting as well as important due to its connections to many fundamental coordination problems by mobile agents on graphs, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective has been to provide a solution that optimizes simultaneously time and memory complexities. There exist graphs for which the lower bound on time complexity is Ω(k). Memory complexity is Ω(log k) per agent independent of graph topology. The state-of-the-art algorithms have (i) time complexity O(k log2 k) and memory complexity O(log(k + Δ)) under the synchronous setting [DISC'24] and (ii) time complexity O(min{m, kΔ}) and memory complexity O(log(k + Δ)) under the asynchronous setting [OPODIS'21]. In this paper, we improve substantially on this state-of-the-art. Under the synchronous setting as in [DISC'24], we present the first optimal O(k) time algorithm keeping memory complexity O(log(k + Δ)). Under the asynchronous setting as in [OPODIS'21], we present the first algorithm with time complexity O(k log k) keeping memory complexity O(log(k + Δ)), which is time-optimal within an O(log k) factor despite asynchrony. Both the results were obtained through novel techniques to quickly find empty nodes to settle agents, which may be of independent interest.

We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.

Given an undirected, anonymous, port-labeled graph of n memory-less nodes, m edges, and degree Δ, we consider the problem of dispersing k ≤ n robots (or tokens) positioned initially arbitrarily on the nodes of the graph to exactly k different nodes, one on each node. The objective is to simultaneously minimize time and memory requirement at each robot. The best previously known algorithm solves this problem in O ( min ⁡ { m , k Δ } ⋅ log ⁡ ℓ ) time storing O ( log ⁡ ( k + Δ ) ) bits at each robot, where ℓ ≤ k / 2 is the number of nodes with multiple robots positioned on them in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in O ( min ⁡ { m , k Δ } ) time with O ( log ⁡ ( k + Δ ) ) bits at each robot. The memory complexity of our algorithm is already asymptotically optimal and the time complexity is asymptotically optimal for the graphs of constant degree Δ = O ( 1 ) . The result holds in both synchronous and asynchronous settings.

Detecting causality or the “happened before” relation between events in an asynchronous distributed system is a widely used building block in distributed applications. To the best of our knowledge, this problem has not been examined in a system with Byzantine processes. We prove the following results for an asynchronous system with Byzantine processes. (1) We prove that it is impossible to determine causality between events in the presence of even a single Byzantine process when processes communicate by unicasting. (2) We also prove a similar impossibility result when processes communicate by broadcasting. (3) We also prove a similar impossibility result when processes communicate by multicasting. (4–5) In an execution where there exists a causal path between two events passing through only correct processes, we prove that it is possible to detect causality between such a pair of events when processes communicate by unicasting or broadcasting. (6) However, when processes communicate by multicasting and there exists a causal path between two events passing through only correct processes, we prove that it is impossible to detect causality between such a pair of events. (7–9) Even with the use of cryptography, we prove that the impossibility results of (1–3) for unicasts , broadcasts, and multicasts, respectively, hold. (10–12) With the use of cryptography, when there exists a causal path between two events passing through only correct processes, we prove it is possible to detect causality between such a pair of events, irrespective of whether the communication is by unicasts, broadcasts, or multicasts. Our results are significant because Byzantine systems mirror the real world.

The dispersion problem on graphs requires k robots placed arbitrarily at the n nodes of an anonymous graph, where k ≤ n , to coordinate with each other to reach a final configuration in which each robot is at a distinct node of the graph. The dispersion problem is important due to its relationship to graph exploration by mobile robots, scattering on a graph, and load balancing on a graph. Prior work on solving dispersion assumed the synchronous model. We propose four algorithms to solve dispersion on graphs in the asynchronous model. The first two algorithms require O ( k log ⁡ Δ ) bits at each robot and O ( min ⁡ ( m , k Δ ) ) steps running time, where m is the number of edges and Δ is the maximum degree of the graph. The algorithms differ in what, where, and how data structures are maintained. The third algorithm has a space usage of O ( max ⁡ ( min ⁡ ( D , k ) ⋅ log ⁡ Δ , log ⁡ D ) ) bits at each robot and uses O ( Δ min ⁡ ( D , k ) + 1 ) steps, where D is the graph diameter. The fourth algorithm has a space usage of O ( max ⁡ ( log ⁡ k , log ⁡ Δ ) ) bits at each robot and uses O ( min ⁡ ( m , k Δ ) ⋅ k ) steps. In contrast with existing works which all assume the synchronous model, these are the first algorithms to solve dispersion in the weaker but more realistic asynchronous model.

Detecting causality or the “happens before” relation between events in a distributed system is a fundamental building block for distributed applications. It was recently proved that this problem cannot be solved in an asynchronous distributed system in the presence of Byzantine processes, irrespective of whether the communication mechanism is via unicasts, multicasts, or broadcasts. In light of this impossibility result, we turn attention to synchronous systems and examine the possibility of solving the causality detection problem in such systems. In this paper, we prove that causality detection between events can be solved in the presence of Byzantine processes in a synchronous distributed system. We prove the result by providing two algorithms. The first algorithm uses the Replicated State Machine (RSM) approach and vector clocks. The second algorithm is round-based and uses matrix clocks. The RSM-based algorithm can also run deterministically in partially synchronous systems.

Byzantine fault-tolerant causal ordering of messages is useful to many applications. Causal ordering requires a property that we term strong safety, and liveness. In this paper, we use execution histories to prove that it is impossible to solve causal ordering – strong safety and liveness – in a deterministic manner for unicasts, multicasts, and broadcasts in an asynchronous system with one or more Byzantine processes. We also define a weaker version of strong safety termed weak safety. We prove that it is impossible to solve causal ordering – weak safety and liveness – in a deterministic manner for unicasts and multicasts, in an asynchronous system with one or more Byzantine processes. In view of these impossibility results, we propose the Sender-Inhibition algorithm and the Channel Sync algorithm to provide causal order – weak safety and liveness – of unicasts under the Byzantine failure model in synchronous systems, which have a known upper bound on message latency. The algorithms operate under the synchronous system model, but are inherently asynchronous and offer a high degree of concurrency as lock-step communication is not assumed. The two algorithms provide different trade-offs. We also indicate how the algorithms can be extended to multicasts.

Causal ordering of messages in distributed systems is important for capturing application-level semantics. To the best of our knowledge, Byzantine fault-tolerant causal ordering has not been attempted for point-to-point communication in an asynchronous setting. In this paper, we first prove that it is impossible to causally order messages under point-to-point communication in an asynchronous system with one or more Byzantine processes. In the face of this impossibility, we then present an algorithm that can causally order messages under point-to-point communication in the face of Byzantine failures, assuming the network provides a known upper bound on the message latency. We also prove that it is impossible to causally order multicasts in an asynchronous setting with one or more Byzantine processes. We then give an extension of our algorithm for unicasts to provide Byzantine fault-tolerant causal ordering of multicasts under the assumption of a known upper bound on the message latency.

Causal ordering of broadcasts is a widely used requirement in collaborative distributed software systems. We consider Byzantine-tolerant causal ordering of broadcasts in a replicated data store implemented over an incomplete graph network topology, wherein messages of the broadcast are sent via flooding. We propose two protocols to achieve this. The incomplete graph topology also occurs naturally in wireless networks and in overlay peer-to-peer networks. We identify four properties – safety, liveness, no impersonation, and no avatars – that a Byzantine-tolerant causal broadcast algorithm for a replicated data store over an incomplete graph must satisfy. We also reformulate the traditional properties – validity, integrity, self-delivery, and reliability (or termination) – specified for a complete graph in the literature for a replicated data store system over an incomplete graph topology. We then analyze whether Byzantine processes can mount attacks on these properties in our two protocols. We show results for the classical communication model and the local broadcast model.

Detecting causality or the happens before relation between events in an asynchronous distributed system is a fundamental building block for distributed applications. To the best of our knowledge, this problem has not been examined in a system with Byzantine processes. We prove the following results for an asynchronous system with Byzantine processes. (1) We prove that it is impossible to determine causality between events in the presence of even a single Byzantine process when processes communicate by unicasting. (2) We also prove a similar impossibility result when processes communicate by broadcasting. (3) We also prove a similar impossibility result when processes communicate by multicasting. (4) In an execution where there exists a causal path between two events passing through only correct processes, the impossibility result for unicasts remains. (5) However, when processes communicate by broadcasting and there exists a causal path between two events passing through only correct processes, it is possible to detect causality between such a pair of events. (6) In an execution where processes communicate by multicasting and there exists a causal path between two events passing through only correct processes, we prove that the impossibility result for multicasts remains.

In this paper, we examine the inherent properties of the Byzantine Reliable Broadcast (BRB) primitive as pertain to the ability to provide causal ordering. We prove the following results. First, we analyze Bracha’s BRB algorithm and show that under the failure-free model, safety is guaranteed across broadcasts. Second, we also prove that Bracha’s BRB algorithm guarantees safety across broadcasts under the crash failure model tolerating any number of crash failures. Third, we prove that Bracha’s BRB algorithm cannot provide weak or strong safety under the Byzantine failure model. Fourth, we prove that neither the Imbs-Raynal BRB protocol nor any (2,*)-round BRB protocol can provide causal order even if all processes are correct, and they must incur additional latency to causally order messages at a higher layer. The inherent causal ordering properties of Bracha’s BRB can be of use under favourable circumstances in practical applications, given the widespread adoption of the protocol.

Asynchronous geo-replication for data resources is used to provide high availability and lower latency in modern cloud store systems. Convergent causal consistency is the corner-stone to provide useful semantics for online human interaction services. Compared to full replication, partial replication has potential benefit of lower message counts in social network systems. However, static replication is ineffective for time-varying workloads. We propose a causal+ consistency protocol, CaDRoP, to support dynamic replication, and ensure the convergence property for all comments following a post and the causal ordering between posts with explicit causality. We evaluate CaDRoP protocol with realistic workloads by different PUT rates in terms of the practical price of Amazon AWS. The results show that CaDRoP incurs much lower cost than the statically replicated data store in another causal+ algorithm. We further evaluate CaDRoP by comparing it with a clairvoyant optimal replication solution. The findings indicate that with cache, CaDRoP incurs only around 6% ~ 16% extra cost. Without cache, CaDRoP brings around 2% ~ 4.5% extra cost in steady states.

Flooding is a fundamental concept in distributed computing. In flooding, typically, a node forwards a message to its neighbors for the first time when it receives a message. Later if the node receives the same message again, it simply ignores the message and does not forward it. The nodes store a “message record” to ensure that the same message is not forwarded again. Hussak and Trehan introduced amnesiac flooding where nodes do not require to keep the message record. They established a surprising result that the amnesic flooding of a single (k = 1) message starting from some source node always terminates in bipartite graphs in e rounds and in non-bipartite graphs in [e + 1, e + D + 1] rounds, where e is the eccentricity of the source node and D is the diameter of the graph. Recently, Hussak and Trehan introduced dynamic amnesiac flooding initiated in possibly multiple rounds with possibly multiple (k > 1) messages from possibly multiple source nodes. They showed that the partial-send case where a node only sends a message to neighbours from which it did not receive any message in the previous round and the ranked full-send case where a node sends some highest ranked message to all neighbors from which it did not receive that message in the previous round, both terminate. However, they showed that the unranked full-send case, where a node sends some random message (not necessarily the highest ranked message) to all the neighbors from which it did not receive that message in the previous round, does not terminate. In this paper, we show that the unranked full-send case also terminates, provided that diameter D is known to graph nodes. We further show that the termination time is D · (2k − 1) rounds in bipartite graphs and (2D + 1) · (2k − 1) rounds in non-bipartite graphs.

Given an undirected, anonymous, port-labeled graph of $n$ memory-less nodes, $m$ edges, and degree $Δ$, we consider the problem of dispersing $k\leq n$ robots (or tokens) positioned initially arbitrarily on one or more nodes of the graph to exactly $k$ different nodes of the graph, one on each node. The objective is to simultaneously minimize time to achieve dispersion and memory requirement at each robot. If all $k$ robots are positioned initially on a single node, depth first search (DFS) traversal solves this problem in $O(\min\{m,kΔ\})$ time with $Θ(\log(k+Δ))$ bits at each robot. However, if robots are positioned initially on multiple nodes, the best previously known algorithm solves this problem in $O(\min\{m,kΔ\}\cdot \log \ell)$ time storing $Θ(\log(k+Δ))$ bits at each robot, where $\ell\leq k/2$ is the number of multiplicity nodes in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in $O(\min\{m,kΔ\})$ time with $Θ(\log(k+Δ))$ bits at each robot, improving the time bound of the best previously known algorithm by $O(\log \ell)$ and matching asymptotically the single-source DFS traversal bounds. This is the first algorithm for dispersion that is optimal in both time and memory in arbitrary anonymous graphs of constant degree, $Δ=O(1)$. Furthermore, the result holds in both synchronous and asynchronous settings.

Causality tracking among events is a fundamental challenge in distributed environments. Much previous work on this subject has focused on designing an efficient and scalable protocol to represent logical time. Several implementations of logical clocks have been proposed, most recently the Encoded Vector Clock (EVC), a protocol to encode Vector Clocks (VC) in scalar numbers through the use of prime numbers, to improve performance and scalability. We propose and formalize the concept of Resettable Encoded Vector Clock (REVC), a new logical clock implementation, which builds on the EVC to tackle its very high growth rate issue. We show how our REVC can be applied in both shared memory systems and message passing systems to achieve a consistent logical clock. We show, through practical examples, the advantage of REVC's growth rate with respect to EVC's growth rate. Finally, we show a practical application of the REVC to the dynamic race detection problem in multi-threaded environments. We compare our tool to the currently existing VC-based tool DJIT+to show how the REVC can help in achieving higher performance with respect to the Vector Clock.

The dispersion problem on graphs asks k ≤n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driving electric cars (robots) to recharge stations (nodes). The objective is to simultaneously minimize (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory requirement at each robot. This problem has been relatively well-studied on static graphs. In this paper, we investigate it for the very first time on dynamic graphs. Particularly, we show that, even with unlimited memory at each robot and 1-neighborhood knowledge, dispersion is impossible to solve on dynamic graphs in the local communication model, where a robot can only communicate with other robots that are present at the same node. We then show that, even with unlimited memory at each robot but without 1-neighborhood knowledge, dispersion is impossible to solve in the global communication model, where a robot can communicate with any other robot in the graph possibly at different nodes. We then consider the global communication model with 1-neighborhood knowledge and establish a tight bound of Θ(k) on the time complexity of solving dispersion in any n-node arbitrary anonymous dynamic graph with Θ(log k) bits memory at each robot. Finally, we extend the fault-free algorithm to solve dispersion for (crash) faulty robots under the global model with 1-neighborhood knowledge.

Cloud computing offers a variable-cost payment scheme that allows cloud customers to specify the price they are willing to pay for renting spot instances to run their applications at much lower costs than fixed payment schemes, and depending on the varying demand from cloud customers, cloud platforms could revoke spot instances at any time. To alleviate the effect of spot instance revocations, applications often employ different fault-tolerance mechanisms to minimize or even eliminate the lost work for each spot instance revocation. However, these fault-tolerance mechanisms incur additional overhead related to application completion time and deployment cost. We propose a novel cloud market-based approach that leverages cloud spot market features to provision spot instances without employing fault-tolerance mechanisms to reduce the deployment cost and completion time of applications. We evaluate our approach in simulations and use Amazon spot instances that contain jobs in Docker containers and realistic price traces from EC2 markets. Our simulation results show that our approach reduces the deployment cost and completion time compared to approaches based on faulttolerance mechanisms.

One of the major advantages of cloud spot instances in cloud computing is to allow stakeholders to economically deploy their applications at much lower costs than that of other types of cloud instances. In exchange, spot instances are often exposed to revocations (i.e., terminations) by cloud providers. With spot instances becoming pervasive, terminations have become a part of the normal behavior of cloud-based applications; thus, these applications may be left in an incorrect state leading to certain bugs. Unfortunately, these applications are not designed or tested to deal with this behavior in the cloud environment, and as a result, the advantages of cloud spot instances could be significantly minimized or even entirely negated. We propose a novel solution to automatically find these bugs and locate their causes in the source code. We evaluate our solution using 10 popular open-source applications. The results show that our solution not only finds more instances and different types of these bugs compared to the random approach, but it also locates the causes of these bugs to help developers improve the design of the shutdown process and is more efficient in finding instances of these bugs since it interposes at the system call layer.

One of the major advantages of cloud spot instances in cloud computing is to allow stakeholders to economically deploy their applications at much lower costs than that of other types of cloud instances. In exchange, spot instances are often exposed to revocations (i.e., terminations) by cloud providers. With spot instances becoming pervasive, terminations have become a part of the normal behavior of cloud-based applications; thus, these applications may be left in an incorrect state leading to certain bugs. Unfortunately, these applications are not designed or tested to deal with this behavior in the cloud environment, and as a result, the advantages of cloud spot instances could be significantly minimized or even entirely negated. We propose a novel solution to automatically find these bugs and locate their causes in the source code. We evaluate our solution using 10 popular open-source applications. The results show that our solution not only finds more instances and different types of these bugs compared to the random approach, but it also locates the causes of these bugs to help developers to improve the design of the shutdown process for cloud-based applications.

In wide-area distributed systems, data replication provides fault tolerance and low latency. Causal consistency in such systems is an interesting consistency model. Most existing works assume the data is fully replicated because this greatly simplifies the design of the algorithms to implement causal consistency. Recently, we proposed causal consistency under partial replication because it reduces the number of messages used under a wide range of workloads. One drawback of partial replication is that its meta-data tends to be relatively large when the message size is small. In this paper, we propose an algorithm Approx-Opt-Track which provides approximate causal consistency whereby we can reduce the meta-data at the cost of some violations of causal consistency. The amount of violations can be made arbitrarily small by controlling a tunable parameter, that we call credits. We present the analytic data to show the performance of Approx-Opt-Track. We then give simulation results to show the potential benefit of Approx-Opt-Track, viz., its ability to provide almost the same guarantees as causal consistency, at a smaller cost.

Analyzing social network structures can provide an insight into the character of human interactions and communication mechanisms for solving a variety of social problems. By applying variable social vector clocks and involving weight evolution influence, we construct a coupled-weight and directed link generation algorithm for modeling a social topology in a closed social group. The degree and weight strength distributions of simulation topologies demonstrate the scale-free properties and effectiveness of weight diffusion in the real world.

Mobile social network (MoSoN) signifies an emerging area in the social computing research built on top of the mobile communications and wireless networking. It allows virtual community formation among like minded users to share data and to organize collaborative social activities at commonly agreed upon places and times. Such an activity scheduling in real-time is non-trivial as it requires tracing multiple users' profiles, preferences, and other spatio-temporal contexts, like location, and availability. Inherent conflicts among users regarding choices of places and time slots further complicates unanimous decision making. In this paper, we propose an autonomic system for activity scheduling in MoSoN communities. Our system allows flexible activity proposition while efficiently handling the user conflicts. As evident from our simulation and testbed results and analysis, our system can schedule multiple simultaneous activities in real-time while incurring low message and time cost.

In large-scale systems where an on-going monitoring program is needed, the traditional predicate detection algorithms become undesirable due to their high overhead and inability to do repeated detection and to resume the detection after a node failure. This paper presents an on-line decentralized algorithm that detects strong conjunctive predicates in a large-scale system. Our algorithm assumes a preconstructed spanning tree in the system, and detects all satisfactions of the predicate in a hierarchical manner. When a node fails or moves and the structure of the spanning tree is changed, our algorithm is able to recover from this situation and continue the detection of further occurrences of the predicate satisfactions. The hierarchical structure of our algorithm also provides a finer-grained monitoring in those large-scale systems where grouping is established and the monitoring happens at the group level. Comparing with other detection algorithms, our algorithm incurs a low space and time cost, which is distributed across all the nodes in the system, and a low message complexity. Our algorithm is particularly beneficial to resource-constrained systems.

Recently, the concept of locality-aware predicates (LAP) has been proposed. A LAP models a predicate within a local region of the whole network in a large-scale locality driven system, such as WSNs and modular robotics. In such systems, the cost of doing a global predicate detection is high, besides which, a predicate over the state of a local region better captures properties of local interactions. Thus, LAP detection becomes a relevant and interesting problem. In this paper, we explore the problem of detecting unstable conjunctive LAP, and develop a scale-free algorithm by running an interval-based detection algorithm using a vector clock built on-the-fly for processes in the local region. More importantly, we develop the encoded vector clock (EVC) technique. EVC makes detecting unstable conjunctive LAP more practical in large-scale systems by reducing the storage cost.

An important task in sensor networks is to sense locally to detect global properties that hold at some instant in physical time, namely, Instantaneously. We propose software logical clocks, called strobe clocks, that can be implemented by the middleware when synchronized physical clocks are not available or are too expensive in resource-constrained environments. Strobe clocks come in two flavors--scalar and vector. Let $(n)$ be the number of sensors and $(p)$ be the upper bound on the number of relevant events sensed at a sensor. We propose an algorithm using vector strobes that can detect all occurrences of a conjunctive predicate in time $(O(n^3p))$. The algorithm has some false negatives but this is the best achievable accuracy in the face of race conditions. We also present a variant algorithm using scalar strobes; it needs time $(O(n^2p))$ but may also suffer from some false positives. We provide a characterization of the errors. Both algorithms can also detect relational predicates but with a greater chance of error. The message complexity of strobe clocks (scalar and vector) and both algorithms is $(O(np))$, which is the same as that of reporting each sensed event for detection of the predicate even with synchronized physical clocks. We formalize the physical time modality, Instantaneously, and show its relationship to the logical time modalities Definitely and Possibly.

In this paper, we propose a Cross-Layer Application-aware Paradigm (CLAP) for designing and simulating Cross-Layer (CL) protocols. CLAP allows each layer to publish its local information to be shared with other layers and subscribe to other layers' shared information via an Information-Layer (I-Layer). The controlling layer, where optimization decisions are made, also utilizes the I-Layer to configure the behavior of other layers according to its current demands and their reported status. The publish/subscribe behavior is achieved by a new API designed as an augmentation to the SIDnet-SWANS simulator. This eliminates the need for bypassing/hacking conventional design hierarchies and simulator architectures, which greatly reduces the design and implementation complexities of CL protocols. CLAP facilitates CL interactions and extends the application layer's awareness and capabilities. This will lead CL protocol design in WSNs to a higher level of awareness via seamless CL information access and sharing, a new dimension of adaptability to operating conditions via continuous reconfiguration, and much simpler implementations.

Pervasive computing environments are composed of numerous smart entities (objects and human alike) which are interconnected through contextual links in order to create a Web of physical objects. The contextual links can be based on matching context attribute-values (e.g., co-location) or social connections. We call such a Web of smart physical objects as context map. Context maps can be used for context-aware search and browse of the physical world. However, changes of dynamic context values over time may render a context map inconsistent. So, it is important to update contextual links with changes in specific context values. Given the asynchronous nature of pervasive environments, it is non-trivial to detect events generated by contextual changes in real time. We propose two algorithms for instantaneous and periodic detection of events with concurrent timing relations. Our algorithms have low time complexity and they can address the needs of different types of pervasive computing applications. We have evaluated our proposed algorithms through simulations as well as test bed experiments.

The vector clock is an important mechanism to track logical time and causality in distributed systems. Vector clocks incur an overhead of n integers on each message, where n is the number of processes in the system. The incremental vector clock technique attaches only the changed components of the vector clock to a message. This technique to reduce the size of the message overhead is popularly used. We evaluate the performance of the incremental vector clock technique via extensive simulations under a wide range of network loads and communication patterns. Our simulations confirm the intuition that this technique shows marked gains when application processes communicate with locality patterns. In addition, the simulations revealed the following behaviour: (i) the message overhead is not much dependent on the number of processes, (ii) a higher multicast frequency, as opposed to unicasting, lowers the message overhead, and (iii) a slower network speed relative to the inter-message generation time lowers the message overhead.

Mobile objects can be used to gather samples from a sensor field. Civilian vehicles or even human beings equipped with proper wireless communication devices can be used as mobile sinks that retrieve sensor-data from sampling points within a large sensor field. A key challenge is how to gather the sensor data in a manner that is energy efficient with respect to the sensor nodes that serve as sources of the sensor data. In this paper, an algorithmic technique called Band-based Directional Broadcast is introduced to control the direction of broadcasts that originate from sensor nodes. The goal is to direct each broadcast of sensor data toward the mobile sink, thus reducing costly forwarding of sensor data packets. The technique is studied by simulations that consider energy consumption and data deliverability.

Applications that exploit the capabilities of sensor networks have triggered significant research on query processing in sensor systems. Energy constraints make optimizing query processing particularly important. This article addresses multiroot, multiquery optimization for region queries. The work focuses on application-layer issues exploiting query semantics. The article formulates three algorithms: a naïve algorithm, without data sharing, and a static and heuristic data-sharing algorithm. The heuristic algorithm allows sharing of partially aggregated results of preconfigured geographic regions and exploits the location attribute of sensor nodes as a grouping criterion. Simulation studies indicate the potential for significant energy savings with the proposed algorithms.

Large-scale distributed systems such as supercomputers and peer-to-peer systems typically have a fully connected logical topology over a large number of processors. Existing snapshot algorithms in such systems have high response time and/or require a large number of messages, typically O(n2), where n is the number of processes. In this paper, we present a suite of two algorithms: simple_tree, and hypercube, that are both fast and require a small number of messages. This makes the algorithms highly scalable. Simple_tree requires O(n) messages and has O(log n) response time. Hypercube requires O(n log n) messages and has O(log n) response time, in addition to having the property that the roles of all the processes are symmetrical. Process symmetry implies greater potential for balanced workload and congestion-freedom. All the algorithms assume non-FIFO channels.

This paper presents a O(n log n) message distributed snapshot algorithm for a system with non-FIFO channels, where n is the number of processors. The algorithm finds applications for checkpointing in large scale supercomputers and distributed systems that have a fully connected logical topology over a large number of processors. Each processor sends log n messages in the algorithm. The sizes of the messages are geometrically distributed, and the sum of the sizes of the messages sent by any processor is n. The response time of the algorithm is O(log n). The algorithm is fully distributed and the role of each processor is symmetric, unlike tree-based, ring-based, and centralized algorithms.

Advances in clock synchronization techniques allow an approximated global time in ubiquitous environments. This paper presents an event stream- based online algorithm that fuses the data reported from the processors in such a network to detect time-based predicates. The algorithm has low space, time, and message complexities. The paper also considers the detection of simultaneous events as a special case.

A stable property continues to hold in an execution once it becomes true. Detecting arbitrary stable properties efficiently in distributed executions is still an open problem. The known algorithms for detecting arbitrary stable properties and snapshot algorithms used to detect such stable properties suffer from drawbacks such as the following: They incur the overhead of a large number of messages per global snapshot, or alter application message headers, or use inhibition, or use the execution history, or assume a strong property such as causal delivery of messages in the system. We solve the problem of detecting an arbitrary stable property efficiently under the following assumptions: P1) The application messages should not be modified, not even by timestamps or message coloring. P2) No inhibition is allowed. P3) The algorithm should not use the message history. P4) Any process can initiate the algorithm. This paper proposes a family of nonintrusive algorithms requiring 6(n-1) control messages, where n is the number of processes. A three-phase strategy of uncoordinated observation of local states is used to give a consistent snapshot from which any stable property can be detected. A key feature of our algorithms is that they do not rely on the processes continually and pessimistically reporting their activity. Only the relevant activity that occurs in the thin slice during the algorithm execution needs to be examined.

This paper proposes a self-organizing bootstrap- ping protocol for establishing authenticated channels as well as secure identifiers in peer-to-peer networks. Specifically, the paper makes the following contributions. (1) It proposes a fully self-organized protocol that establishes an authenticated communication channel between nodes of a wireless ad-hoc network. This authenticated channel can then be used to establish a secret communication channel between nodes. This is the main contribution. (2) The protocol design also provides a secure identifier framework that is resilient to impersonation. The authentic identifiers it establishes can be used to associate network (and upper) layer identifiers to prevent spoofing. They can also serve as a reliable basis for reputation management protocols. The self-organized bootstrapping is a useful feature for designing autonomic systems.

Flooding and random walk are two basic mechanisms for blind search in unstructured peer-to-peer overlays. Although these mechanisms have been widely studied experimentally and via simulations, they have not been analytically modeled. Time overhead, message overhead, and success rate are often used as metrics for search schemes. This paper shows that node coverage is an important metric to estimate performance metrics such as the message efficiency, success rate, and object recall of a blind search. The paper then presents two simple models to analyze node coverage in random graph overlays. These models are useful to set query parameters, evaluate search efficiency, and to estimate object replication on a statistical basis

Web prefetching is based on Web caching and attempts to reduce user-perceived latency. Unlike on-demand caching, Web prefetching fetches objects and stores them in advance, hoping that the prefetched objects are likely to be accessed in the near future and such accesses would be satisfied from the caches rather than by retrieving the objects from the Web server. This paper reviews the popular prefetching algorithms based on popularity, good fetch, API characteristic, and lifetime, and then makes the following contributions: 1) The paper proposes a family of linear-time prefetching algorithms, objective-greedy prefetching, wherein each algorithm greedily prefetches those Web objects that most significantly improve the performance as per the targeted metric. 2) The hit rate-greedy and bandwidth-greedy algorithms are shown to be optimal for their respective objective metrics. A linear-time optimal prefetching algorithm that maximizes the H/B metric as the performance measure is proposed. 3) The paper shows the results of a performance analysis via simulations, comparing the proposed algorithms with the existing algorithms in terms of the respective objectives - the hit rate, bandwidth, and the H/B metrics. The proposed prefetching algorithms are seen to provide better objective-based performance than any existing algorithms. Further, H/B-greedy performs almost as well as H/B-optimal.

This paper presents event stream-based online algorithms that fuse the data reported from processes to detect causality-based predicates of interest. The proposed algorithms have the following features. 1) The algorithms are based on logical time, which is useful to detect "cause and effect" relationships in an execution. 2) The algorithms detect properties that can be specified using predicates under a rich palette of time modalities. Specifically, for a conjunctive predicate /spl phi/, the algorithms can detect the exact finegrained time modalities between each pair of intervals, one interval at each process, with low space, time, and message complexities. The main idea used to design the algorithms is that any "cause and effect" interaction can be decomposed as a collection of interactions between pairs of system components. The detection algorithms, which leverage the pairwise interaction among the processes, incur a low overhead and are, hence, highly scalable. The paper then shows how the algorithms can deal with mobility in mobile ad hoc networks.

Active queue management (AQM) is an area of critical importance for the operation of networks. We propose a minimal adjustment to the classic random early detection (RED) algorithm, called hyperbola RED (HRED), that uses the hyperbola as the drop probability curve. The control law of HRED can regulate the queue size close to the reference queue size which is settable by the user. As a result, it is expected that HRED is no longer sensitive to the level of network load, its behavior shows low dependence on the parameter settings, and it can achieve higher network utilization. Additionally, very little work needs to be done to migrate from RED to HRED on Internet routers because only the drop profile is adjusted. We implemented HRED on a real Internet router to examine and compare its performance with the classic RED and parabola RED that are currently deployed on Internet routers. From experiments on the real network, we conclude that HRED is insensitive to the network conditions and parameter settings, and can achieve higher network utilization than the other RED schemes.

Web prefetching is based on Web caching and attempts to reduce user-perceived latency. Unlike on-demand caching, Web prefetching fetches objects and stores them in advance, hoping that the prefetched objects are likely to be accessed in the near future and such accesses would be satisfied from the cache rather than by retrieving the objects from the Web server. This work reviews the popular prefetching algorithms based on popularity, good fetch, APL characteristic, and lifetime, and then makes the following contributions. (1) The paper proposes a family of prefetching algorithms, objective-greedy prefetching, wherein each algorithm greedily prefetches those Web objects that give the highest performance as per the metric that it aims to improve. (2) The paper shows the results of a performance analysis via simulations, comparing the objective-greedy algorithms with the existing algorithms in terms of the respective objectives - the hit rate, bandwidth, and the H/B metrics. The proposed prefetching algorithms are seen to provide the best objective-based performance. (3) The paper also proves that the algorithms based on good fetch and on the APL characteristic, although using different criteria, are equivalent in terms of their choice of objects selected for prefetching.

The peer-to-peer (P2P) network model differs from the well established client-server model in that all members of the network are assigned an equal role. P2P networks are recently gaining increasing popularity. Providing security in distributed content sharing in P2P networks is an important challenge. This paper identifies security vulnerabilities in the protocols for sharing servants' reputations in the Gnutella P2P system, proposed recently. It demonstrates attacks on the protocols that allow an attacker to alter the results of the voting procedure. The paper then presents a protocol that is resilient to the attacks described. In the proposed protocol, enhanced security against various attacks is achieved using smart design and a combination of various techniques such as the use of digital signatures for message integrity and random numbers for message freshness.

An optimal causal message ordering algorithm for asynchronous distributed systems was proposed by Kshemkalyani and Singhal and its optimality was proven theoretically. For a system of n processes, although the space complexity of this algorithm was shown to be O(n/sup 2/) integers, it was expected that the actual space overhead would be much less than n/sup 2/. It is difficult to determine the behavior of this algorithm by a theoretical analysis. We measure the overheads of two different implementations of the optimal causal message ordering algorithm via simulation under a wide range of system conditions. The optimal algorithm is seen to display significantly less message space overhead and log space overhead than the canonical Raynal-Schiper-Toueg algorithm.

This paper addresses the problem of how to service web requests quickly in order to minimize the client response time. Some of the recent work uses the idea of the shortest remaining processing time scheduling (SRPT) in Web servers in order to give preference to requests for short files. However by considering only the size of the file for determining the priority of requests, the previous works lack in capturing potentially useful scheduling information contained in the interaction between networks and end systems. To address this, this paper proposes and implements an algorithm, SWIFT that focuses on both server and network characteristics in conjunction. Our approach prioritizes requests based on the size of the file requested and the distance of the client from the server The implementation is at the kernel level for a finer-grained control over the packets entering the network. We present the results of the experiments conducted in a WAN environment to test the efficacy of SWIFT The results show that for large-sized files, SWIFT shows an improvement of 2.5% - 10% over the SRPT scheme for the tested server loads.

Specifying and detecting predicates in a distributed execution is an important problem. Distributed execution observation has classically used two modalities-Possibly(/spl Phi/) and Definitely(/spl Phi/)-for predicate /spl Phi/. Based on the temporal interactions of intervals, the author identified a complete, orthogonal set of relationships /spl Rfr/; between pairs of intervals in a distributed execution. We show how to map the rich, orthogonal classification of modalities of pairwise interval interactions, to the classical coarse-grained classification, Possibly(/spl Phi/) and Definitely(/spl Phi/), for specifying predicates defined on any number of processes. This increases the power of expressing the temporal modalities under which predicates can be specified, beyond the current Possibly/Definitely classification. We give some timestamp-based tests for the orthogonal modalities in the refined classification.

In large distributed systems, event abstraction becomes an important issue in order to represent interactions and reason at the right level of abstraction. Abstract events are collections of more elementary events, which provide a view of the system execution at an appropriate level of granularity. Understanding how two abstract events relate to each other is a fundamental problem for knowledge representation and reasoning in a complex system. In this paper, we study how two abstract events in a distributed system are related to each other in terms of the more elementary causality relation. Specifically, we analyze the ways in which two abstract events can be related to each other orthogonally, that is, identify all the possible mutually independent relations by which two such events could be related to each other. © 2002 Wiley Periodicals, Inc.

This paper presents a fair decentralized mutual exclusion algorithm for distributed systems in which processes communicate by asynchronous message passing. The algorithm requires between N-1 and 2(N-1) messages per critical section access, where N is the number of processes in the system. The exact message complexity can be expressed as a deterministic function of concurrency in the computation. The algorithm does not introduce any other overheads over Lamport's and Ricart-Agrawala's algorithms, which require 3(N-1) and 2(N-1) messages, respectively, per critical section access and are the only other decentralized algorithms that allow mutual exclusion access in the order of the timestamps of requests.

No abstract available.

Replicated databases that use quorum-consensus algorithms to perform majority voting are prone to deadlocks. Due to the P-out-of-Q nature of quorum requests, deadlocks that arise are generalized deadlocks and are hard to detect. We present an efficient distributed algorithm to detect generalized deadlocks in replicated databases. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine the existence of a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst-case time complexity of 2d+2 hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform significantly better in both time and message complexity than the best known existing algorithms. We conjecture that this is an optimal algorithm, in time and message complexity, to detect generalized deadlocks if no transaction has complete knowledge of the topology of the WFG or the system and the deadlock detection is to be carried out in a distributed manner.

No abstract available.

Fast and efficient detection of deadlocks remains an important problem in distributed operating systems. We present a distributed algorithm to detect generalized deadlocks in distributed systems. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst case time complexity of 2d hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform better in both time and message complexity than the best known distributed algorithms to detect distributed generalized deadlocks. We conjecture that the algorithm is optimal in the number of messages and time delay, among distributed algorithms to detect generalized deadlocks.

Connection preemption can be a means to provide available and reliable services to high-priority connections when a network is heavily loaded and connection request arrival patterns are unknown, or when the network experiences link or node failures. We present a simulation study of preemption in a general connection-oriented network setting. Based on the observations made in this study, we have developed two optimal connection preemption selection algorithms that operate in a decentralized/distributed network where individual link managers run the algorithm for connection preemption selection on their outgoing links. The first algorithm optimizes the criteria of (i) the number of connections to be preempted, (ii) the bandwidth to be preempted, and (iii) the priority of connections to be preempted, in that order, and has polynomial complexity. The second algorithm optimizes the criteria of (i) the bandwidth to be preempted, (ii) the priority of connections to be preempted, and (iii) the number of connections to be preempted, in that order, and has exponential complexity. We conclude that the polynomial algorithm is almost as good as the exponential algorithm in terms of overall network performance.

An emerging paradigm that handles multiple locii of control in a system allows multiple program threads to work on the same task, each thread to work on a different task, or a thread to work on multiple tasks for greater design flexibility or due to system constraints such as real-time demands and a high load on tasking. We use the definition of context to capture the notion of logical locus of control. The context of the work being currently executed must be identifiable uniquely by the application, the Resource Managers and the Transaction Manager because each context represents different work. In this paper we define context management by defining a local Context Manager and its user interface. We then show why the notion of context is required to solve the problems that arise in local and distributed transaction processing due to the emerging paradigm. We present solutions to these problems in transaction processing using the proposed context management.

No abstract available.

We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e/spl minus/2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks.>

It is argued that most previous proposals for distributed deadlock detection are incorrect because they have used informal/intuitive arguments to prove the correctness of their algorithms. Informal and intuitive arguments are prone to errors because of the highly complex nature of distributed deadlock detection/resolution algorithms. The priority-based probe algorithm for distributed deadlock detection and resolution of A.L. Choudhary et al. (1989) is corrected, and it is formally proven that the modified algorithm is correct (i.e., that it does detect all deadlocks and does not report phantom deadlocks). The proof technique is novel in that the authors first abstract the properties of the deadlock detection and resolution algorithm by invariants, and then show that the invariants imply the desired correctness of the algorithm.>

The authors define basic units of computation in distributed systems, whether communicating synchronously or asynchronously, as comprising indivisible logical units of computation that take the system from one ground state to another. It is explained how a computation can be viewed as a partial order over the basic units of the computation. The problem of detecting the basic units is considered. One algorithm for creating ground states during a computation in an asynchronously communicating system with FIFO channels is given, and an existing algorithm that implicitly creates ground states in a synchronously communicating system is referenced. The significance of the basic unit is explained, and its applications are given.>