Search

The 5G new radio (NR) standards find application in the area of augmented reality, connecting massive internet of things devices and using mission critical applications with sub millisecond latency. A large volume of spectrum needs allocation to NR standards for realizing benefits. But this is not possible due to regulatory constraints. This creates a space for developing a new algorithm in spectrum sharing for the 5G NR standards. Conventional spectrum methods are affected by mutual exclusion issues. This paper discusses token-based and non-token based spectrum sharing methods which, it is believed, can help solving this problem. The results show that proposed techniques can efficiently mitigate the mutual exclusion problem seen in 5G NR standards.

Given a mutual exclusion algorithm MXd for d ≥ 2 threads, a mutual exclusion algorithm for N > d threads can be built in a tree of degree d with N leaves, with the critical section at the root of the tree. This tournament solution seems obviously correct and efficient. The present note proves the correctness, and formalizes the efficiency in terms of concurrent complexity by means of Bounded Unity. If the tree is balanced, the throughput is logarithmic in N . If moreover MXd satisfies FCFS (first-come first-served), the worst case individual delay of the tournament algorithm is of order N . This is optimal.

Most of the mutual exclusion algorithms in a shared memory system assume that memory reference to at least one shared variable used in the algorithm is mutually exclusive. However, we claim that Peterson’s two-process mutual exclusion algorithm need not assume such low level mutual exclusion for its correct implementation. It is shown that the shared variables used in this algorithm need to obey only the safe register axioms. To prove this assertion we propose a temporal logic viz., Temporal ordering Related to Observation. This logic does not allow any assertion related to the future behavior of the predicates.

The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.

Mutual exclusion is one of the fundamental problems in mobile ad hoc networks (MANETs). The solutions to the mutual exclusion problem ensure exclusive access to a shared resource(s). In MANETs, one of the variants of mutual exclusion problem is local mutual exclusion (LME) problem. In LME problem, the non-neighboring nodes may enter CS simultaneously. Whereas, the group local mutual exclusion (GLME) problem in MANETs is the generalization of LME problem, where, unlike LME problem, the processes requesting same group (resource) may be in a critical section (CS) simultaneously. In the presented exposition, an extension of GLME problem, named h-group local mutual exclusion (h-GLME), has been proposed. The h-GLME problem, where the number of active groups can be h (h ≥ 1) and the processes requesting any of h groups may be in their respective CS simultaneously. It is applicable to MANETs. To the best of our knowledge, h-GLME is the first wireless extension of the GLME problem.

The article presents a generalization of the group mutual exclusion (GME) problem, called group local mutual exclusion (GLME), henceforth. In GLME, the activities of neighboring nodes need to be synchronized; however, no such synchronization is required between non-neighbors. The neighborhood is defined based on the location of the shared resources. A token-based solution to the GLME problem has also been proposed. The solution satisfies the correctness criteria for group mutual exclusion, i.e., safety, starvation freedom, and concurrent occupancy. The illustration includes simulation extensive results to estimate message overhead, latency, concurrency, and session switch complexity. The simulation results prove that the proposed algorithm demonstrates better performance when compared with the closest work in the literature. The token loss problem has also been handled. To the best of our knowledge, the algorithm presented in the paper is the first token-based algorithm to solve the GLME problem in MANETs.

In distributed function computation, each node has an initial value and the goal is to compute a function of these values in a distributed manner. In this paper, we propose a novel token-based approach to compute a wide class of target functions to which we refer as “token-based function computation with memory” (TCM) algorithm. In this approach, node values are attached to tokens and travel across the network. Each pair of travelling tokens would coalesce when they meet, forming a token with a new value as a function of the original token values. In contrast to the coalescing random walk (CRW) algorithm, where token movement is governed by random walk, meeting of tokens in our scheme is accelerated by adopting a novel chasing mechanism. We proved that, compared to the CRW algorithm, the TCM algorithm results in a reduction of time complexity by a factor of at least $\sqrt{n/\log (n)}$ in Erdos-Renyi and complete graphs, and by a factor of $\log (n)/\log (\log (n))$ in torus networks. Simulation results show that there is at least a constant factor improvement in the message complexity of TCM algorithm in all considered topologies. Robustness of the CRW and TCM algorithms in the presence of node failure is analyzed. We show that their robustness can be improved by running multiple instances of the algorithms in parallel.

