User Tools

Site Tools


research:dgc

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
research:dgc [2006/07/01 13:04]
elisag
research:dgc [2015/02/04 19:10] (current)
elisag
Line 1: Line 1:
 ===== Distributed Garbage Collection ===== ===== Distributed Garbage Collection =====
 +[[http://soft.vub.ac.be/~egonzale/|Elisa Gonzalez Boix]]
 +
 +<note>
 +This page is outdated. Please check [[http://soft.vub.ac.be/~egonzale/|my website]] for more recent research.
 +</note>
  
 ==== Motivation ==== ==== Motivation ====
  
-Mobile ad hoc networks represent a new kind of distributed system with distinguishing characteristics that pose new challenges in the field of distributed garbage collection (DGC). In particular, DGC must deal with a highly partial disconnected network topology where remote references may be inaccessible for unpredicted amount of time. DGC mechanisms typically determine the reachability of the remote objects by means of communication between the nodes involved. However, in a mobile setting where disconnections are the rule rather the exception, the system cannot determine how long it should wait for a connection to be restored. At best, the failure will be transitory and the created inaccessible reference will become accessible again by a repaired connection, but at worst the devices may never encounter again - e.gwhen a user never comes back to a certain place - and an unbounded amount of inaccessible reference will be accumulated as they move about+Mobile ad hoc networks represent a new kind of distributed system with distinguishing characteristics that pose new challenges in the field of distributed garbage collection (DGC). In particular, DGC must deal with a highly partial disconnected network topology where remote references may be inaccessible for unpredicted amount of time. DGC mechanisms typically determine the reachability of the remote objects by means of communication between the nodes involved. However, in a mobile setting where disconnections are the rule rather the exception, the system cannot determine how long it should wait for a connection to be restored. Knowing when the communication will be restored depends on how the application reacts to disconnections. Some applications may wait for the connection to be restored to resume its computation while some others may continue their computation with a substitute service instead. Sometimes the geographic location of the devices or identify information may also influence the behaviour of mobile applicationsDGC thus depends not only on the object graph but also on the //context// in which the objects are themselves i.e the semantics of the application and the role of the reference in the network, but also implicit context such as the location of devices
  
-Knowing when the communication will be restored between two devices depends on how the application reacts to disconnections. Some applications may wait for the connection to be restored to resume its computation while some others may continue their computation with a substitute service in the proximity instead of waiting for the connection to be restored. Moreover, context information may also influence the behaviour of mobile applications. Imagine the case of a user that wants to print some of their PDA files in a printer available in the ambient. Considering that this interaction occurrs at the user's home, their PDA will establish a remote reference to the user printer service. The PDA application could keep this remote reference after the disconnection of the devices since there is a high change that the user will come back eventually and print another file. Considering the same kind of interaction when the user is attending a conference, the remote reference could be reclaimed after the termination of the conference once the user has left. These examples illustrates that DGC process depends not only on the object graph but also on the context in which the objects are themselves - understanding context as internal context such as the semantics of the application or the role of the reference in the network, but also external context such as the location of the devices or identity information.  +Our position is that reclaiming remote objects can no longer be a low level concern tackled in a transparent way via a DGC mechanism. On the contrary, we admit that automatic transparent DGC is irreconcilable with the characteristics intrinsic to mobile networks. Our research proposes a novel treatment of the memory management called //semi-automatic garbage collection// based on the collaboration between the developer and collector which will be guided by the developer to determine the reachability of the remote objects. 
- +
-As a result, we claim that reclaiming remote objects can no longer be a low level concern tackled in a transparent way with a DGC mechanism.  On the contrary, we admit that automatic transparent DGC is irreconcilable with the characteristics intrinsic to mobile networks since context information is necessary to ascertain whether remote references can be cleared. Our research proposes a novel treatment of the memory management called //semi-automatic garbage collection// based on the collaboration between the developer and collector which will be guided by the developer to determine the reachability of the remote objects. +
  
 ==== Design ====  ==== Design ==== 
  
-Semi-automatic garbage collection is a hybrid approach which relies on an underlying local GC and proposes a non-transparent DGC. The approach can be seen as an extension to the indirect reference counting (Piquer,1991) and network objects (Birrel et al.m 1993) since it also maintains the distributed inverse reference graph (IRG) where each remote object keeps a list of pointers to other devices which have references to it. However, the IRG is augmented with additional semantic information attached to the remote references to help the collector to determine the reachability of the remote objects they point to.  This means the developer will be able to steer the gc proccess and accomodate the requirement of the applications by means of annotating the remote references. +Semi-automatic garbage collection is a hybrid approach which relies on an underlying local GC and proposes a non-transparent DGC. The approach can be seen as an extension to the indirect reference counting (Piquer,91) and network objects (Birrell et al.,93) since it also maintains the distributed inverse reference graph (IRG) where each remote object keeps a list of pointers to other devices which have references to it. The IRG is augmented with additional semantic information attached to the remote references to help the collector to determine the reachability of the remote objects they point to.  This means the developer will be able to steer the gc proccess and accomodate the requirement of the applications by means of annotating the remote references. 
  
-{{ remoterefint.jpg?455x318| Click the image to enlarge }}+{{ remoterefint.jpg?430x250 }}
  
-Since devices may not be able to communicate at some point in time, when a remote reference is first allocated both parties in the interaction will establish a contract with the condition under which the reference is useful to the application. Therefore, if one devices becomes inaccessible because of a broken connection, the other one is aware of the conditions in which the inaccessible reference is still valuable. We propose //referencing strategies// as the language support that allows the developer to determine which collection policy will be applied to both source and target of the reference upon disconnection.  From the point of view of the device hosting remote objects, the DGC will be able to determine the reachability of its remote objects based on the analysis of the referencing strategies of the references pointing to them. From the point of view of the clients, the referencing strategy will determine the rebinding policy to apply to a reference after a disconnection. +Since devices may not be able to communicate at some point in time, when a remote reference is first allocated both parties in the interaction will establish a contract with the condition under which the reference is useful to the application. Therefore, if one devices becomes inaccessible because of a broken connection, the other one is aware of the conditions in which the inaccessible reference is still valuable.  
 + 
 +We propose //referencing strategies// as the language support that allows the developer to determine which collection policy will be applied to both source and target of the reference upon disconnection.  From the point of view of the device hosting remote objects, the DGC will be able to determine the reachability of its remote objects based on the analysis of the referencing strategies of the references pointing to them. From the point of view of the clients, the referencing strategy will determine the rebinding policy to apply to a reference after a disconnection. 
  
 ==== Ongoing and Future work ==== ==== Ongoing and Future work ====
  
-We are currently exploring the necessary referencing strategies for the developer to annotate remote references with the extra semantic information. We have come up with a tentative classification of referencing strategies that can be found [ [[http://prog.vub.ac.be/Publications/2006/vub-prog-tr-06-16.pdf| here]] ], but we are still investigating the semantics of these constructs.  +We are currently exploring the necessary referencing strategies for the developer to annotate remote references. We have come up with a tentative classification of referencing strategies that can be found [ [[http://soft.vub.ac.be/Publications/2006/vub-prog-tr-06-16.pdf| here]] ], but we are still investigating the semantics of these constructs.  
  
-We have also identified a number of  open issues that are not properly tackled yet by our approach:+There are a number of open issues that are not properly tackled yet by our approach:
  
   * Resolving conflicts between client and service provider strategies.   * Resolving conflicts between client and service provider strategies.
- 
  
   * Indirect references: passing a reference to a third party.   * Indirect references: passing a reference to a third party.
- 
  
   * Composition mechanism to mark group of remote reference at once.    * Composition mechanism to mark group of remote reference at once. 
  
-  * Garbage collection of the remote objects once it is no longer pointed to. 
  
  
 ==== Further Reading ==== ==== Further Reading ====
  
-**Semi-Automatic Garbage Collection for Mobile Networks**. Elisa Gonzalez Boix, Tom Van Cutsem, Stijn Mostinckx, Jessie Dedecker, Wolfgang De Meuter, and Theo D'Hondt. In "Proceedings of the workshop on Object Technology for Ambient Intelligence and Pervasive Computing (OT4AmI), collocated with ECOOP 2006, Nantes, France". [ [[http://prog.vub.ac.be/Publications/2006/vub-prog-tr-06-16.pdf|download]] ]+**Semi-Automatic Garbage Collection for Mobile Networks**. Elisa Gonzalez Boix, Tom Van Cutsem, Stijn Mostinckx, Jessie Dedecker, Wolfgang De Meuter, and Theo D'Hondt. In "Proceedings of the workshop on Object Technology for Ambient Intelligence and Pervasive Computing (OT4AmI), collocated with ECOOP 2006, Nantes, France". [ [[http://soft.vub.ac.be/Publications/2006/vub-prog-tr-06-16.pdf|download]] ]
research/dgc.1151751888.txt.gz · Last modified: 2006/07/01 13:07 (external edit)