The Shell-Spread Algorithm proposed in this paper is a reverse Shell-Sort. The process of sorting an array by reducing disorder as the gap size decreases is reversed. Shell Spread increases the average expected distance between adjacent elements. Applications include artificially inducing fragmentation on a hard-disk for system testing, testing an anti-fragmentation page allocator, etc.

We tested the algorithm on the NT File System and observed exponentially increasing average fragments per fragmented file as well as overall fragmentation. This algorithm was developed and tested in Citrix Systems Inc. as a tool to reproduce an error in our systems software. Shell Spread can be implemented with no internal knowledge of the file system. We implemented our algorithm in Ruby.

Shivakalyani Ankam and Ashwin Baskaran are co-authors on this paper.

The Time Travelling File Manager is a file browser that allows one to quickly and intuitively travel back in time, and view the file system as it existed at that time. It uses the ext3cow file system as a building block, to provide a clean user-oriented interface to versioning, and time shifting in the file system.

Key features include a "date slider bar" and a clock, that allows one to navigate time by just sliding in the selected window of time, and then exploring the file system, at the selected time. One can view different versions of a file or directory, and even compare different versions of a file with it's incarnation in the present time. One can create a portal, in the form of a console (shell) at the time, and snap back to the present time.

It provides an interface to the Time Machine Metaphor, and gives one full control of not only the file system Namespace, but also of Time!

Waitloss provides an efficient way of automatically notifying all relevant Transport Vehicles in the vicinity the need for transportation. The system is currently being built for the Johns Hopkins’ Security Shuttle Service that provides escort vans for students on fixed routes and in a fixed radius.

The basic idea is to be able to automatically request a shuttle, without the need of a central dispatcher. Waitloss also provides a way for inter-van communication and even route van-pickup communication. The system will eliminate common complaints like waiting for a non-existent shuttle, indefinite waits, no cancellation of calls, no-shows, etc. The system will also allow alternative route scheduling, and make the off-route services more effective.

Using peer to peer communication using IP-multicast groups, Waitloss uses the Wave Relay mobile ad-hoc wireless routers, to ensure communication channels in a mobile environment. It uses GPS coordinates to track vans and calculate Estimated times to arrival, and a central proxy server to provide the client interface to any node on the internet. The project was done as the final project for the Advanced topics in Wireless Networks.

Bilbo is a fault tolerant, persistent instant messaging service. Using Spread as the underlying reliable Group Communication toolkit, an Anti-Entropy replication using eventual path propagation, and a persistent message log, the servers are consistently replicated. The servers survive faults like network partitions and process crashes. The replication protocol utilizes communication messages to the order of the square of number of servers and is designed for efficient propagation of knowledge.

Bilbo was undertaken as the final project for the Distributed Systems course.

Legolas uses the Transis algorithm for guaranteeing SAFE ordering of multicast messages. It uses a Directed Acyclic Graph built using implicit acknowledgements to decide if the packet delivery is SAFE. The algorithm is robust and scalable. It performs well under even high losses.

This project was done as part of the Distributed Systems course.

The project simulates independent, distributed swarms of simple creatures (dragon-floyds) that hunt for food and make effective use of pheromone trails, while avoiding obstacles, and other unfriendly swarms.

The floyds have simple brains (state machines) that allow them to use few and simple rules to live their lives. The group behavior emerges as intelligent ‘swarm’ tendencies. The element of surprise exists in the fact, that such simple and a small number of highly localized rules give rise to such intelligent and global emergent behavior.

The Dragon-floyds live in a ‘floyd-hill’ that is a repository for all the food that they collect. Their day begins with foraging for their food. The individuals in a swarm always stick together. ‘Floyds of a feather flock together!’

When they hit a food-mine, they split up and give their whole attention to the food. After they each has a mandible full of food, they return home marking a pheromone trail each (The Dragon-floyds are mutated beings, having the ant-like character of marking chemical trails). This massively parallelizes the ‘bring back food’ operation, as the pheromone trail marking the path to food is proportionally stronger to the amount of food.

The pheromone trail itself serves as a robust way of distributed, decentralized messaging between floyds of the swarm. The swarming also serves to allocate more floyds to the bigger food deposit, thus using them efficiently.

In analogy to Computer science, the food represents resources that can be used and the swarm and floyds are its clients. The pheromone trails represent the connecting fabric, or the network that connects the resource to its new home. The swarm behavior achieves high bandwidth (strength of the pheromone trail), near shortest path resource searches (choosing food over pheromone) and high parallel throughput (more floyds for bigger food particles).