Summary Proving properties of distributed algorithms is still a highly challenging problem and various approaches that have been proposed to tackle it [1] can be roughly divided into state-based and event-based proofs. Informally speaking, state-based approaches define the behavior of a distributed algorithm as a set of sequences of memory states during its executions, while event-based approaches treat the behaviors by means of events which are produced by the executions of an algorithm. Of course, combined approaches are also possible. Analysis of the literature [1], [7], [12], [9], [13], [14], [15] shows that state-based approaches are more widely used than event-based approaches for proving properties of algorithms, and the difficulties in the event-based approach are often emphasized. We believe, however, that there is a certain naturalness and intuitive content in event-based proofs of correctness of distributed algorithms that makes this approach worthwhile. Besides, state-based proofs of correctness of distributed algorithms are usually applicable only to discrete-time models of distributed systems and cannot be easily adapted to the continuous time case which is important in the domain of cyber-physical systems. On the other hand, event-based proofs can be readily applied to continuous-time / hybrid models of distributed systems. In the paper [2] we presented a compositional approach to reasoning about behavior of distributed systems in terms of events. Compositionality here means (informally) that semantics and properties of a program is determined by semantics of processes and process communication mechanisms. We demonstrated the proposed approach on a proof of the mutual exclusion property of the Peterson’s algorithm [11]. We have also demonstrated an application of this approach for proving the mutual exclusion property in the setting of continuous-time models of cyber-physical systems in [8]. Using Mizar [3], in this paper we give a formal proof of the mutual exclusion property of the Peterson’s algorithm in Mizar on the basis of the event-based approach proposed in [2]. Firstly, we define an event-based model of a shared-memory distributed system as a multi-sorted algebraic structure in which sorts are events, processes, locations (i.e. addresses in the shared memory), traces (of the system). The operations of this structure include a binary precedence relation ⩽ on the set of events which turns it into a linear preorder (events are considered simultaneous, if e 1 ⩽ e 2 and e 2 ⩽ e 1), special predicates which check if an event occurs in a given process or trace, predicates which check if an event causes the system to read from or write to a given memory location, and a special partial function “val of” on events which gives the value associated with a memory read or write event (i.e. a value which is written or is read in this event) [2]. Then we define several natural consistency requirements (axioms) for this structure which must hold in every distributed system, e.g. each event occurs in some process, etc. (details are given in [2]). After this we formulate and prove the main theorem about the mutual exclusion property of the Peterson’s algorithm in an arbitrary consistent algebraic structure of events. Informally, the main theorem states that if a system consists of two processes, and in some trace there occur two events e 1 and e 2 in different processes and each of these events is preceded by a series of three special events (in the same process) guaranteed by execution of the Peterson’s algorithm (setting the flag of the current process, writing the identifier of the opposite process to the “turn” shared variable, and reading zero from the flag of the opposite process or reading the identifier of the current process from the “turn” variable), and moreover, if neither process writes to the flag of the opposite process or writes its own identifier to the “turn” variable, then either the events e 1 and e 2 coincide, or they are not simultaneous (mutual exclusion property).

Many cloud computing applications are bandwidth-intensive, and thus the cloud bandwidth information is important for their tenants to manage and troubleshoot the application performance. However, current bandwidth estimation methods face great challenges with clouds. One important reason is that traffic shapers such as token bucket shapers are widely used as a building block for rate limiting in clouds. In this paper, we propose two methods called NarrowLinkCapacity and NarrowTokenRate to actively estimate the capacity and token rate, respectively, of a path in a network with potentially multiple token bucket shapers. The capacity of a path is the slowest link capacity among all links on the path, and the token rate of a path is the slowest token rate among all token bucket shapers in the path. They are two important path properties determining the average rate of a train of packets on a path. Our evaluation results show that our methods work well under a variety of network conditions.

This letter presents a distributed user association algorithm for the load balancing in heterogeneous networks. In this new method, we formulate the load balancing problem as a max min throughput problem. To solve this problem, we propose a distributed max-throughput algorithm. The main advantages of this algorithm include low computational complexity and few free parameters. Analysis and simulation results show that the proposed algorithm is very practical due to its simplicity.

Mutual Exclusion (ME) problem involves a group of processes, each of which intermittently requires access to the only resource present in the environment. Handling ME problem becomes difficult due to the dynamic nature of the ad hoc environment. This paper presents a token-based solution to ME problem in the mobile ad hoc environment. The proposed token based algorithm is sensitive to link forming and link breaking and thus is suitable for MANET. The algorithm uses the concept of dynamic request set (DRS). As the request set is dynamically updated, the average size of request set is reduced resulting in less number of messages exchanged per critical section. The algorithm satisfies mutual exclusion, starvation freedom, and freedom from deadlock. The present algorithm has been compared with DRS based ME algorithms for static distributed systems. The results show that the concept of DRS in MANETs can be successfully used. Token loss problem has also been handled separately in the present exposition.

