Summaries of Papers in Reading List*

(* The title of the paper on this page is same as its local copy's file name, which is composed by the first author's last name and last two digits of the publishing year.)

1. [Satya96]
   This paper tries to exploit the fertile topics in the research of distributed system in mobile environment from the perspective of projects Coda and Odyssey. It first presents the four constraints in mobile computing: limited resources, inherent hazard of mobility, unreliable connectivity and finite power supply. Adaptation is required to solve these constraints. The paper then categorizes the adaptation strategies (a spectrum from laissez-faire approach to application-transparent approach). The client/server model is extended to adapt to the mobile environment, in which the boundary between them is blurred. The Coda and Odyssey projects' results are summarized, including disconnected operation, optimistic replication, support for weak connectivity, isolation-only transactions and server replication. The major part of the paper discusses five topics deserving future exploration: caching metrics, semantic callbacks and validators (to improve the performance of validate cache coherence), resource revocation, adaptation analysis (how to measure adaptive capabilities, i.e. agility) and global estimation from local observation (interesting topic!).
2. [Duchamp92]
   This paper is an early speculation of wireless mobile computing. The author compares the differences of two kinds of mobile devices: terminal-based and computer-based. And he thinks the computer-based device will be more interesting. Then the paper proposes four major challenges for computer-based mobile systems, including distributed services, adjusting to new technology, user interface and authentication/accounting/management. The sketch solution of the first two challenges are discussed. For the distributed services, two models are proposed: caching model (for small working set) and remote access model (cache is infeasible). The major problem for caching model is how to support graceful disengagement for both client and server. Two examples of how to employ new technologies in wireless mobile computing are also given, including a file prefetching algorithm and the application of new non-volatile storage, such as Flash.
3. [Bharghavan97]
   This paper focuses on the challenges to provide seamless mobility over heterogeneous wireless networks. The difference between the model this paper considered and the ones in other literatures (such as Odyssey) is a home computer that holds the computing resources for the portable computers and interacts with the application servers (such as databases). This paper discusses the research goals that emphasize the seamless migration between autonomously managed networks and adaptation to the changing of QoS. The paper proposes three categories of research challenges including the application structure, seamless mobility and adaptive computing. Each challenge is given several possible solutions. Finally, the solution of the author's project PRAYER is presented, which gives the solution of seamless mobility across multiple wireless networks (by adapt TCP/IP), caching and consistency management in the file system and simple language and OS support of application level adaptation.
4. [Forman94]
   This is an early survey on challenges of mobile computing. The unique constraints of mobile computing are presented in three categories: wireless communication (disconnection, low and variable bandwidth, heterogeneous network and security); mobility (address migration, location dependent information and migrating locality); portability (power, data risks and user interface). Possible solution to these constraints are discussed.
5. [Satya01]
   This paper envisions the future of the pervasive computing. The relationship among pervasive computing, distributed computing and mobile computing is discussed. Two scenarios of the future pervasive computing are presented. Then the missing capabilities of current technologies in these scenarios are discussed. The challenges are mainly in how to offloading the computing from mobile devices, how to adapt to the environment change, how to save device energy, how to predict user intent and be aware of user's context, how to achieve privacy and trust and how to make the system "invisible" from user.
6. [Banavar00]
   This paper proposes an application model for the pervasive computing, which can be concisely described as "device as protal", "application as task" and "physical surroundings as computing environment". From the perspective of this model, challenges are presented in three stages of an application's lifecycle. In the design stage, the programming model and development methodology are important. At loading time, challenges are in dynamic resource discovery according to the devices' capability and the choice of user interface. At run-time, environment monitoring and resource redistribution are the major problem. How to deal with disconnection and failure is also a challenge.
7. [Stone77]
   Network flow algorithm is used to solve the multiprocessor scheduling problem in this paper. The problem scenario consists of two processor and a serial program with N components. The intermodule-connection graph is extended with two nodes representing two processors. Then network flow algorithm is used to find the min-cut set, which corresponds to the scheduling solution. The theorem is also extended to try to solve three or more processors problem. But no feasible solution is given.
8. [Bokhari88]
   The paper develops an algorithm to solve the sum-bottleneck path problem in a doubly weighted graph. Using this technique, a few scheduling problems can be converted to doubly weighted graph to be solved. The most interesting problem is of a host-satellite structure and serial programs with arbitrary structure. To solve this problem, the algorithm of [Stone77] and its extension are also needed to first convert a program into chain structure. Then a layered doubly weighted graph is built and the sum-bottleneck path algorithm is applied to solve it..
