From: Long Hai Vu Sent: Tuesday, February 28, 2006 9:27 AM To: Indranil Gupta Cc: Long Vu Subject: CS598ig review 02/28 CS598IG-Spring 2006 Name: Long Vu REVIEW PAPERS A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems In this paper, authors propose the Sigma protocol which is implemented inside a dynamic P2P DHT. They try to adopt queuing as well as cooperation between peers and replicas to get the quorum consensus scheme. According to the system model, replicas are always available for peers’ access; however, the replicas’ internal states may be randomly reset to keep the transparency for peers. In the proposed context, the number of peers can be very large; authors also assume that client is not malicious and messages are never forged but could be lost and replicated. The key points of Sigma protocol is using logical replicas (peer could only see the logical view of replicas without knowing the inside arrangements and states) and quorum consensus to overcome the dynamisms of the system. There are some contributions: - They invest a straw-man protocol and point out the reason of system’s degradation: the high variation of network latency between clients and replica - They also show that there exists a cooperative strategy between clients and replicas to deal with network latency and contention. The strategy could provide high scalability and robustness - They present the informed back-off mechanism to handle the random reset problem of replicas in the straw-man protocol Mutual exclusion is the central part of any systems. To provide mutual exclusion, we have to deal with huge variance of network latency, high churn rate, and unpredicted dynamic number of replicas. Sigma protocol proposed in this paper could solve part of distributed exclusion inside P2P DHT. Sigma deal with failure by two techniques: back-off and lease. The idea of logical replicas could be extended in future work. Scalable and Dynamic Quorum Systems In this paper, author focus on issues related to quorum system in term of complexity of the system and its implementation in dynamic environment. There are two main contributions of this paper: - The first contribution is that finding the quorum in case of random failures. Given the distributed and peer to peer model, find the quorum systems while taking into account the network implementation. - The second one is Dynamic Paths which works for dynamic and scalable environment with high churn rate. Dynamic Paths is the first quorum system which has low load, high availability, and good probe complexity. This approach could be viewed as a dynamic adaptation of the Paths system. From: Bach Duy Bui Sent: Tuesday, February 28, 2006 10:54 AM To: Indranil Gupta Subject: 598ig review 02/23 A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems 1. Summary In this paper, the authors propose a solution for mutual exclusion problem in peer-to-peer systems. The system model considered in this protocol assumes (1) the availability of replicas which can be randomly reset (2) the number of clients is unpredictable and can be very large (3) clients and replicas communicate via message across unreliable channels. First, by investigating the ALOHA-like strawman protocol, the authors show that the high variation of network latency between clients and replicas is responsible for the system degradation. Two problems are pointed out: (1) client requests reach different replicas at different time (2) clients keep on trying when collision occurs. To solve the problem, the authors propose (1) installing a queue at the replicas and reshuffling them to wards a consistent view (2) enforcing clients into a state of active waiting. To deal with problem of unreliable system and communication, the authors propose two mechanisms: (1) informed backoff: is the way to rebuild a restarted replica's state without overloading those healthy replicas, (2) renewable lease: when the granted lease is expired, it is granted to next queued client. 2. Comments By using the combination of multiple techniques i.e. waiting queue and yield command; informed back-off and renewable lease, the protocol demonstrate that it can work every good under the condition of unpredictable crashing clients/replicas and unreliable communication. The using of queue which store information of each client at each replica is not scalable in term of number of clients and number of replicas. The main advantage of the protocol based on the collaborative nature of clients who send YIELD when nobody won. It is, however, skeptical that this process is convergent in every situation. A counter example is: a system with two clients and 100 replicas, in the first round each client wins 50 replicas and in queue of the other 50, since there is no winner they will yields them. In the second round they continue receiving only 50 replicas each. The process goes on without resolving contention. This creates a kind of deadlock. A Sqrt(N) Algorithm for Mutual Exclusion in Decentralized Systems 1. Summary This paper solves the problem of creating mutual exclusion in a distributed computer network. The proposal algorithm uses c*sqrt(N) messages to establish mutual exclusion given an error-free underlying communication networks. The algorithm is based on the fact that, if node i locks a set of resource, no other node can capture all its required number of resources. To avoid deadlock when more than one node simultaneously requests mutual exclusion, a node will yield to others if the priority of its request is lower than that of any other conflicting requests. The authors prove the correctness of mutual exclusion creation and deadlock-free characteristic of the algorithm. Two near-optimal methods to create a dominating set of resources for each node are proposed. 2. Comments No practical algorithm for creating dominating set of resources for each node is mentioned. This process would require much overhead and computation. It would be harder if taken into account the fact that nodes and resources behavior unpredictable in reality. Since the algorithm is out perform the others under the assumption of the existence of such sets, the authors should investigate on how this assumption can be realized in more detail. From: Anthony Cozzie [acozzie@gmail.com] Sent: Tuesday, February 28, 2006 4:13 AM To: Indranil Gupta Subject: 598ig review 02/28 Anthony Cozzie, reviews 2/28/2005 A sqrt(N) algorithm: This paper hinges upon the result that it is possible to give N objects sqrt(N) neighbors such that every pair of nodes will share at least one neighbor. Therefore, if a node can lock all of its neighbors it can guarantee mutual exclusion. Interestingly this paper was written about the same time as FLP's impossibility result for these sort of things. As a practical protocol in a faulty asynchronous system it seems rather poor, as even 1 new node entering the system would force a new computation of groups, but in say a supercomputer or a cluster environment it might prove useful. A practical distributed mutal exclusion protocol: This is mutual exclusion built on top of a DHT. The DHT forms a strange server model: the server always exists and is never down, as a key always maps to some node in the system, but the node may change and thus a node may forget about its obligations. Their protocol, Sigma, proceeds by acquiring M locks. They analyze the rate at which nodes leave a system and conclude that, for example, a node that acquired 24 / 36 locks would have an extremely (10^40) small chance of error. The problem with this is that as contention rises the throughput falls through the floor. They deal with this by having nodes that realize they have acquired 1 part of the lock but have no chance to actually get the lock (ex: I have 2 / 36 locks, node 7 has 12 / 36 locks) give up their slot to nodes that have a larger number of locks. From: Mike Earnhart [mearnhart@gmail.com] Sent: Tuesday, February 28, 2006 9:02 AM To: Indranil Gupta Subject: 598ig review 02/28 Michael Earnhart February 28, 2006 CS598 IG Summary A Practical Distributed Mutual Exclusion Protocol And A (N)^(1/2) Algorithm for Mutual Exclusion in Decentralized Systems In a practical distributed mutual exclusion protocol they develop the Sigma protocol to provide a highly available majority-based consensus system. They show the well-known problems in such protocols through an analysis of the strawman protocol. They conclude that the poor performance of the strawman protocol is due to variance of network latency between a client and each replica. Their system starts by send request messages to all replicas. These messages are handled by the onrequest at each replica. It will then determine whether to vote or queue the request based on whether it had voted previously. Every replica then sends back a response message indicating how the replica handled the request message. The client receives the response message and is able to measure its position in the system queue for mutual exclusive access to a resource. Three states are mentioned that can be determined by the client, it won by quorum consensus, someone else won, or no one won. In the case of the third outcome the system could be heading toward dead lock and therefore must take measures to avoid it. Therefore it provides a yield message to indicate to all the supportive replicas that the client is forgoing its right for mutual exclusion in the hopes of avoiding dead lock. Beyond this mutual exclusion protocol they also provide a mechanism for determining failed replicas within the system. The tools they develop are informed backoff and lease. Finally they provide an analysis of their protocol for service, safety, and liveliness. Their experimental results show a very stable protocol even when the replica base is very unstable and also extremely good throughput given high request rates. Both the throughput and the fault tolerance are quite amazing. Being able to handle 30 second lifetimes and maintain any functionality is fairly amazing. Beyond that the comparison of strawman to sigma given loads exceeding 4 requests/second show not so much as an improvement but an ability difference. Strawman cannot handle more than 4 requests/sec where as sigma seems to level out around that point at a throughput of 4 – 5 requests/sec. My issues with this paper are the lack of security concern, and a too much focus on their algorithm which does not seem special. First they state clients are not malicious and fail stop. No attackers imply an optimal case and if just one client is malicious the system will fail. Therefore their experiments show extreme scenarios such that no one is malicious there is high request rates and significant churn. However they do not experiment with even one malicious node because it would cause a breakdown. Also along the same lines they claim that messages cannot be forged but provide no means for explaining that claim. The problem with the focus on their algorithm is that clearly there was a page limit to this paper and the need to spend a half of a page on pseudo code is not there. More detail about security and less about their request/release/yield algorithm would have been nice. In the Square-root of N algorithm for mutual exclusion in decentralized systems they use only partial agreement to provide mutual exclusion. The only stipulation is that the set of partial agreement must be selected carefully to make sure it contains enough members to guarantee agreement. They use request/locked/failed/inquire/relinquish messages to provide defenses against dead-lock and various other issues with a distributed mutual exclusion algorithm. The paper then describes several examples and provides an excellent comparison amongst other algorithms in this area. They are very strong in their examples such that they show conclusively that their algorithm works. I also appreciate the layout of their comparison chart so that their algorithm is centered which makes it easy to see how well it does versus either of the two alternatives. Finally I would see the partial agreement as its greatest strength but building the sets would probably be its greatest trouble spot. From: Mehedi Bakht Sent: Tuesday, February 28, 2006 8:51 AM To: Indranil Gupta Subject: 598 IG review 02/28 netid : mbakht2 Title: A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-peer Systems. Summary: This paper presents Sigma, a quorum based distributed mutual exclusion protocol for dynamic peer to peer systems. The paper first gives a straightforward design of a mutual exclusion protocol (analogous to ALOHA). In this simple design, a client sends request to enter critical section (CS) to all the replicas. Each replica grants access to the first request it has received. If a client gets permission from a majority of replicas, it becomes the winner. If not, it releases the permissions it has obtained, backoff for some time and retries the process. The paper shows that this naive protocol has good safety property. However, the paper shows the performance of this protocol is poor. This is because requests from different clients may arrive at different replicas in different order, and there is no cooperation between clients and replicas. Sigma protocol improves the performance by installing a request queue at each replica. When a client understands from a lack of enough support that nobody is winning, it can yield the permissions it has obtained. The replicas can then grant permission to the next client. This is supposed to achieve much more consistent view between the replicas, which means the system succeeds in selecting a winner to enter the CS. If a client infers that someone else is winning, it will wait instead of retry. It does not need to retry because the replicas already have its request and will grant permission to it once other winners have finished the CS. To cope with various failures in a dynamic p2p system, the paper also proposes various techniques. Experimental results from a fully implemented and deployed version of Sigma protocol is also discussed at the end of the paper. Comments: The paper seemed very well written, lucid and to- the-point. I have some confusion about the procedure for achieving consensus. The YIELD message may try to reshuffle the queue, but what is the guarantee that it will lead to a consensus in a certain number of rounds? The paper provides no mathematical or formal guarantee. Instead, it just asserts that is will quickly settle, “as verified in our experiments”!! Due to varying nature of network latencies, I can think of certain cases where the protocol may result in a sort of deadlock. Title: Scalable and Dynamic Quorum Systems Summary: The paper presents an intensively algorithmic model to achieve a quorum system called Path. The paper first presents non-adaptive and adaptive algorithm to construct a quorum system that can tolerate a level of node failures. The paper then presents the dynamic version of Paths quorum system which exhibits fault-tolerance and churn-resistance, which are two important characteristics of Peer-to-Peer network. Comments: This paper seemed a bit too mathematically complex for me. I really had a hard time to grasp its contents. So I am in no position to comment about all the analyses they have presented. My only observation is that real world scenarios do not always correspond to nice algorithmic models. Some experimental results from deployment of Paths would have been really appreciated. From: Muyuan Wang [mwang2@uiuc.edu] Sent: Tuesday, February 28, 2006 8:42 AM To: Indranil Gupta Subject: 598ig review 02/28 A sqrtN Algorithm for Mutual Exclusion in Decentralized systems This paper presents a distributed algorithm that creates mutual exclusion using c*sqrtN messages, where c is a constant between 3 and 5. The algorithm is symmetric and allows fully parallel operation and a node removal. It is optimal in terms of the number of messages used to create mutual exclusion among fully distributed algorithms, where the term distributed is used to mean that each node serves as an arbitrator for the same number of nodes. In this algorithm, each node executes an identical algorithm. If node i locks all members of S_i, no other node can capture all its members because for any combination of i and j, 1<=i, j<=N, S_i intersect S_j = empty set. The algorithm is described as follows: 1) When node i invokes mutual exclusion, it sends a REQUEST message to every member of S_i. 2) When receiving a REQUEST, a member node of S_i marks itself locked for the REQUEST if it is not currently locked for another REQUEST, or place the REQUEST in the waiting queue. 3) When a node receives an INQUIRE, it returns a RELINQUISH if it knows that it will not succeed in locking all its members. 4) When a node receives a RELINQUISH, it relieves itself of the current locking REQUEST and then locks itself for the most preceding REQUEST in the waiting queue. 5) If all members of S_i have returned a LOCKED message, node i enters its critical section. 6) When complete the critical section, node i sends a RELEASE message to each member of S_i. 7) When a node receives a RELEASE message, it relieves itself from the current locking REQUEST. 8) Repeat the above steps for each mutual exclusion request. A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems This paper proposes the Sigma protocol implemented inside a dynamic P2P DHT, which is able to avoid the challenges of ensuring mutual exclusion in P2P systems. The key idea is to adopt queuing and cooperation between clients and replicas to enforce quorum consensus scheme. Quasi-consistency and cooperation between clients and replicas circumvent the large variance of network latency and high contention. The protocol is scalable with system size, and is robust to contention, it also can avoid failure by using informed backoff and lease, as well as making protocol fault-tolerant. The protocol is also quasi-RCFS, and can guarantee safety with high probability. The liveness is ensured by using lease. This protocol is shown to be resilient to network latency variance and fault-tolerant, by experiments on different network topology models, under various contention rates. From: Hussam Hasan Abu-Libdeh Sent: Tuesday, February 28, 2006 2:38 AM To: Indranil Gupta Subject: 598ig review 02/28 The two papers that i will review are: 1. A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems. 2. Scalable and Dynamic Quorum Systems. A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems: ---------------------------------------------------------------------------------------- The motivation for this paper is: Suppose that we have a P2P system, and we have multiple nodes trying to access a set of resources that are stored at some other nodes in the system. When trying to provide access to resources for different nodes we find ourselves facing several challenges such as 1. Huge variance of network latency 2. Unpredictably large number of clients 3. High dynamism This paper proposes "Sigma" which is a practical, efficient, and fault-tolerant protocol for mutual exclusion in P2P systems. It first tries to solve this problem in a simple naive way (the strawman protocol) that is built on top of the ALOHA protocol; however, they prove that this approach doesn't perform well due to two things: The variance of network latency between a client and each replica; and the greedy behavior of the clients (they would keep on retrying when collision occurs, thus nobody can win). The key points of Sigma protocol are to use logical replicas and quorum consensus to deal with system dynamisms. Quasi-consistency and cooperation between clients and replicas circumvent the large variance of network latency and high contention. Sigma also gracefully deals with failure by two techniques: informed back off and lease, making protocol fault-tolerant. With various tests and simulations, the paper verified that this protocol offers high performance in heterogeneous network condition and various contention rates. In a practical environment, the failure handling mechanism works well with negligible performance penalty and moderate communication overhead. -------------------------------------------- Scalable and Dynamic Quorum Systems : -------------------------------------------- I have to admit, the name quorum threw me off in the beginning. However, it simply means set of sets of elements of a universe that are disjoint. Quorum systems have been used in the study of distributed control and management problems such as mutual exclusion, data replication protocols and secure access control. In many applications of quorum systems the underlying universe is associated with a network of processors, and a quorum is employed by accessing each of its elements. The paper builds quorum systems that are ?t in a dynamic peer-to-peer model. The authors allow only two types of events in these systems: node entrance/leaving the system, and node failure (temporary halt). The main topic discussed in this paper is the "Paths quorum system" and after mathematically analyzing, the authors concluded that it has excellent adaptive and non-adaptive probing algorithms. The Paths system offers excellent balance between different quality measures, because it has optimal load, high load, and simple probing. All this makes it a perfect candidate for use in dynamic settings (such as large scale p2p apps). Personal thought: I really don't have much to say here. Although, if i have to say anything i'd say that i enjoyed the first paper more than the second one (even though the second provides the foundation for the first :-) ) From: Ravishankar Sathyam Sent: Tuesday, February 28, 2006 12:40 AM To: Indranil Gupta Subject: 598ig review 2/28 Ravi Sathyam A Sqrt N Algorithm for Mutual Exclusion in Decentralized Systems Summary: This paper presents an algorithm that uses only O(sqrt(N)) messages in order to create Mutual Exclusion in a network. The algorithm is basically as follows: If node k locks all members of a particular set of nodes S, then it had achieved mutual exclusion! This is because no other node can capture all of the members of S, due to the pairwise non-null intersection property between two corresponding sets of two nodes. Hence, a node will try to lock all of the members (by sending a REQUEST message whose timestamp determines priority) of its corresponding set S and if it succeeds, then it can enter its critical region. Otherwise, if a node in the set S is locked by another node, it places this new request in a queue (known as the Waiting Queue). If this message is preceded by the current message, or by any other Outstanding Request (another message in the Waiting Queue), then a FAILED message is sent back to the node that initiated the request. If this message is not preceded by anything else, an INQUIRE message is sent to the initiator node to see if the node has succeeded in locking all of its members. When this is received by an initiator node, then it can return a RELINQUISH message if it already knows that it cannot lock all members of S (and relinquishes its member set of nodes to a REQUEST message from another node, thus preventing deadlock). If a node has locked all of the members of its corresponding set S, and has completed its critical section, then it sends a RELEASE message to all of the members of S. When these members receive the RELEASE message, they relieve themselves from their locked position, delete the locking REQUEST, and relock themselves for the next highest priority REQUEST in the WAITING QUEUE. The fact that two corresponding sets of any two nodes k and p are not mutual exclusive (that is, their intersection is not null), forms the basis of the proof that this algorithm guarantees mutual exclusion. Also, we have already seen that deadlock is not possible. The paper then goes on ways to select corresponding sets for various nodes. The paper then explores message traffic under two conditions: a) Light Traffic – where a total of 3(K-1) messages are required for mutual exclusion, and b) Heavy Traffic – where a total of 4(K-1) messages are required (Please note that K is the size of these corresponding sets). The paper also goes on to show that under the failure of a particular node, it would take O(sqrt(N)) messages for another node to regain the lost dynamic and modified static information. Comments: I did not understand how these sets could be created, and hopefully will understand this from the lecture. A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems Summary: This paper presents and implements a mutual exclusion protocol on top of a p2p DHT. This can be achieved by implementing a set of Logical Replicas upon which a Quorum Consensus Protocol can grant access to the Critical Section. From a client’s perspective, these replicas are always “live” even if a node behind a replica crashes (it is replaced by another node). The system model is basically as follows: Replicas are always available (regardless of their physical states), clients can be large, unpredictable and malicious, and clients and replicas communicate via messages across reliable channels. The way the system works is that if any client wants to enter the critical section, it will send a request to each of the replicas and wait for responses. Replicas then either grants permission or reject the request. Replicas grant permission by issuing renewable leases to the clients. This is to counter clients who crash while in Critical Section (the lease will then be passed on to the next waiting client). A client who has obtained majority permissions (majority factor m = n/2) is the winner (loser clients release acquired votes, back-off and retry after some time). However, in order to counter replica resets, one can raise the value of m in order to preserve exclusivity. However, this protocol performs poorly with respect to variance in network latency between the clients and the replicas. In order to counter this, one can install queues at replicas and reshuffle them towards high contention. Also, another problem is multiple clients retrying when collision occurs, and this is countered by letting clients adopt Active Waiting strategy. Also, when a replica crashes, then one adopts a strategy known as Informed Backoff in order to rebuild its state. This is done by computing the average waiting time for any request (based on position in the queue and average Critical Section duration) and relayed back to the client. In the experimental results, it is noted that the message cost is asymptotically limited, while throughput increases linearly when request rate increases, and then reaches a saturation point. Meanwhile, network latency barely affects throughput. From: Maifi Khan [maifi.khan@gmail.com] Sent: Tuesday, February 28, 2006 12:18 AM To: Indranil Gupta Subject: 598ig review 02/28 Title: A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems. Summary: This paper proposes use of logical replicas to form a quorum consensus protocol for granting access to critical section and thus solve the mutual exclusion problem. In their solution the number of clients can be dynamic. They first describe Strawman protocol which uses majority based consensus to enter critical section. But random reset can cause more than one client to be in critical section at the same time. Strawman protocol suffers from poor performance and greedy behavior of clients can lead to no win situation for all clients for unspecified time. To solve these problems they proposed Sigma protocol. Sigma protocol uses a queue at replicas and use reshuffling in case of high contention. They use active waiting to guarantee progress. After sending a request, if a node wins than it enters critical section, if it does not win it sends a YIELD massage to all the acquired replicas to release so others can proceed. After receiving YIELD, replicas remove the client from winning set and enters it into the queues which is served according to FIFO order. To balance the overload due to retry they use informed backoff mechanism to control the retry timeout. From experimental result they showed that memory reset can cause performance drop and average lifetime of replicas has direct impact on throughput. Criticism: 1. They assume the clients are not malicious which is quite unreasonable. 2. Their solution does not give 100% guarantee of mutual exclusion. 3. It may take multiple YIELD before one client can proceed and no guarantee is provided how many turn will be needed. 4. They proposed continuously adding new nodes to combat compromised node but they did not specify how to determine the number of new nodes to be added. 5. The system will not be scalable as network grows. To obtain quorum consensus in a large p2p system, the traffic and queue management will be tremendous. 6. They assume message cannot be forged which may not be true. Future work: 1. It would be useful if we can bound the number of worst case YIELD a client have to go through to get into critical section. 2. More practical modeling is needed to incorporate malicious node and see how the system works. As malicious node is a reality now a days. Title: A sqrt-N algorithm for mutual exclusion in decentralized systems. Summary: This paper proposes a highly efficient distributed algorithm to achieve mutual exclusion in a networked environment which needs c*sqrt(N) messages and can execute in parallel. There algorithm divides the total number of nodes into N sets where total number of nodes is N and intersection of any two sets is non empty. Each set is also of equal size. Set I contains node i. When node i want to have mutual exclusion, it sends a REQUEST message to every member of Si. After receiving a REQUEST message the node lock itself if it is currently free and returns a LOCKED message to the requesting node. Otherwise it put that node in the WITING queue. If a node knows that it cannot succeed, it RELINQUISH the acquired nodes and thus guarantee progress by avoiding circular wait. If all members of Si returns LOCKED message, a node safely enters critical section and upon completion send RELEASE message to each member of Si. Upon receiving of RELEASE, nodes try to serve requests in the WAITING queue. Discussion: One of the important property of this algorithm is it prevents starvation and the maximum waiting time is bounded. It is possible to remove nodes dynamically by duplicating the dynamic information in other nodes. One of the problem is how to divide the nodes into sets of equal size. According to equation N=K(K-1) +1 , a set of Si's exist if (K-1) is a power of prime. Otherwise some of the conditions need to be relaxed to find a near optimal solution. The number of messages needed is still large for large networks that has thousands of nodes and will not be scalable after a certain size. From: Raghu Kiran Ganti Sent: Monday, February 27, 2006 4:12 PM To: Indranil Gupta Subject: 598ig review 02/28 Review for Algorithms for Systems (Feb. 28th 2006) -------------------------------------------------- Paper title: A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems Summary/Main ideas: ------------------ This paper presents a ``practical'' mutual exclusion protocol for P2P systems. The protocol, Sigma, is implemented inside a dynamic P2P DHT. The basic idea of the protocol is to utilize the fact that nodes in a DHT form a logical space, which together compose a set of logical replicas, and through a quorum, access to CS can be granted. Sigma extends on ALOHA style strawman protocol and overcomes the shortcomings of this protocol. In a simple ALOHA style protocol, each client sends a request to the replicas and waits for responses. The majority wins the round and proceeds into its CS execution, whereas on a loss, the client releases any acquired locks and backs-off for a random period of time before trying again. In such a protocol, the variance of network latency is high as the maintenance of consistent view of competing clients is hard and the random retires by clients (on losing) can result in a lot of contention and nobody winning! Sigma overcomes these shortcomings by introducing a queue at replicas to keep the requests it receives, and put a client (which has requested) into a state of active waiting (to avoid any contention due to retries). There are three main message types, REQUEST, RESPONSE and YIELD. As the names suggest, REQUEST messages request for locks from the replicas and the RESPONSE sent by the replica indicates whether a given client has won, some other client has won, or nobody won. If the response indicates that nobody has won, the client sends out a YIELD message to each of the acquired replicas, which gives an opportunity for the replicas to try to elect a new winner. The protocol is probabilistic in providing CS. It is dependent on the fraction m/n, where m is the number of votes to be obtained out of n replicas in the network (the higher m/n is, the lower the probability of breaking exclusivity). Comments: --------- 1. The system model is quite practical, with network losses also being considered while designing the protocol. 2. The protocol is also quite simple and can be easily implemented on existing DHTs in P2P networks. 3. The number of messages moving around the network is quite high, each client sends n messages (if there are n replicas). 4. The authors have mentioned that self-stabilization, when multiple rounds of YIELD are happening, quickly settles. But, they do not explain why this happens? 5. The protocol is highly dependent on m/n ratio, which is probabilistic. For it to work, m/n must be chosen appropriately. 6. There are a few assumptions made, such as lifetime of a replica being short, nodes in a P2P network being online for a certain amount of time. These assumptions can change over time (especially the P2P node being online for only 10000s), there is no explanation as to how the protocol adapts to such situations? ********************************************************** Paper title: A sqrt(N) Algorithm for Mutual Exclusion in Decentralized Systems Summary/Main ideas: ------------------ This paper presents a sqrt(N) algorithm for providing mutual exclusion in a distributed system. The basic idea is that nodes in the network are divided into subsets, where each element in a subset acts as an arbitrator. Thus, for every subset S_i, it is the case that for every S_j, the intersection of S_i and S_j is not null (else, the mutual exclusion will not be satisfied). Once such a set is obtained, the algorithm proceeds in a simple fashion, through exchange of a set of messages. The algorithm ensures mutual exclusion, avoids deadlocks, and is starvation free. The algorithm begins by trying to lock all the members of its set (S_i). If it succeeds, it can enter the CS. It avoids deadlock by yielding to other nodes if its request's priority is lower than that of any conflicting request. The priority is based on timestamp, if a case occurs where the timestamp of a REQUEST message is smaller than the current locking request, an INQUIRE message is sent to the node which has acquired the lock currently. In the event that the current node is unable to obtain mutual exclusion, it relinquishes the locks it currently has. If it does get all the locks, it will proceed to finish its CS execution. The authors prove that their protocol provides mutual exclusion, avoids deadlocks and creates no starvation conditions. They compare the message traffic of their algorithm with another distributed mutual exclusion algorithm (Ricart and Agrawal's) and show that they perform significantly better, even under heavy load. They also provide a sketch of how to handle node failures. Comments: --------- 1. The number of messages to be sent around the network is lower than other mutual exclusion protocols, the authors provide a O(sqrt(N)) algorithm, where the constant factor hidden in O(.) is between 3 and 5. 2. In my opinion, the algorithm is ``cute'' as it is based on fundamental principles of OS and builds on top of it. 3. One of the major drawback of this paper is that it assumes that the communication layer is error free! 4. It is not clear how this algorithm can be implemented practically on a real P2P network. 5. Also, finding S_i's such that the conditions presented in the paper are satisfied is not very easy, to this end the authors present different methods to do so, but it is not very convincing. 6. Fairness is not present, for example, some node X could always win the mutual exclusion first, because it is closer (in terms of time) to its set of nodes. 7. The assumption that node failure can be detected by another node is questionable, and perhaps it would be the case mostly in distributed networks. From: Praveen Jayachandran Sent: Monday, February 27, 2006 12:16 PM To: Indranil Gupta Subject: cs598ig review 02/27 CS598IG Review 02/27/2006 Praveen Jayachandran A Sqrt(N) Algorithm for Mutual Exclusion in Decentralized Systems ----------------------------------------------------------------- This paper presents an O(sqrt(N)) algorithm to ensure mutual exclusion in a computer network, where N is the number of nodes in the system. The algorithm assumes a reliable communication network which delivers messages in FIFO order. The fundamental idea or condition that ensures mutual exclusion is that any two requests must be known to at least one of the arbitrators (preferably one to minimize overhead). Each node requests permission from a subset of the nodes in the system (including itself), and any two such subsets have a non-empty intersection. The node enters the critical section only when all the nodes in the subset grant permission. A protocol that each node executes to request and grant permission to enter the critical section is presented. An important feature of the protocol is the RELINQUISH message that helps avoid deadlocks. I understand that an earlier version of this algorithm did not have this feature. The author quotes theory to suggest that this condition is equivalent to finding a finite projective plane of N points, which is known to have a solution when N is a power of a prime p. Alternate approximate algorithms which relaxes the condition that exactly one arbitrator should have knowledge of any pair of two requests, have been proposed. These approximate algorithms also run in O(Sqrt(N)) time, improving on the previous O(N)-time Ricart and Agarwala algorithm. This algorithm has many attractive features. The amount of work performed by each node is the same on an average. The algorithm is robust under node failures and does not get into deadlocks, ensuring safety and liveness. Comments: 1. The algorithm works well for static systems where nodes do not join and leave the system often. Whenever a node enters or leaves the system, the subsets from which a node can request permission need to be altered. There has been no discussion provided as to whether this would require all the nodes to be aware of the new membership. For large N, informing all nodes of the new membership could be prohibitively costly. 2. When a node fails, the paper suggests that another node take over its role. However, the requests sent to the failed node have been lost, resulting in the requester waiting indefinitely. Also, if a node fails after entering the critical section, liveness could be compromised. Some timeout mechanism is required to overcome these problems. A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems ------------------------------------------------------------------------------- This paper presents a mutual exclusion protocol that will work in a dynamic environment where the number of nodes in the system could change unpredictably and could be very large. The critical resource is a set of logical replicas, and only one client should access the resource at any given time. The authors propose a cooperative strategy between clients and replicas to counter latency variance and contention, and achieve scalability and robustness. They also propose an informed back-off mechanism to rebuild replica state whenever a replica encounters failure. The mutual exclusion protocol ensures safety with a very high probability even under random replica failures and unreliable communication channels where messages could be replicated or lost. The protocol works as follows. Clients send request messages to the replicas. Due to the variable latencies between clients and different replicas, the replicas may not have a consistent view of the requests posted. Each replica nominates one client (the first request that it received), and sends that clients id to all clients from whom it has received a request. Once a client receives a reply from all the replicas, it can check if it has received a majority vote and enter the critical section. However, it is possible that no client receives a majority vote. In this case, all the clients issue a YIELD message to the replicas, which simply remove the client's request from the head of the queue and place them at the tail, and nominates a new client. This serves to shuffle the request queues maintained by the replicas in the hope that one client will receive a majority. Comments: 1. Each client needs to request all the replicas in order to obtain access to the critical resource. Hence the number of messages for each request is at least O(N) where N is the number of replicas. This also means that under high load, the replicas need to be dedicated purely to answer requests and cannot act as normal peers. This suggests a partly centralized system where some nodes work more to ensure mutual exclusion than others, although the decision of which client enters the critical section is made in a distributed manner. 2. When the number of replicas and requests are large, the probability of one client receiving a majority vote will be low. This could compromise liveness. The protocol provides no bound on how long clients have to wait in order to resolve contention. The authors suggest through experiments that the shuffling mechanism used will stabilize quickly. 3. The protocol only provides a probabilistic safety guarantee. Though this probability of safety violation is very low, the algorithm cannot be used for applications that require strict safety guarantees. 4. The authors identify addressing security aspects of the protocol as future work. From: Juan Jose Jaramillo Jimenez Sent: Monday, February 27, 2006 11:55 AM To: 'Indranil Gupta' Subject: 598ig review 02/28 1 A Practical Distributed Mutual Exclusion Protocol in Dynamic Peer-to-Peer Systems 1.1 Summary The authors use the fact that nodes in the DHT form a logical space that does not have holes to define a set of logical replicas to grant access to the critical section. Since in a P2P network nodes can arrive or depart, this fact is taken into account assuming that the replicas can suffer from complete memory loss from time to time. From these facts, the paper first shows that the high variation of network latency between clients and replicas is responsible for the large performance degradation in the consensus problem, and then demonstrates that a cooperative strategy between clients and replicas is necessary to circumvent those problems and achieve scalability and robustness. It is proposed a new algorithm called Sigma, which tries to solve the problem of requests reaching replicas at different times using a queue at the replicas and reshuffling the queue in case of high contention. To avoid greedy clients that keep resending requests when collisions occur it is used a state of active waiting, where clients wait for a timeout before sending a new request. To make the protocol fault tolerant, two techniques are used: informed backoff (a way to restore a replica's state, in which a client sends a new request for access to the CS after a timeout expires that was given by the respective replica) and lease (access to the critical section is granted for a bounded amount of time, and after that access is granted to another client). Experimental results show that the protocol offers high performance in heterogeneous network conditions and contention rates. The failure handling mechanism is shown to work well with small performance degradation and small communication overhead. 1.2 Comments I am not quite sure that a peer-to-peer system is the best way to handle reliability and robustness for a system that needs to grant mutual exclusion to a critical section. Just as we have already discussed in previous lectures when exploring P2P backup systems, it is not clear whether a company or institution would be willing to lose control of where a critical section is stored and backed, making the problem of consistency even worse in these networks. In other words, I consider that a critical section should not be stored in a P2P system, since tractability is easily lost. Maybe a more interesting research topic could be algorithms for mutual exclusion when having distributed backup copies of the critical section. 2 A sqrt(N) Algorithm for Mutual Exclusion in Decentralized Systems 2.1 Summary This paper proposes an algorithm to create mutual exclusion in a distributed system. It is assumed for this algorithm that we have an error-free communication channel where message transfers can have variable delays, but messages between two nodes are always delivered in the same order. The main idea is to develop a fully distributed exclusion algorithm, opposed to previous proposals that are not fully distributed, like the work by Gifford and the work by Skeen. The idea behind the algorithm is that it is not necessary for all the nodes in a network to cast a vote in order to get mutual exclusion, it suffices that any two voting sets have a non-empty intersection, thus guaranteeing that there is always a common node in two different elections that can act as an arbitrator. Although the selection of the voting sets is not unique, it is easy to see that if the number of nodes is N=L^2 then the easiest way to form those voting sets is that for every node, you take the 2L-1 nodes in the respective column and row as the node's voting set, so no matter which two nodes are competing for access to the critical section, there is at least two nodes that will act as arbitrators. The algorithm creates mutual exclusion using c\sqrt{N} messages, where c\in [3,5] 2.2 Comments Maekawa's algorithm is one of the classical algorithms in mutual exclusion for distributed systems. It uses a minimal amount of messages to grant access to the critical section, while avoiding deadlock and starvation. From: Ravishankar Sathyam Sent: Sunday, February 26, 2006 6:29 PM To: Indranil Gupta Subject: cs598ig project idea.. Professor, I remember you saying once that in order to come up with ideas, you need to think of things you would really like to solve which haven't been covered explicitly (or extensively) in class. I feel that one problem plaguing current p2p networks is the concept of freeloading (and correct me if I'm wrong but most p2p protocols that we've covered so far do not solve this problem). I feel that there could be some system that either minimizes freeloading (by gossiping about freeloaders throughout the network??), or has a reward scheme for people who upload a lot more than downloading....while this idea isn't really concrete, I wanted your input also in this issue...whether this is a good idea to extend or not... Thanks, Ravi Sathyam