Matchmaking players is an important problem in online multiplayer games. Existing solutions employ client-server architecture, which induces several problems. Those range from additional costs associated with infrastructure maintenance to inability to play the game once servers become unavailabe (due to being under Denial of Service attack or being shut down after earning enough profit). This paper aims to provide a solution for the problem of matchmaking players on the scale of the Internet, without using a central server. In order to achieve this goal, the SelfAid platform for building custom P2P matchmaking strategies is presented. After the developer creates a service algorithm defining the matchmaking behavior specific to his/hers case, the SelfAid platform designates a number of player machines to execute the service. Furthermore, the number of designated machines adapts to the demand. SelfAid uses only spare resources of player machines, following the trend of sharing economy. A distributed algorithm is presented and its correctness is proven.

In communicating resource systems (CRS), a set of independent, hierarchically composed resources communicate to realize a business process. Examples of CRSs include RESTful Web services, cloud computing platforms and hierarchical distributed systems. Unfortunately, their complexity, distributed nature, and usually long lifespan can lead to problems like livelocks, deadlock occurrences and invocation loops. This makes CRSs hard to maintain and manage; it also leads to a loss of QoS or system failures. Moreover, it is important to take into account, in system management, the exact way how the system gets to some desired or undesired state. Therefore, it is crucial to analyze processes, executed in a system to find and fix the above problems. Unfortunately, CRS process models are hardly ever available. Therefore, we present a new distributed algorithm, dRMA, discovering process models from CRS event logs. In order to reduce the representational bias between the discovered process model and the real process, we have defined a Communication Net, which can express features of CRSs: directed communication channels, hierarchy, and a resource perspective. Finally, we have evaluated dRMA on a cluster, and have showed that distributing jobs can significantly reduce the time of process model discovery.

Composition of Web Services (WS) into business processes (BP) often results in occurrence of defects in a process: implicit dependencies, incorrect contexts, non-optimal or bottlenecked workflow, and deadlocks. To deal with these problems, WS Mining (process mining in SOA) research provides methods and tools to discover, evaluate and enhance real world processes basing on a process model discovered from a log. Unfortunately, current research in this field only concerns SOAP-WS which are not as well-suited as RESTful-WS in the context of current research trends like Internet of Things or Web 2.0. WS Mining methods and tools should consider RESTful-WS where functionality of the system is expressed in the form of resources and relationships among them. In this paper we show the idea of discovering process models for interacting RESTful-WS with respect to both workflow and resources perspectives. We introduce extended version of the α algorithm (AA), RESTful-WS mining algorithm (RMA), which discovers hierarchical process models and resource-oriented perspective of a process including local and global behavior. Finally, we present a brief discussion on how RMA decomposes a problem into smaller ones, significantly reducing the execution time in real time scenarios.

D-ReServE increases reliability of SOA-based systems in case of failure occurrence. The fault-tolerant information in D-ReServE is stored in the Stable Storage, which available space depletes with time. Thus, in this paper we propose a garbage collection protocol for D-ReServE that allows the periodic purging of the Stable Storage, and discuss the challenges of garbage collection due to the nature of SOA systems.

The MANET liveness property ensures that no operative host in an ad hoc network is permanently isolated, and for networks that fulfill the property a few crash-tolerant broadcast protocols have been proposed. However, the protocols proposed till now guarantee that only at least an arbitrary majority of operative hosts receives each disseminated message, and one of these protocols has been further modified to fulfill the properties of regular reliable broadcast. Moreover, it has also been proved that the minimum time of direct connectivity between hosts, and thus the correctness of all these protocols, depends on the total number of hosts in a network and on the total number of messages that can be disseminated by each host concurrently. In this paper, we propose a novel uniform reliable broadcast protocol that works correctly, even though the minimum time of a direct connection between hosts allows them to exchange at least only two messages, which makes the correctness of this protocol independent of the total number of messages that can be disseminated by all nodes in a network.

In the mobile environment, weak consistency replication of shared data is the key to obtaining high data availability, good access performance, and good scalability. Therefore new class of consistency models, called session guarantees, recommended for mobile environment, has been introduced. Session guarantees, called also client-centric consistency models, have been proposed to define required properties of the system regarding consistency from the client's point of view. Unfortunately, none of proposed consistency protocols providing session guarantees is resistant to server failures. Therefore, in this paper checkpointing and rollback-recovery protocol rVsMW, which preserves monotonic writes session guarantee is presented. The recovery protocol is integrated with the underlying consistency protocol by integrating operations of taking checkpoints with coherence operations of VsSG protocol.