9. [Eager86]
   This paper discusses the adaptive load sharing in homogeneous distributed systems. Authors argue that simple adaptive policies with very small system state information yield dramatic performance improvements. They doubt that more complex policies and more system information would achieve more performance gain. An analytical model is built and simulation is performed. With the same transfer policy (threshold), three location policies (random, threshold, shortest) are run to compare the performance. The results shows that the three simple policies improve the performance greatly. And even with more system state information, the shortest policy can't achieve more performance improvement than threshold policy.
10. [Harchol-Balter97]
    This paper studies the process lifetime in the real operating system environment, whose distribution follows T^-1. With this distribution, a preemptive migration policy is proposed, which tries to choose the process that has highest probability of running longer than its migration time to ensure that by migration the performance improves rather than degrades. Then simulation is performed to compare the performance of the preemptive and non-preemptive migration. The result shows that the former is better than later.
11. [Vijaykrishnan00]
    SimplePower is a architectural-level, transition-sensitive, cycle-accurate energy simulator based on SimpleScalar toolset. It combines the transition-sensitive model and analytical model to estimate the energy consumption of data path, memory and bus in a model system. Applications in multidimensional array domain are executed on the simulator to find the energy hotspot in the system. Memory system is the most power-consuming component. The impact of optimization is also analyzed, which makes the cache and data path energy contribution become more significant. Furthermore, traditional code optimization may not necessarily mean the efficiency from the energy perspective.
12. [Brooks00]
    Wattch is another architectural-level energy simulator based on SimpleScalar. It is built on higher level than that of SimplePower ([Vijaykrishnan00]). System components are classified into different categories. Parametric models are built for each component. The overall energy estimation is based on the summation of component energy consumption. Real data is compared with the simulated data to validate the simulation model. Several cases are studied to demonstrate the usage of Wattch.
13. [Tiwari94]
    This paper uses the method of measuring the instruction-level energy consumption to synthesize software energy consumption estimation. Base cost of energy of each instruction is measured by running a loop of specific instruction. Other considerations, including the variation in the base cost, the inter-instruction effect and cache miss are also studied and included into the measurement model.
14. [Kravets98]
    This paper proposes a transport-level power management protocol to save the energy consumed by the network interface during its idle receiving mode. The network interface of the mobile host periodically sleeps to reduce the energy consumption and tells the base station when it will be available to receive data. When the mobile host wakes up, it sends a query to the base station for pending data. This transfer mode causes the burst communication pattern. The sleep mode is implemented by a system call to the driver of network interface. The experiment results show a great improvement of energy saving.
15. [Paleologo98]
    A general dynamic power management algorithm is proposed in this paper. Instead of using heuristic methods (timeout, predictive), policy optimization is applied to the power management problem. Abstractly, components in a computer system have different power states, like idle, sleep, etc, which trades power consumption with performance. In this method, Markov process models are built for the component (Service Provider), the user (Service Requestor) and a task queue (Service Queue). Then the system's expect power/performance metric is built and optimized by solving Markov decision process problem. This paper uses the discrete time Markov decision chain.
16. [Kistler92]
    This paper discusses the disconnected operation in the Coda system. The idea is simple: a file system proxy, Venus, which resides at client hoards the objects that the program is using or going to be used (hoarding state); when client is disconnected from server, Venus acts as the real server and all the data accesses are from the local cache (emulation state); upon reconnection, the local operations are integrated with the copy at server (reintegration state). The implementation strategy for each state is discussed. In hoarding state, the prefetched objects are from both history information and user specified profile. The cache is prioritized. In emulation state, a log of operation is kept and optimized. Recoverable virtual memory (RVM) is used to support the transactional access of the logs. In reintegration state, the logged operations are replayed and the conflicts are resolved. Three criteria of the system performance are evaluated. The duration of reintegration are normally in the order of one minute for a program lasting a few hours. The cache size of 100MB is used in the experiment and a reduction of the cache size is possible. And from the simulation using a real file system's trace, the likelihood of conflicts are proved to be very small (<1%).
17. [Noble97]
    This paper summarizes the application-aware adaptation in Odyssey. The prototype system provides mechanisms to help concurrent applications achieve agile adaptation to the changing environment. The applications adapt the environment by changing the fidelity of data, which means the degree to which data presented at a client matches the copy at the server. Odyssey runtime consists of a viceroy and a set of wardens. Each warden deals with a specific type of server data for applications. And applications access the data via the wardens. Viceroy manages system resources centrally. Applications access Odyssey runtime via a set of new system calls on NetBSD operating system. An interceptor in the kernel translates the system call into Odyssey calls. So an application uses the system call to specify the data type it wants to access, the resource range it can tolerate and a callback for Odyssey to execute. Odyssey runtime will call the callback when the resource falls out of the range. Normally the callback changes the fidelity of the data to adapt to the environment change. Three example applications implemented over the Odyssey architecture are introduced. The paper also studies the agility the system can achieve.