Dragon Floyds was the final project for Object Oriented Systems course.

Distributed Hash Tables (DHTs) have been used to store and manage data in a distributed environment. Popular DHT strategies like Consistent Hashing try to randomly distribute data in the system for reduction of bottlenecks and hot spots. The idea is to find the shortest path to the correct replica and move its data closer toward the requesting node, depending upon its popularity. This not only speeds up lookups, it also achieves fault tolerance through redundancy of data.

However, even the best peer to peer decentralized hash tables suffer from high lookup latency (O (log n)). This can be worsened by heterogeneous networks, topology changes, congestion, etc. We try to move the data closer to the requestor node using an ancient technique used by ants!

We try to exploit techniques used by ants for finding the most efficient path to the food source, taking into account network latency, access latency, processing overheads, etc. Ants use pheromone trails and a form of positive feedback to reinforce certain “good” paths toward food. The pheromone technique can be encapsulated using simple and local rules that evolve and adapt paths that are the best. The effectiveness of the pheromone trail has been proved by the fact that ants have thrived for billions of years!

Most programs use dynamic data structures like linked lists, buffers, symbol tables, trees, arrays of structures, objects, etc. These are often composed of equal-sized elements. Algorithms that use these structures often allocate and then free these elements iteratively. Thus programs display 'Temporal Locality' in terms of their memory allocation sizes. In other words, if a program requests a chunk of size 's' and frees it, then it is highly likely that it will need the same sized chunk again. Also, programs show 'Locality of Reference' in their allocation patterns. That is, if a program allocates a chunk of size 's', then it becomes highly probable that it will allocate another chunk of the same size before freeing the first chunk.

Modern Memory Allocators are optimized to speed up the acquisition of the right sized memory chunk out of a free slab, or pool. However, memory allocation algorithms are heavy. ' The solution is to make the use of the classic 'Cache'. Caches' have been used for a long time to bridge the speed gaps between subsystems of varying response times. Also, Caches work because many programs show locality of time as well as space.

We cache the memory containers instead of it's contents, that is, the allocated memory blocks. Only in the event of a cache 'miss' do we actually invoke the expensive malloc() function. The cache lookup is very fast, and we save a lot of time. Also, to emulate the 'read ahead caching', we do an adaptive allocate-ahead. That is, we pre-allocate a number of blocks proportional to the history of requests.

The allocator is implemented as a shared object (dynamic library) that loads before libc. It hooks into the malloc-free subsystem, maintains caches for the blocks of memory, and implements aging and cache-shrinking policies. As shared objects are loaded per process, the caching can be adapted as per the process. The kernel allocator sees a random stream of incoming allocations that has lesser locality, and hence must be generalized. Also, since this cache is entirely in user space, the overhead of a context switch is avoided.

A prototype implementation showed, that on an average, standard programs (like gimp, bash, mozilla, kmahjongg, vi, cvs, cscope, etc) incur a cache hit occurs 92 % of the time. This shows that programs indeed demonstrate Temporal as well as Spatial locality in their memory allocation patterns. The prototype also speeds up the time spent by some applications in memory operations by as much as a factor of 5!

The project maps a set of networked computers to a file-system-like directory hierarchy. Each leaf directory represents a computer on the network, while the computer’s properties are contained in a regular file within the directory. Parent directories represent classifications such as Windows or UNIX machines, or Desktops or Servers. File access operations applied to the leaf directory or the properties files cause changes to be applied to the networked computers.

For example, a rename operation on a ‘directory’ will change the hostname of the machine. Similarly, changing directory to a machine will take you to the machine itself, via the secure shell (ssh). The Administrator can seamlessly integrate with all the machines in the network, and massive operations that span all the machines can be replaced by a trivial shell script which just traverses machine directories.

Every 'Machine' directory will contain two directories: local and remote. 'local' is the local root file system, while 'remote' is the remote root file system. When in the machine directory, one has access to both file systems and the local process subsystem. When one changes directory to 'remote' one looses all local access, but gains both remote file system and process subsystem access. To return to the first scenario, one need just change directory back to the machine directory.

This is a very powerful paradigm, allowing near-seamless access to the file systems and process subsystems. When this is extended to the forest of machines, it becomes even more powerful.

BDwrap is a template that makes writing stackable block device drivers for Linux very easy and safe. It provides the 'glue' to 'hook' into underlying block device drivers. It exposes a clean interface to the user while hiding the complexity of block device handling, asynchronous I/O, synchronization and concurrency, interaction with the buffer cache, etc.