Local mutual inclusion is a process synchronization problem where, for each process, at least one of its processes and neighbors must be in the critical section. We propose a self-stabilizing distributed solution to the local mutual inclusion problem. Convergence time of the proposed algorithm is one round under the weakly fair distributed daemon. A self-stabilizing distributed algorithm for the local mutual inclusion problem is presented.The local mutual inclusion is a problem such that for each process P, at least one of P and its neighbors is in critical section.Convergence time of the proposed algorithm is 1 round under weakly fair distributed daemon.

Electronic tokens have been successfully used as incentive mechanisms to stimulate self-interested network nodes to relay other nodes' traffic. In other words, tokens are paid to buy transmission (relaying) services. In this work, we propose a novel distributed token exchange framework, which can be used in heterogeneous small cell networks to successfully mitigate interference among the self-interested users. Contrary to the traditional role of buying transmission, tokens are exchanged between users to buy silence . Heterogeneity poses unique challenges for interference mitigation, which are difficult to handle with previous solutions but can be effectively tackled with the proposed token design. This paper focuses on the rigorous design of the optimal token scheme that minimizes the system outage probability. We first analyze the optimal strategies of individual users, which only consider their own utility maximization and do not care about the system-wise performance. We prove that under some mild conditions the optimal strategy has a simple threshold structure. We then analytically derive the optimal token supply that minimizes the network outage probability. Analysis shows that even if each user adopts the optimal strategy that only maximizes its own utility, a careful token system design can lead to a significant overall network performance improvement. Simulation results show that not only does the proposed token system design greatly improve the network outage probability, it also improves the overall network QoS, particularly when the deployment density is high.

For years, the mutual exclusion algorithm of Lycklama and Hadzilacos (1991) 21] was the optimal mutual exclusion algorithm with the first-come-first-served property, with a minimal number of (non-atomic) communication variables (5 bits per thread). Recently, Aravind published an improvement of it, which uses 4 bits per thread and has simplified waiting conditions. This algorithm is extended here with fault tolerance, and it is verified by assertional methods, using the proof assistant PVS. Progress is proved by means of UNITY logic. The paper proposes a new measure of concurrent time complexity, and proves that the concurrent complexity for throughput of the present algorithm is not more than quadratic in the number of threads. Verification of the mutual exclusion algorithm of Lycklama-Hadzilacos-Aravind.The verification is complete, and completely assertional.The first-come-first-served property, progress, and fault tolerance are proved.We introduce a measure of concurrent complexity related to UNITY.The concurrent complexity of the algorithm is proved to be at most quadratic.

In the mutual inclusion problem, at least one process is in the critical section. However, only a solution for two processes with semaphores has been reported previously. In this study, a generalized problem setting is formalized and two distributed solutions are proposed based on an asynchronous message-passing model. In the local problem setting (the local mutual inclusion problem), for each process P , at least one of P and its neighbors must be in the critical section. For the local problem setting, a solution is proposed with O ( Δ ) message complexity, where Δ is the maximum degree (number of neighboring processes) of a network. In a global setting (the global mutual inclusion problem), at least one of the processes must be in the critical section. For the global problem setting, a solution is proposed with O ( | Q | ) message complexity, where | Q | is the maximum size for the quorum of a coterie used by the algorithm, which is typically | Q | = n , where n is the number of processes in a network. The mutual inclusion problem is a problem such that at least one process is in critical section.This paper proposes two distributed solutions in the asynchronous message passing model.We discuss the relation between mutual inclusion and mutual exclusion.

Distributed fault-tolerant control algorithms are in great demand nowadays due to their practical importance in cloud computing, Internet of Things (IoT) technology, swarm robotics, and other areas. It is usually hard to make a distributed algorithm fault-tolerant. It is even harder to ensure that such algorithm behaves correctly in the presence of faults of some kind. In this work, we construct a reliable, adaptive, fault-tolerant distributed mutual exclusion algorithm based on the well-known Ricart-Agrawala algorithm. In order to formally verify it, we use a hybrid approach of deductive reasoning and bounded model-checking. First, a safety property of the Ricart-Agrawala algorithm is proved in Calculus of Inductive Constructions of Coq proof assistant using assertional reasoning. Then, an extension of that algorithm turning it into fault-tolerant and adaptive to participants set change, is formalized in TLA and checked on a bounded model. Besides constructing and verifying the algorithm, this work aims to familiarize those interested in constructing highly reliable components with well established verification methods that were used to verify the proposed algorithm.