18. [Yarvis01]
    Conductor focuses on providing application-transparent distributed adaptation over heterogeneous networks. Conductor enable the adaptation by deploying adaptors in the network. Adaptors intercept the network data stream and handle the data according to its specific semantics. So adaptors are typed. The adaptation can happen anywhere along the connection path from the server to the client and the adaptors are paired to enable the adaptation on one segment of the path. Each adaptor monitor the environment and makes its own planning. When a connection is to be built, a specific adaptor node collects the local plan from the adaptors along the data path and makes a global plan to deploy the adaptation along the data path. Reliability and security are two very important issues in this architecture. The semantic segmentation is used to dynamically adjust the retransmission for data recovery. Also a security model is built to secure the distributed adaptation. The performance of the adaptation is presented (But only the download time, which is not sufficient to measure the system performance. The agility and other criteria should be given and measured.)
19. [Davies97]
    Unlike other RPC-based system (e.g. Rover), Limbo uses the concept of tuple space as the mechanism for message passing among the distributed hosts. Because of the asynchronous nature of tuple space, it is easy to support adaptive communication. Limbo has the features of multiple tuple spaces, tuple type hierarchy, QoS attributes in the tuples and multiple system agents. A centralized prototype and a de-centralized system are discussed to demonstrate the usage of tuple space.
20. [Crow97]
    This paper introduces the draft of wireless LAN standard, IEEE 802.11. The infrastructure of the wireless LAN is composed by basic service set (BSS), distributed system (DS), access point (AP) and portal. BSS is a set of mobile stations with wireless network interface. DS is the backbone of the static infrastructure. BSS connects with DS and other BS via AP. The specification covers two parts of the OSI model: the physical layer and the media access control (MAC) sublayer. At the physical layer, 802.11 adopts three options of spread spectrum method: frequency hopping spread spectrum (FHSS), direct sequence spread spectrum (DSSS) and infrared (IR). Both FHSS and DSSS work at 2.4GHz. At the MAC layer, distributed coordination function (DCF) and point coordination function (PCF) are the two components. DCF is used for contention services, which is based on carrier sense multiple access with collision avoidance (CSMA/CA). PCF is used for contention-free services. PCF relies on the point coordinator (which is access point here) to perform polling. PCF is required to coexist with DCF. The last part of the paper discusses the performance study by simulation.
21. [Perkins97,98]
    These two papers introduce the Mobile IP protocol. Mobile IP is designed at IP layer (Data Link Layer). Its components includes a home agent, the home network, a foreign agent, the foreign network and the mobile node. The home agent is responsible to redirect the traffic to mobile node when the mobile node is not at its home network. The foreign agent is in the foreign network and used to relay the traffic to the mobile node when the mobile node is in the foreign network. The mobile node has two IP addresses: the home IP, which is permanent; the care-of address, which is used in the foreign network. When the mobile node moves from its home network to the foreign network, it obtains the care-of address from the foreign agent and registers the care-of address at the home agent. Then the home agent will intercept the traffic of mobile node and redirect it to the mobile node by tunneling. The tunneled traffic either goes through the foreign agent or goes directly to the mobile node. Routing optimization is enabled by make the mobile node's correspondent node cache the mobility binding (i.e. home IP and care-of IP pair). This mechanism is also used to realize smooth handoff. In IPv6, Mobile IP can be implemented more easily and efficiently taking advantage of the new features.
22. [Perkins94]
    In an ad-hoc network, there is no static infrastructure to support communications among mobile hosts. Instead, a less steady network is built. Packets are transferred via the relay of intermediate mobile nodes. In such an environment, routing problem is very important. This paper is the early study of routing algorithm in ad-hoc network. The Destination-Sequenced Distance-Vector (DSDV) routing algorithm is table-based algorithm. Each mobile node keep a routing table, containing all available destination nodes' addresses and the hops to the destinations. When nodes move, leave or join, the sensed nodes changes their own table and broadcast the change to their neighbors. Sequence number is used to avoid loop updates.
23. [Milojicic02]
    This is a good survey paper on peer-to-peer computing, although it is more an overview than a detailed analysis. This best part of the paper is its categorizing the current P2P systems according to different criteria. In general, the necessary components and algorithms of P2P computing are introduced. Twelve key characteristics of P2P are discussed. For each characteristics, corresponding systems are analyzed. Then, P2P systems are classified into five categories with respect to their intended application area, each represented by several important systems. Eight systems are discussed in detail as case study.

By Ye Wen. Updated on Aug 19th, 2002