The interface that BDwrap provides is modeled to be as close as possible to the ‘file’ object. Just like a ‘file’ object, a block device 'object' can be opened, yielding a handle to it. Further operations like synchronous or asynchronous reads or writes, IOCTLs, close etc, are performed on this handle. Also, registering and un-registering of a block device are abstracted, and operate on a 'block device registry key'.

It can be a quick development tool to develop stacked block drivers for encryption, logical volume management, block level profiling, implementing flavors of Object Based Storage Disks (OBSD), etc. It will help those who have just begun on a journey of understanding the Linux kernel block driver interface, or those who want to write a quick stackable block device. It will also serve as a learning tool to help understand the intricacies and complexities involved. The project includes sample stacked block device drivers like a mirrored-device, an encryption-decryption device, a I/O profiler device, etc.

I conducted a lecture on Writing Stackable Block device drivers on Linux as a part of Calsoft's 'Storage Systems Lecture Series'.

I covered the fundamentals of block devices, the kernel block device driver interface, Linux kernel development and writing modules, stackable drivers, using the buffer cache, synchronization and signaling, asynchronous I/O callbacks and piggybacking of buffer heads.

The workshop was a part of Concepts 2004 (PICT), a national level Project exhibition and competition. The title was "Project development in C on Linux".

The workshop gave hands on experience with using important project development tools like CVS, vi, make, gcc, gdb, Bugzilla, ddd, splint, lxr, cscope, etc. Proper design was also stressed during the session.

Pratima is a product that provides block-level, real-time faithful replication of one or more block devices of a local computer to a remote server. This product performs online block level data replication to a remote computer over a network. Both synchronous and asynchronous modes are supported. It supports multiple local devices as well as multiple remote computers. In case the local machine fails, it is possible to fail over an application to the replica by disabling replication and using the replica as a local volume.

A local storage device (a hard disk, partition, or volume) is accessed through a stacked device driver. The device can be accessed by applications at user level. The device can also be accessed from the kernel, for example by mounting a file system on it. The product provides a method to initially synchronize a remote replica offline, and a fast online resync mechanism for recovering quickly from temporary failures. The product supports a cascaded configuration for chained replication and higher availability. An administrative Graphical user Interface with Quick-View is provided along with complete online documentation in form of manual pages

In a world that appears to be governed by Murphy's Laws, anything can go wrong. Accidents ranging from machine crashes, media failures, operator errors and random data corruption to such catastrophes as floods and earthquakes can result in lost data, both temporarily and permanently. The risk of data accidents cannot be eliminated, so one must plan to minimize it. The article discuss popular techniques for this.

This project involved a discrete event simulation of an ant farm. Each ant follows four simple rules.

• If it finds food, it takes it home marking a pheromone trail.
• If it crosses a trail and has no food, it follows the trail to the food.
• If it returns home with food, it puts it down and returns to the trail.
• Otherwise, it wanders at random looking for food.

These sound like very simple rules for any kind of behavior to emerge. However the ant population quickly evolved a pretty elaborate and twisting trail of pheromones, and very few ants were 'wandering randomly' about.

The main characteristic of this rather simplistic algorithm was the pheromone trail. This was the key to robustness. It is a message laid down for any ant to stumble across.

This seminar discussed the justification of using Evolution as a strategy to generate solutions. It then explored the various techniques and ideas of evolutionary computation, reviewed the genetics behind the strategy, listed some applications where it has been successfully applied and concluded on philosophical lines!

The series covered topics like :

• Introduction to the Linux O.S (basic commands, file system basics)
• UNIX programming environment (vi, gcc, gdb, make, the shell - Bash,
• Operating system architecture and I/O streams,
• C and C++ programming
• Programming Style, Design approaches, the concept of an Object and Object Oriented Designing

This project won a Special Mention Prize in a Final Year Engineering Project Competition, Innovation 2000, organized by Cummins College of Engineering. The prize was special because I was in my First Year at the time!

The project included implementing Logic Gates like the NOT, AND, NOR, NAND, EXOR gates using strings, pulleys and rubber bands. I had also implemented a flip-flop, which was the most challenging. Strings control the Logic Gate inputs while the output is displayed as a change of color on a small 'screen' using cardboard sliders and windows.

The project was based on the concept that a 'pull' or tension in a string in a mechanical system translates to a 'ON state' or '1' in an electronic or binary system, while a 'slack' string or no tension means an ''OFF state' or '0'. Rubber bands were used to negate tension by providing a tension of the reverse polarity, while pulleys were used to either translate a change of tension to a rotation or a change of direction.