Wireless Token Passing Networks (WTPN) have gained significant attention in the recent times due to the ability of these networks to overcome the challenge of channel access sharing faced by the wireless networks supporting real-time communications. A WTPN is specified as the network implementing token passing techniques in order to share the wireless channel access medium. In the token passing techniques, only the wireless node holding the token acquires the chance to access the channel, which thereby helps in offering guaranteed channel access time to the nodes connected in the WTPN. The efficiency of token passing techniques in offering guaranteed channel access when compared with master-slave and polling mechanisms resulted in the development of several token passing techniques. This paper intends in surveying and simulating the state-of-art token passing techniques that are applicable for supporting real-time communications over WTPN used for industrial control applications. The theoretical and practical comparison of the token passing techniques presented in this paper can help the practitioners in choosing the suitable token passing technique.

In some of the earlier works, token-based algorithms for ME are presented for the distributed environment. These are for inverted tree topology. However, such a stable, hierarchical topology is quite unrealistic for many types of networks, e.g., mobile ad-hoc networks (MANET), due to frequent link failures.

A distributed system is self-stabilizing if, regardless of its initial state, the system is guaranteed to reach a legitimate (i.e., correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [9]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes in the system. In 2008, Goddard et al. [4] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm.

Channel allocation in wireless communication network plays a crucial role in the performance of the network. Fixed scheme for channel allocation does not account for any non-uniform traffic in the network. Dynamic scheme, on the other hand, ensures that whenever a cell requires a channel, it is allocated pertaining to the frequency reuse constraints. The fact that distributed dynamic channel allocation technique has recently gained popularity is due to its high reliability and scalability. In this paper we propose a token based mutual exclusion technique to solve the problem of distributed dynamic channel allocation. We will show through simulation, how message exchange between cells is reduced in token based relaxed mutual exclusion as opposed to other relaxed mutual exclusion techniques.

An algorithm for generating a session key and a message start token is proposed. This algorithm is based on joint integration by subscribers of the N body problem.

Resource sharing is a major advantage of distributed computing. However, a distributed computing system may have some physical or virtual resource that may be accessible by a single process at a time. The mutual exclusion issue is to ensure that no more than one process at a time is allowed to access some shared resource. The article proposes a token-based mutual exclusion algorithm for the clustered mobile ad hoc networks (MANETs). The mechanism that is adapted to handle token passing at the inter-cluster level is different from that at the intra-cluster level. It makes our algorithm message efficient and thus suitable for MANETs. In the interest of efficiency, we implemented a centralized token passing scheme at the intra-cluster level. The centralized schemes are inherently failure prone. Thus, we have presented an intra- cluster token passing scheme that is able to tolerate a failure. In order to enhance reliability, we applied a distributed token circulation scheme at the inter-cluster level. More importantly, the message complexity of the proposed algorithm is independent of N, which is the total number of nodes in the system. Also, under a heavy load, it turns out to be inversely proportional to n, which is the (average) number of nodes per each cluster. We substantiated our claim with the correctness proof, complexity analysis, and simulation results. In the end, we present a simple approach to make our protocol fault tolerant.

Token bucket algorithm is a common algorithm used for traffic shaping and rate limiting. In LTE (Long Term Evolution) system, RRC (Radio Resource Control) layer configures priority, PBR (prioritisedBitRate), and BSD (bucketSizeDuration) for every logical channel so that lower priority channel can also get resource and bursting data can be sent in a short time. This paper firstly introduces application of token bucket algorithm in LTE system. And the test procedure is designed to test the algorithm. Test result shows that the algorithm is used in LTE system successfully. The algorithm has been used in TD-LTE radio frequency conformance testing instrument.

DCOP (Distributed Constraint Optimization Problem) is currently the most widely used in multi-robot communication algorithm problem, Adopt algorithm is a kind of algorithm which is relatively perfect; it can transport messages accurately under the harsh environment of communication. It is completely asynchronous algorithm, through analyzing algorithm for local agents to obtain the global optimal solution, in the comparison of each algorithm can see that ADOPT algorithm not only can well solve the problem of communication failure, and the algorithm set up mechanism of terminate detection, it can make the algorithm stops on the optimal solution, and effectively solve the deadlock problem. The text use ADOPT algorithm to analyze how to solve the problem of multi-robot communication failure, and improve the algorithm to take messages more accurately and effectively.

This paper proposes an Efficient Token based Opportunistic Routing called ETOR, which is an improvement to the token based coordination approach for opportunistic routing proposed by Economy[1]. In Economy, method used for finding the connected candidate order chooses neighbor as the next candidate by considering ETX of that neighbor towards the source but it does not consider the link probability between the relay candidate and neighbor to be selected. ETOR proposes variant methods for finding the connected candidate order in token based opportunistic routing by considering both the ETX of the neighbor towards source as well as ETX of the relay towards sending candidate which avoids weaker links between its intermediate nodes thereby improving the throughput and reducing the AA Ratio. We also propose a solution for reducing the number of hops traversed by the token, which in turn increases the token generation speed. Simulation results show that the proposed ETOR approaches perform better than Economy approach in terms of AA Ratio, number of hops traversed by the token and number of token traversals.

In the present paper, we propose a hierarchical algorithm to solve the group mutual exclusion (GME) problem in clusterbased systems. We consider a two-level hierarchy in which the nodes are divided in to clusters and a node in each cluster is designated as coordinator which is essentially the cluster head. The number of global messages per critical section entry in our algorithm depends upon the number of clusters in the system unlike most of the existing GME algorithms where it depends upon the total number of nodes in the system. Performance of the algorithm directly depends on the coherent behavior of nodes inside clusters. The results have been substantiated with extensive simulation. A fault tolerant extension of the algorithm has also been proposed in the present exposition.

A simplification of the mutual exclusion algorithm of Lycklama and Hadzilacos (ACM Trans Program Lang Syst 13:558---576, 1991) is presented. It uses only four nonatomic shared bits per thread to guarantee mutual exclusion with the first-come-first-served property. The algorithm is verified by assertional methods, aided by the proof assistant PVS. A variation with five bits per thread is also given. This variation may give better performance when the number of threads is large. The use of the proof assistant made it easy to transfer the proof of the main algorithm to the variation.

WOS: 000323038600001, Distributed mutual exclusion is a fundamental problem which arises in various systems such as grid computing, mobile ad hoc networks (MANETs), and distributed databases. Reducing key metrics like message count per any critical section (CS) and delay between two CS entrances, which is known as synchronization delay, is a great challenge for this problem. Various algorithms use either permission-based or token-based protocols. Token-based algorithms offer better communication costs and synchronization delay. Raymond's and Suzuki-Kasami's algorithms are well-known token-based ones. Raymond's algorithm needs only O(log(2)(N)) messages per CS and Suzuki-Kasami's algorithm needs just one message delivery time between two CS entrances. Nevertheless, both algorithms are weak in the other metric, synchronization delay and message complexity correspondingly. In this work, a new hybrid algorithm is proposed which gains from powerful aspects of both algorithms. Raysuz's algorithm (the proposed algorithm) uses a clustered graph and executes Suzuki-Kasami's algorithm intraclusters and Raymond's algorithm interclusters. This leads to have better message complexity than that of pure Suzuki-Kasami's algorithm and better synchronization delay than that of pure Raymond's algorithm, resulting in an overall efficient DMX algorithm pure algorithm.

This paper is Part II of a two-paper set which develops a finest-grain per-molecule timing treatment of molecular communication. We first consider a simple one-molecule timing channel with a molecule launch deadline, similar to but different from previous work ("Bits Through Queues") where the constraint was mean launch time. We also derive a number of results related to the {\em ordering entropy}, a key quantity which undergirds the capacity bounds for the molecular timing channel, both with and without token data payloads. We then conclude with an upper bound on molecular timing-channel capacity., 12 pages, 2 figures, 1 Table, in review at IEEE Transactions on Molecular Biological and Multiscale Communication

International audience; In this paper, we introduce a SMT-based method that automatically synthesizes a distributed self-stabilizing protocol from a given high-level specification and the network topology. Unlike existing approaches, where synthesis algorithms require the explicit description of the set of legitimate states, our technique only needs the temporal behavior of the protocol. We also extend our approach to synthesize ideal-stabilizing protocols, where every state is legitimate. Our proposed methods are fully implemented and we report successful synthesis of Dijkstra’s token ring and self-stabilizing version of Raymond’s mutual exclusion algorithm, we well as ideal stabilizing leader election and local mutual exclusion.

Distributed systems have been studied thoroughly. Many applications are based on huge systems and one of the main property an algorithm running on such systems should verified is fault-tolerance. This paper presents a new randomized algorithm to solve the handshake problem in a distributed system. This algorithm is designed for an asynchronous distributed network ofanonymous processes under the message passing communication protocol. In addition to its fault-tolerance, this algorithm is more effective than the existing ones thanks to its asynchronous aspect. To highlight its performance, we provide an experimental evaluation by comparing it to the most representative algorithm solving the handshake problem. The experimentation is done using Visidia, a tool for simulating and visualizing distributed algorithms.

Many distributed algorithms require a specific role to be played by a leader, a single node in the system. The choice of this node often has a direct impact on the performance. In particular, selecting a central node as the leader can significantly improve algorithm efficiency. Classical distributed algorithms require global information about the connectivity network to elect a centroid node. Thus, they are not suitable for large-scale distributed embedded systems with scarce computation, memory and energy resources. We present \algoNameNoSpace, an Effective and Efficient Approximate-Centroid Election algorithm that uses $O(1)$ memory space per node, $O(d)$ time and $O(mn^2)$ messages of size $O(1)$, where $n$ is the number of nodes, $m$ the number of connections and $d$ the diameter of the system. We evaluate our algorithm on the Blinky Blocks system using simulations. Experimental results show that \algoName scales well in terms of accuracy, execution time and number of messages. We show that \algoName is more accurate than the only existing algorithm with similar complexity results.

Mutual Exclusion is one of the most studied topics in distributed systems where processes communicate by asynchronous message passing. It is often necessary for multiple processes at different sites to access a shared resource or data called a critical section (CS) in distributed systems. A number of algorithms have been proposed to solve the mutual exclusion problem in distributed systems. In this paper, we propose the new algorithm which is modified from Garg"s algorithm[1] thus works properly in a fault-tolerant system. In our algorithm, after electing the token generator, the elected process generates a new token based on the information of the myreqlist which is kept by every process and the reqdone which is received during election. Consequently, proposed algorithm tolerates any number of process failures and also does even when only one process is alive.

Opportunistic networks are essentially distributed networks with transient connectivity among nodes. Nodes in opportunistic networks are resource constrained, mobile and opportunistically come in contact with each other. In such a distributed network, nodes may require exclusive access to a shared object or resource. Ensuring freedom from starvation is a challenging problem in opportunistic networks due to limited pairwise connectivity and node failures. In this paper, we review mutual exclusion algorithms proposed for generic mobile ad hoc networks (MANETs) and discuss their applicability to opportunistic networks. Further, we propose a novel token based algorithm and prove its correctness. Simulation results show that our algorithm is communication efficient as compared to other algorithms proposed for generic mobile ad hoc networks. We also propose a timeout based fault detection algorithm that exploits the intercontact time distributions.

In distributed systems,cooperating process essh are both local and remoter sources. Chance is very high that multiple processes makesimultaneous requests to the same resource. If the resourcerequires mutually exclusive access (critical section - CS), then some regulation is needed to access it for ensuring synchronizedaccess of the resources thatonly one process could use the resource at a given time. This is the distributed mutual exclusion problem. The problem of coordinating the execution of critical sections by eachprocessissolved by providing mutually exclusive access to the CS. Mutual exclusion ensures that concurrent processes make a serialized access to shared resources.Quorum-based algorithms offer the advantage of protocol symmetry, spreading effort and responsibility uniformly across the distributed systems. In thispaper, we have proposed a permission baseddistributedmutual exclusion algorithmwhichis an improvement of Maekawa’s algorithm. The number of messages required by the improvisedalgorithmis in the range 3Mto 5Mper critical section invocation whereMis the number of intersection nodes1 in the system. A reduction in number of message by restricting the communication of anynodewith the intersection nodes of the quorums, withoutany modification of the basic structure of the algorithm.

In this paper, we propose a token-based fully distributed algorithm with token-asking method for Distributed Mutual Exclusion (DME) in a computer network composed of N nodes that communicate by message exchanges. The main goal is to introduce a new class of token-based DME algorithms called info-based algorithms. In some previous algorithms, the request to enter a critical section is sent to all nodes because the token-holding node is unknown, but in this info-based algorithm some nodes know the token-holding node and lead critical section entering requests to it, directly. This algorithm uses a logical structure in the form of a wraparound two-dimensional array which is imposed on the interconnecting network. Usually, a request message for entering the critical section is sent vertically down in the array, and eventually sent to the token-holding node with the assistant of an informed-node (common node between the row consisting of the token-holding node and the column consisting of the requester node). The nodes invoking the critical section can obtain the token with fewer message exchanges in comparison with many other algorithms. Typically, the number of message exchanges is 4N+1 under light demand which reduces to approximately 2 message exchanges under heavy demand. A correctness proof is provided.

We propose a distributed mutual exclusion algorithm for mobile ad hoc networks. This algorithm requires a ring of cluster coordinators as the underlying topology. The topology is built by first providing clusters of mobile nodes in the first step and then forming a backbone consisting of the cluster heads in a ring as the second step. The modified version of the Ricart-Agrawala Algorithm on top of this topology provides analytically and experimentally an order of decrease in message complexity with respect to the original algorithm. We analyze the algorithm, provide performance results of the implementation, discuss the fault tolerance and the other algorithmic extensions, and show that this architecture can be used for other middleware functions in mobile networks.

Providing a reliable group communication in a mobile ad hoc network (MANET) is a challenging task. The dynamic nature of this network makes it highly unreliable. Moreover, the future MANETs such as military applications are so large that the disaster recovery scenes would become unmanageable. For better utilization of the system, nodes within the close proximity need to communicate with each other quite often than those which are far apart. To address these issues and to provide a reliable and manageable group communication, this paper proposes a novel token circulation scheme using an adaptive secondary clusterhead-aided clustering algorithm. The token circulation scheme handles token loss and node failures, while the clustering algorithm provides variable diameter clusters, within which group communication is provided. The primary clusterhead is chosen according to the connection degree and mobility of each node. A secondary clusterhead is also set inside each cluster to take charge of part of the duties of the primary clusterhead, such as clustering functionalities, storage of information relating to clustering, token monitoring, etc. Criteria for comparing the algorithms with the existing algorithms include the average time required to complete a round, number of bytes sent per round, number of nodes visited per round, member change frequency in clusters and rate of change of clusterheads. Simulation results show that the proposed token circulation scheme in combination with the clustering algorithm gives better results in comparison with the existing schemes.

This paper aims towards designing a new token-based mutual exclusion algorithm for distributed systems. In some of the earlier work, token based algorithms for mutual exclusion are proposed for the distributed environment assuming inverted tree topology. In a wireless setup, such a stable, hierarchical topology is quite unrealistic due to frequent link failures. The proposed token-based algorithm works for processes with assigned priorities on any directed graph topology with or without cycles. The proposed algorithm, in spite of considering priorities of processes, ensures liveness in terms of token requests from low priority processes. Moreover, the algorithm keeps control message traffic reasonably low. The simulation results exhibit the performance of the proposed algorithm under varied contexts besides presenting a comparative performance with other recent algorithms for mutual exclusion like FAPP (Fairness Algorithm for Priority Process).

Many atomic broadcast algorithms have been published in the last 20 years. Token-based algorithms represent a large class of these algorithms. Interestingly, all the token-based atomic broadcast algorithms rely on a group membership service and none of them uses unreliable failure detectors directly. This paper presents the first token-based atomic broadcast algorithm that uses an unreliable failure detector instead of a group membership service. It requires a system size that is quadratic in the number of supported failures. The special case of a single supported failure (f = 1) requires n = 3 processes. We experimentally evaluate the performance of this algorithm in local and wide area networks, in order to emphasize that atomic broadcast is efficiently implemented by combining a failure detector and a token-based mechanism. The evaluation shows that the new token-based algorithm surpasses the performance of the other algorithms in most small-system settings.

In token-based distributed mutual exclusion algorithms a unique object (token) is used to grant the right to enter the critical section. For the movement of the token within the computer network, two possible methods can be considered: perpetual mobility of the token and token-asking method. This paper presents a distributed token-based algorithm scheduling mutually exclusive access to a critical resource by the processes in a distributed network. This network is composed of N nodes that communicate by message exchanges. The proposed hybrid algorithm imposes a logical structure in the form of wraparound two-dimensional array on the network. It applies the concept of perpetual mobility of the token in columns and token-asking in rows of the array. The major purpose of the algorithm is to increase the scalability property and decrease overhead due to additional communication in a system with at least one unresponded critical section request at any given time. In this status, typically, the number of message exchanges is between N and 2 N under light demand and reduces to N message exchanges under heavy demand. Therefore, it outperforms lots of well known algorithms in terms of number of messages exchanged. The algorithm satisfies safety and liveness properties.

Self-stabilizing distributed control is often modeled by token abstractions. A system with a single token may implement mutual exclusion; a system with multiple tokens may ensure that immediate neighbors do not simultaneously enjoy a privilege. For a cyber-physical system, tokens may represent physical objects whose movement is controlled. The problem studied in this paper is to ensure that a synchronous system with m circulating tokens has at least d distance between tokens. This problem is first considered in a ring where d is given whilst m and the ring size n are unknown. The protocol solving this problem can be uniform, with all processes running the same program, or it can be non-uniform, with some processes acting only as token relays. The protocol for this first problem is simple, and can be expressed with Petri net formalism. A second problem is to maximize d when m is given, and n is unknown. For the second problem, the paper presents a non-uniform protocol with a single corrective process., 22 pages, 7 figures, epsf and pstricks in LaTeX

Adaptation is a desirable requirement in a distributed system as it helps the system to perform efficiently under different environments. For many problems, more than one protocol exists, such that one protocol performs better in one environment while the other performs better in another. In such cases, adaptive distributed systems can be designed by dynamically switching between the protocols as the environment changes. In this work we propose an adaptive distributed mutual exclusion scheme that dynamically switches between two token based distributed mutual exclusion protocols; the Raymond's algorithm [15] and the Martin's algorithm [13]. Algorithms are proposed for switching in both directions and their correctness are proved. For each switching algorithm, it is shown that no more than one node can access the shared resource during the switching and no deadlock happens during the switching.

This note proposes a new version of the bakery algorithm that: (i) assures fair tie-breaking when two or more processes choose same token number; and (ii) bounds the token numbers within the range [-n,n]. The algorithm is simple and uses one additional shared bit.

Problem statement: The communications domain has utilized the implementation of protocols for a wide spectrum of applications. This encompasses Medium Access Control (MAC) protocols. MAC protocols have been extensively researched from several angles. This encompasses the implementation in the area of Wave Division Multiplexing (WDM) networks and Mobile Adhoc Networks (MANET). The relevance of intelligence in sustaining the pre-requisites for dynamic reconfiguration has gained an integral attention in MANET. Approach: The implementation of Token Ring in MANET can be correlated to its complementary implementation in IP networks. In this paper, the limitation of Token Ring algorithm for IP networks in the context of intelligent processing has been researched extensively. An enhanced Token Ring protocol governed by intelligent processing has been implemented in this paper. The core of the new protocol is based on the circulation mechanism of the token. As opposed to the traditional circulatory mechanism, a software agent is designed to become an intelligent circulatory agent is this research. The developed software agent is utilized to implement prioritized token access subject to the traffic type. Each station is coupled with a software agent who cohesively collaborates to assign the token. Results: The proposed agent and the enhanced Token Ring implementation have been extensively verified through simulation experiments. A complete circulation of the ring is defined upon all nodes being visited at least once. Discrete-event simulation models were developed and deployed for the purpose of performance analysis. The results acquired validated the improved results of the new software agent based implementation. The performance metrics studied were average delay and average buffer utilization. Conclusion: The proposed algorithm has enabled to derive an ideal balance between the complexity of intelligent processing and the versatility of managing the token ring.

This paper addresses the @?-Exclusion problem for mobile ad hoc networks. The @?-Exclusion problem, a generalization of distributed mutual exclusion problem, involves a group of processes, each of which intermittently requires access to one of @? identical resources or pieces of code called the critical section (CS). This paper presents a consensus-based mobility-aware @?-Exclusion (LE) algorithm that operates asynchronously and copes explicitly with arbitrary (possibly concurrent) topology changes associated with such networks. The algorithm can tolerate link changes or failures, sudden crashes or recoveries of at most @?-1 mobile nodes. The algorithm is based on collection of enough consensuses for a mobile node intending to enter CS, and uses diffusing computations for this purpose. This paper presents a simulation to demonstrate that the proposed algorithm, as compared to the k-Reverse Link (KRL) algorithm, is quite effective to variety of operating conditions, and is highly adaptive to frequent and unpredictable topology changes due to link changes or failures.

In this letter we give a lower bound on the worst-case time complexity of Dijkstra's three-state mutual exclusion algorithm by specifying a concrete behavior of the algorithm. We also show that our result is more accurate than the known best bound.

The group mutual exclusion problem is a generalization of mutual exclusion problem such that a set of processes in the same group can enter critical section simultaneously. In this paper, we propose a distributed algorithm for the group mutual exclusion problem in asynchronous message passing distributed systems. Our algorithm is based on tokens, and a process that obtains a token can enter critical section. For reducing message complexity, it uses coterie as a communication structure when a process sends a request messages. Informally, coterie is a set of quorums, each of which is a subset of the process set, and any two quorums share at least one process. The message complexity of our algorithm is O(|Q|) in the worst case, where |Q| is a quorum size that the algorithm adopts. Performance of the proposed algorithm is presented by analysis and discrete event simulation. Especially, the proposed algorithm achieves high concurrency, which is a performance measure for the number of processes that can be in critical section simultaneously.

A mobile host has small memory, relatively slow processor, low power batteries, and communicate over low bandwidth wireless communication links. Existing mutual exclusion algorithms for distributed systems are not enough for mobile systems because of several limitations. In this study, a mutual exclusion algorithm that is more suitable for mobile computer systems is developed. The algorithm tends to minimize the number of messages needed to be transmitted in the system, by reducing the number of sites involved in the mutual exclusion decision, and reducing the amount of storage needed at different sites of the system.