This paper considers the reliability of software Distributed Shared Memory systems where the unit of sharing is a persistent read-write object. We present art extended coherence protocol for causal consistency model, which integrates replication management with independent checkpointing. It uses a trove! coordinated burst checkpoint operation in order to replicate consistent checkpoints of shared objects in local memory of distinct system nodes. No special reliable hardware devices are required. The protocol offers high availability of shared objects with limited overhead and ensures fast recovery in case of multiple node failures. lit case of the network partitioning all the processes in a majority partition of the system can continuously access all the objects.

As is well known any algorithm correct in an asynchronous shared memory setting (physically shared memory) can be directly applied in distributed shared memory (DSM) systems provided that the latter guarantees strong consistency (atomic or sequential) of replicas. Generally however, in DSM systems, weaker consistency models (causal, processor, PRAM, etc.) are often considered to improve the performance. A weakening consistency model may however imply the incorrectness of the algorithm. So we face a consistency requirement problem, the problem of finding the weakest consistency model of DSM that is sufficient and necessary for algorithm correctness. We consider a reliable DSM environment, and present a complex consistency model comprising three elementary models: sequential consistency, coherence and PRAM consistency. This complex model is then applied to Dijsktra's (1965) algorithm for mutual exclusion of n processes, one of the first solutions to a fundamental problem in both centralised and distributed operating systems. In the resulting algorithm, coherence and PRAM consistency are associated with some write operations performed at shared memory locations. As concurrent execution of write operations with weaker consistency models is more efficient when compared to the execution of strongly consistent operations, the proposed solution reduces synchronisation delay (mutual exclusion overhead) and thereby increases system throughput. The presented model is proven to be sufficient for algorithm correctness. Moreover, the algorithm is shown to be optimal in the sense that further relaxation of any write operations semantics violates progress (liveness) or safety of the algorithm.

As has been shown, the polygon time structure overcomes the main limitations of the interval time structure, and allows one to verify communication protocols, in which the explicit concurrency of both competing and supporting events is considered. The authors apply the polygon time structure to the verification of dynamic properties (like livelocks) of a simple protocol. As a result, they show that an application of the previously used interval time structure may lead to the evaluation of a protocol as incorrect, while it is livelock free.

A problem of deadlock avoidance in store-and-forward networks with at least two buffers per node is considered for fixed as well as dynamic routing. For both cases polynomial time, centralized deadlock avoidance algorithms are proposed and shown to be optimal in a sense of possible buffer utilization. When the number of buffers is equal to one for each node the problem is known to be NP-complete, thus, unlikely to admit a polynomial-time algorithm. The presented results may be also interesting for other applications, some massively parallel computer systems being one of the examples.>

Termination detection constitutes one of the basic problems of distributed computing, and many distributed algorithms have been proposed to solve it, but all these algorithms consider a very simple model for the underlying application programs: for processes of such programs, nondeterministic constructs are allowed, but each 'receive' statement (request) concerns only one message at a time. A more realistic and very general model of distributed computing is first presented, allowing a request to be atomic on several messages and to obey AND/OR/AND-OR/k-out-of-n/etc. request types. Within this framework, two definitions of termination are proposed and discussed. Then, accordingly, two distributed algorithms for detecting these terminations are presented and evaluated; they differ in the information they use and in the time they need to claim termination.>

This paper deals with the problem of store-and-forward deadlock prevention in store-and-forward networks. The presented solution uses time stamping of all messages in the network, and a nonpreemptable message exchange mechanism. By combining these ideas, a new distributed flow control procedure is derived which guarantees that all messages are delivered to their own destinations, thus avoiding both deadlock and livelock without any message loss. It is shown that some properties of this procedure depend on the policy of the allocation of exchange buffers to nodes. On the one hand, an optimal allocation strategy is presented which results in a maximally optimal deadlock prevention procedure. The procedure is network sizeand topology-independent and allows unrestricted packet routing. On the other hand, the allocation of one exchange buffer per node is discussed, which, even if not optimal, makes the derived deadlock prevention procedure completely independent of network reconfigurations. The last feature is extremely important from the practical point of view and, therefore, such a solution is strongly recommended. When compared to store-and-forward deadlock prevention procedures described so far, which lack some or all of these desirable properties, the procedure presented here behaves favorably. However, it imposes other drawbacks, i.e., the possibility of extra hops as a result of exchange operations. It is argued that this drawback appears rarely in practice, and some strategies which aim at a reduction of it are proposed.

This correspondence is concerned with the prevention of four types of deadlock in store-and-forward networks, i.e., progeny, copy-release, reassembly, and resequence deadlocks. The approach presented makes use of time stamping of all messages and generalizes the method of store-and-forward deadlock prevention.