On Randomized Online Scheduling - Review

On Randomized Online Scheduling deals with the most common problem found in the study of online algorithms: minimize the makespan of a sequence of tasks or jobs when scheduled in different parallel machines. The Rand algorithm proposed by Alberts performs better - 1.916 competitive ratio - than known deterministic solutions for general m (being m the number of machines available). The approach is a combination of two different scheduling alternatives which are chosen randomly with 1/2 probability to serve the entire sequence of tasks. In this paper I present a review of the Rand algorithm itself, analyzing the lower bound theory presented, technical approach, the algorithm, some proof and concepts and particular examples of the findings.


Comments

Post a Comment

Popular posts from this blog

A review of Partitioning Attacks

Partitioning Attacks is one form of side channel attacks which deals with cryptographic algorithm implementation, and more specifically, with those implementations where sensitive data reveals some statistical dependency of the logical states and hence, several well known techniques such us power or electromagnetic analysis can be used to find out the value of such relevant data. Partitioning is related to the property of certain implementations where relevant data can be distinguished as belonging to certain clusters - partitions - of signals or side channel information, which the attacker may use to createa statistical dependency of the flow. Such leakiness can be caused by algorithms using, for instance, lookup tables to store values needed during computation. In this paper , an overview of partitioning attacks is presented by exploring a particular example, the characteristics under which it operates and certain countermeasures which has been also suggested to thwart such attack.
Read more

Asynchronous Features for IMS Applications

One of main advantages of using the SIP protocol for developing IMS applications is its asynchronous nature. Interactive applications are those ones providing asynchronous notifications of events, and nowadays the current trend is on this direction (just take a look around to the asynchronous Web where you have the ability for the application to deliver state changes to the client, without the user necessarily having to initiate those updates). SIP is inherently an asynchronous protocol, where your User Agent or IMS entity is both client and server, and therefore, interactivity is a default feature. One of the main extensions offered by the SIP protocols is the SUBSCRIBE / NOTIFY mechanism RFC 3265. SUBSCRIBE/NOTIFY is a kind of observer pattern, where clients subscribe (listen) to a server for specific events, and once the server decides that a certain event must be communicated to the client, it notifies them about it (using the contact information provided by the client during su...
Read more

Homeopathic Ontology

Homeopathy is an alternative medical approachbased on the principle that a disease with a given set of symptoms can be cured by a medicine (remedy) which is known to produce a similar set of symptoms. Homeopathic remedies are based on "proving" techniques, which is a process used to test certain substances on healthy volunteers and to observe their reactions (symptoms). In order to analyze specific symptoms, this process may take months or years and results or provings are registered in a repertory, which represents a collection of homeopathic provings, well known as the Homeophatic Materia Medica. The repertory is an extensive collection of many years of investigation. Software technologies allow us to index all this information, in order to be able to look for any related symptom or remedie based on different criteria, proximity or combination of words. Due to the complexity and broadness of homeopathy, there is not a defined vocabulary or schema on those repertories where...
Read more