OS and Networks Commons^™

An Online Algorithm For The 2-Server Problem On The Line With Improved Competitiveness, Lucas Adam Bang

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis we present a randomized online algorithm for the 2-server problem on the line, named R-LINE (for Randomized Line). This algorithm achieves the lowest competitive ratio of any known randomized algorithm for the 2-server problem on the line.

The competitiveness of R-LINE is less than 1.901. This result provides a significant improvement over the previous known competitiveness of 155/78 (approximately 1.987), by Bartal, Chrobak, and Larmore, which was the first randomized algorithm for the 2-server problem one the line with competitiveness less than 2. Taking inspiration from this algorithm,we improve this result by utilizing ideas from T-theory, game …

Message Passing Algorithm For Different Problems Sum, Mean, Guide And Sorting In A Rooted Tree Network., Sabaresh Nageswara Rao Maddula

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis, we give message passing algorithms in distributed environment for five different problems of a rooted tree having n nodes. In the first algorithm, every node has a value; the root calculates the sum of those values, and sends it to all the nodes in the network. In the second algorithm, the root computes the value of mean of values of all the nodes, and sends it to all nodes of the network. The third algorithm calculates the guide pairs. Guide pair of a node x is an ordered pair (pre_index(x), post_index(x)), where pre_index(x) and post_index(x) are the …

Self-Stabilizing Leader Election In Dynamic Networks, Hema Piniganti

UNLV Theses, Dissertations, Professional Papers, and Capstones

The leader election problem is one of the fundamental problems in distributed computing. It has applications in almost every domain. In dynamic networks, topology is expected to change frequently. An algorithm A is self-stabilizing if, starting from a completely arbitrary configuration, the network will eventually reach a legitimate configuration.

Note that any self-stabilizing algorithm for the leader election problem is also an algorithm for the dynamic leader election problem, since when the topology of the network changes, we can consider that the algorithm is starting over again from an arbitrary state. There are a number of such algorithms in the …

Dynamic Distributed Programming And Applications To Swap Edge Problem, Feven Z. Andemeskel

UNLV Theses, Dissertations, Professional Papers, and Capstones

Link failure is a common reason for disruption in communication networks. If communication between processes of a weighted distributed network is maintained by a spanning tree T, and if one edge e of T fails, communication can be restored by finding a new spanning tree, T’. If the network is 2-edge connected, T’ can always be constructed by replacing e by a single edge, e’, of the network. We refer to e’ as a swap edge of e.

The best swap edge problem is to find the best choice of e’, that is, that e which causes the new spanning …

Visual Occam: High Level Visualization And Design Of Process Networks, Mikolaj M. Slomka

UNLV Theses, Dissertations, Professional Papers, and Capstones

With networks, multiprocessors, and multi-threaded systems becoming more common in our world it is increasingly evident that concurrent programming is not something to be ignored or marginalized even though many takes on concurrency (mainly by means of monitors or shared resources) have proven to be difficult to deal with on large scales. Thankfully, a good deal of work has already been done to combat this, through CSP, occam, and other such derivatives, to produce a scalable process oriented paradigm. Still, it is cumbersome to attempt to deal with the intricacies of such communicating networks down to every minutia; if, instead, …