ABSTRACT
In this paper we have elaborated how ethnomethodology can be used in the requirement-analysis, design and evaluation of interactive systems. We have mentioned some history and future-trends in this regard and further we have briefly contrasted this method with couple of other perspectives. Then we have briefly discussed some of the issues with this approach. Our concluding remark ascertains our basic principle: use ethnomethodology to design (may be not hi-tech but) better and usable systems.
INTRODUCTION
Some people were explicit to remark that Computer Science is really a Social Science [18]. We believe in any case, this is true for the Interactive Systems due to the large involvement of social factors. It is increasingly recognized that human, social, and political issues have a major influence on software systems design [28]. What is needed is a practical, non-ideological approach that can look at 'the real world, real time character of work’ [3]. To attend to this, ethnomethodologically informed ethnographic studies [3,21,23,24] of work have been used to inform the systems design process.
ETHNOMETHODOLOGY IN COMPUTER SYSTEMS
Formal representations of information are needed for designing, using and maintaining computer based systems. Yet, it is also vital to take account of social context, including how information is produced and used, not only how it is represented; that is, we need a social theory of information [9].
Ethnomethodology (literally, 'the study of people's methods') is a sociological discipline which focuses on the way people make sense of their social world [19] and display their understandings of it [5]. Some in the fields have claimed that ethnomethodology is atheoretical[i] [22]. However, it does have a strong focus on methodology. When used in Systems development it is essentially based on fieldwork with the topic: how members accomplish their work tasks [24].
There are two central ideas in ethnomethodology: Indexicality and reflexivity. The first is the insight that there is no such thing as a clear, extensive definition of any word or concept in a language, since meaning comes from reference to other words and to the context in which the words are spoken… Reflexivity refers to the fact that our sense of order is a result of conversational processes: it is created in talk. Yet we usually think of ourselves as describing the order already existing around us. For ethnomethodologists, to describe a situation is at the same time to create it… [16].
Ethnomethodology’s initial involvement in Computer Science revolved around the mismatch between computer applications and the real world, real time circumstances [3] of their use. Since then ethnomethodological studies of work have played a significant role in the field of human-computer interaction, informing design by providing engineers with descriptions of the real world, real time practices of users [5]. Since the 90s, it has remained a popular approach within the CSCW community [3,21] and this is where we also feel it has more to contribute.
Ethnomethodology vs. Rest
Ethnomethodology stands apart from other perspectives as it is at micro level rather than macro level. Instead of analyzing the system it targets the social interaction within the system. Furthermore, ethnomethodology’s main strength lies in its indifferent approach. This is the limitations of some other perspectives such as Activity Theory [26] which is biased towards analyst’s interpretative skills. There is no biased interpretation in Ethnomethodology.
Ethnomethodology is easier to apply as compared to some theoretical perspectives such as Distributed Cognition. Distributed Cognition requires a higher level of skill to move between different levels of analysis that is to move between the detail and the abstract [22]. On the other hand Ethnomethodology is not only a simpler-to-learn approach but it is also more atheoretical; bridging the gap between the abstract and the detail. Central to distributed cognition are the cognitive processes that can be enacted in interaction with the social and material environment [14] thus distributed cognition theory is a theory about cognition [10]. Contrast to this, ethnomethodology emphasizes to understand social interaction without saying anything about cognition. Hence, ethnomethodological analysis is not only indifferent but also accountable (i.e. observable and reproducible).
ETHNOMETHODOLOGY IN STUDYING PEOPLE’S USE OF INTERACTIVE SYSTEMS
Ethnomethodology is not concerned on what is going inside “the head of the user” but what one can observe. Studying people’s use of interactive system through Ethnomethodology is useful for two purposes: 1) Requirement Engineering and 2) Evaluation. However, before mentioning about them we will give a short note on ethnography with respect to ethnomethodology.
Ethnomethodology requires the use of naturally occurring data, which is non-intrusively collected in a situation having significant social interaction, “where members are engaged in activities that they regularly and ordinarily do” [9]. Ethnography is used as the data collection approach for ethnomethodology. It provides comprehensive data in naturalistic setting for ethnomethodological analysis to extract real time, real life patterns. In combination this is called ethnomethodological ethnography [23]. However, ethnomethodological ethnography is often referred to simply as "ethnography" within the context of system design. This assumption is taken in many papers and also in the Crabtree’s book [3].
Requirement Engineering Using Ethnomethodology
Since long, Anthropology has provided a methodological approach (i.e. ethnography) to observing human activities that helps in developing better understanding of how computer systems may help or hinder those activities [7]. Ethnomethodological techniques [8] have been applied in requirement engineering to develop observational techniques for analyzing collaborative work and team interaction [17].
In the 90s Requirement Engineering field brought into it lot of new ideas which challenged orthodox stances. One important idea is that modeling and analysis cannot be performed adequately in isolation from the organizational and social context in which any new system will have to operate. This view stressed the use of contextualized enquiry techniques, including ethnomethodology and participant observation [7,17,20]. Important advantages of using ethnomethodology in requirement engineering are similar to those that are seen in ethnomethodological evaluation which are described next.
Evaluation Using Ethnomethodology
The advantages of using ethnomethodology for evaluation are:
· It gives an insider's view (as one has to learn the work before doing ethnomethodological study)
· It gives explicit and contextualized views of system users complemented by workplace observations
· It helps in understanding of the political and cultural issues surrounding technology use.
To appreciate unique advantages of ethnomethodology one should focus (1) that ethnomethodology has an interpretivist[ii] outlook and (2) the setting for ethnomethodology is naturalistic (rather than controlled and laboratory bounds which are valid for positivist[iii] approaches). Hence, ethnomethodology does not seek to control variables. Also, because all the variables interact in multiple and unpredictable ways, an attempt to isolate and control a particular variable is not considered fruitful.[iv]
Ethnomethodological evaluation is fruitful when it is deployed in all system development phases [3]. In CSCW this has lead to use of ethnomethodological evaluation in Cooperative prototyping [2]. There, ethnomethodological informed ethnography has been involved directly in situated evaluation [27]. In contrast to pragmatic approaches which usually focus exclusively on the user, situated evaluation gives analytical attention to the work that makes the system work in situ [3]. This work includes the interaction between designer and users while they are making the system workable e.g. user support, bug reports etc, as it’s not only the “use” that matters but also unexpected consequence of user actions. Ethnomethodology provides the tools to get hold of this work.
ETHNOMETHODOLOGY IN THE DESIGN OF INTERACTIVE SYSTEMS
Harold Garfinkel has had occasion to note that “ethnomethodology is applied ethnomethodology” [4]. Thus unlike other social perspective main advantage of ethnomethodology is that it is not another theoretical stance but it’s a methodology which when applied, merges with different professions to fulfill their needs. This ensures that product of the ethnomethodological research is applied. Hence, the “product” of the research would not take the form of reports about exotic practices; instead it would consist of efforts to develop hybrid disciplines [15]
Consequently, since the later 90s, there had been significant research efforts in hybridizing ethnomethodology with system-design, in the form of an ethnomethodological perspective for technological support to socially-organized activities called Technomethodology [1]. However it was in mid 80s, when for the first time ethnomethodology entered system design. This is because of the failings of psychological models on which designs were then predicated, hence, there was the need for design to be responsive to the social circumstances of work within which IT systems are embedded in their use [1].
Although, application of social science methods such as ethnography and ethnomethodology to extract design information from field studies of users and their environments is becoming more widespread within HCI practice. Even then these methods are some way from being able to be closely integrated with mainstream software engineering approaches [11]. We think that close integration (or unification) will be fully achieved when ethnomethodologists will be designers as well - or vice versa i.e. we will have designers who are competent in ethnomethodology (See, “learning for ethnomethodology below”). But for this to be achieved, one needs more effort in this direction, both from social and computer scientists – For a middle ground Crabtree’s suggestion of ethnomethodologists working with designers in close collaboration is appropriate. [3].
In CHI 96, Button and Dourish [1] outlined three ways in which ethnomethodology can be used in the design process.
· Learning from the Ethnomethodologist: (Designers) learn from the ethnomethodologist, who goes into the field to study a work setting... (Designer consults the ethnomethodologist directly who is the) primary resource for the design process… (He will work) closely with the designers from the earliest points in the process… Design ideas can be "bounced off' the ethnomethodologist, who draws on field observations both to evaluate and to contribute to aspects of the design.
· Learning from Ethnomethodological Accounts: (This) approach involves learning from ethnomethodological accounts of work settings … (involving) the close collaboration of ethnomethodologist and designer; however, the primary difference is that the designer is working with a specifically ethnomethodological analysis of the work situation, rather than with an ethnomethodologist who might use his training and judgment to respond to design specifics.
· Learning from Ethnomethodology: (This approach makes) the connection at a deeper level yet. Here, the design process learns from ethnomethodology … (it) does not take on board ethnomethodological analysis and insights, but takes on board the very study policy of ethnomethodology… So, rather than have systems design and ethnomethodology "reach" towards each other and "meet" at a design, we instead look to forge more foundational relationships, and then approach design from this new position. This foundational relationship is one in which design adopts the analytic mentality of ethnomethodology, and ethnomethodology dons the practical mantle of design.
Note that, Learning-from-Ethnomethodology is same as “hybridizing ethnomethodology with system-design” which was mentioned earlier in the section. Crabtree [3] further suggested how ethnomethodological analysis can be used for the design of the CSCW system. He recommended number of ways in which Ethnomethodology can be used in the design of CSCW system. We believe his methods are also valid for non CSCW interactive systems however in that case emphasis will be on understanding how an individual makes sense of the work he wants to accomplish.
DISCUSSION
There had been a sudden increase in interest in this area since 90s, largely in response to the growing realization that the laboratory techniques of experimental psychology cannot easily be used to investigate unconstrained use of real-world systems. However, pure Ethnomethodological techniques suffer from exactly the opposite problems. They are so obsessed with the tasks of daily life that it is difficult to establish any hypothesis at all [13].
Another issue is that ethnomethodology briefly requires that a neutral observer should enter the users' working lives in an unobtrusive manner. They should `go in' without any hypotheses and simply record what they see, although the recording process may itself bias results. The situation is similar to that of sociologists and ethnologists visiting remote tribes in order to observe their customs before they make contact with modern technology. The benefit of this approach is that it provides lots of useful feedback during an initial requirements analysis. In complex situations, it may be difficult to form hypotheses about users' tasks until designer shave a clear understanding of the working problems that face their users. This technique avoids the problems of alienation and irritation that can be created by the unthinking use of interviews and questionnaires. [13].
However, to enter a working context, observe working practices and yet not affect users' tasks is not easy and it requires a considerable amount of skill. However we believe still it is worth putting time and effort in learning those skills, as there been some well-documented successes for this approach. Lucy Suchman was able to produce important evidence about the design of photocopiers by simply recording the many problems that users had with them. [13].
Yet, while ethnomethodology seems to reject main-stream sociology, it still has proved to be extremely influential. For instance, ethnomethodology has always focused on the ways in which words are reliant for their meaning on the context in which they are used (they are 'indexical'[v]). This has led to insights into the objectivity of social science and the difficulty in establishing a description of human behavior which has an objective status outside the context of its creation [5]. Hence we will end this discussion by pointing that, this focus on indexical behavior is what has made ethnomethodology useful in the systems development field as it helps the analyst to get hold of ‘the real world, real time character of work' [3].
CONCLUSIONS
As stressed by Button and Dourish (1996) [1] a dilemma facing researchers is that Ethnomethodology’s tradition is in analyzing practice, rather than “inventing the future”. However, coming from a developmental and technical background we believe that Ethnomethodology can very easily be used in development of systems which might not be very innovative but would be very usable. Ethnomethodological analysis of stakeholders’ account can be transformed directly into concrete requirements. Plus while evaluating, Ethnomethodology can be used to understand complexities in software. The complexities can be of bringing context in the system and interpreting meaning out of user system interactions.
We believe that mostly it is not inventing-the-future but understanding-the-past-and-present that helps us in developing usable systems. Ethnomethodology is great tool in this understanding.
REFERENCES
1. Button, G. And Dourish P. (1996) “Technomethodology: Paradoxes And Possibilities”, Proceedings Of The 1996 Chi Conference On Human Factors And Computing, Pp. 19-26, Vancouver, Canada: ACM Press.
2. Bødker, S. and Grønbæk, K. (1991) Cooperative Prototyping, International Journal of Man-Machine Studies, 34 (3).
3. Crabtree, A. (2003) Designing Collaborative Systems: A Practical Guide To Ethnography, London: Springer
4. Crabtree, A. (2004), "Technomethodology"
5. Ethnomethodology Article on Wikipedia Website http://en.wikipedia.org/wiki/Ethnomethodology
6. Gena, C. (2003) Evaluation methodologies and user involvement in user modeling and adaptive systems Proc. Of Simposium on Human-Computer Interaction, HCITALY'2003, RT75/2003, Torino, Italy, 2003, pp 74-78.
7. Goguen, J. & Jirotka, M. (Ed.). (1994). Requirements Engineering: Social And Technical Issues. London: Academic Press.
8. Goguen, J. & Linde, C. (1993). Techniques for Requirements Elicitation. 1st IEEE International Symposium on Requirements Engineering (Re'93), San Diego, USA, 4-6th January 1993, Pp. 152-164.
9. Goguen, J. (1997) Towards A Social, Ethical Theory Of Information, By Joseph Goguen, In Social Science Research, Technical Systems And Cooperative Work, Edited By Geoffrey Bowker, Les Gasser, Leigh Star And William Turner (Erlbaum, 1997) Pages 27-56.
10. Halverson, C. A. (2002) 'Activity theory and distributed cognition: Or what does CSCW need to DO with theories?' Computer Supported Cooperative Work, 11:243-267.
11. Harmelen, M. V. (Editor), and Wilson S. Object Modeling And User Interface Design: Designing Interactive Systems
12. Indexicality Article on Wikipedia Website http://en.wikipedia.org/wiki/Indexicality
13. Johnson C. (1998) Human Computer Interface Design Using Java (Part 1) http://www.dcs.gla.ac.uk/~johnson/teaching/hci-java/course.html
14. Kaptelinin V., Nardi, B. A., Bødker, S., Carroll, J., Hollan, J., Hutchins, E. and Winograd, T., (2003): Post-cognitivist HCI: second-wave theories. CHI Extended Abstracts 2003: 692-693
15. Lynch, M. (1994b) “From Quiddity to Haecceity: Ethnomethodological Studies of Work”, Scientific Practice and Ordinary Action, Pp. 265-308, Cambridge University Press, Cambridge.
16. Marshall, G. (1994), Oxford Concise Dictionary of Sociology.
17. Nuseibeh, B. And Easterbrook, S. (2000) “Requirements Engineering: A Roadmap,” Proceedings Of The Conference On The Future Of Software Engineering, 2000, Pp. 35-46.
18. Pincus, J. D. (2005) Computer Science Is Really A Social Science
19. Poore S. (2000) Ethnomethodology - An Introduction http://www.hewett.norfolk.sch.uk/curric/soc/ethno/intro.htm
20. Potts, C. (1997). Requirements Models in Context. 3rd International Symposium on Requirements Engineering (Re'97), Annapolis, USA, 6-10 January 1997, Pp. 102-104.
21. Randall, D., M. Rouncefield, Et Al. (1995). Chalk and Cheese: BPR and Ethnomethodogically Informed Ethnography in CSCW. In Proceedings of ECSCW 95, Stockholm, Sweden, Kluwer.
22. Rogers, Y. (2004) "New Theoretical Approaches For HCI" In Annual Review Of Information Science And Technology, No 38, 2004.
23. Shapiro, D. (1994) “The Limits of Ethnography: Combining Social Sciences for CSCW”, Proc. Of CSCW ‘94, Pp. 417- 428, Chapel Hill, North Carolina: ACM Press.
24. Sharrock, W. And Hughes, J. A. (2000) Ethnography In The Workplace: Remarks On Its Theoretical Bases http://www.teamethno-online.org/Issue1/Wes.html
25. Suchman, L. (1987) Plans and Situated Actions: The Problem of Human-Machine Communication, Cambridge: Cambridge University Press.
26. Turner, P., Turner, S. and Horton J. (1999): ‘From description to requirements: An activity theoretic perspective’, Group '99, ACM Press, Phoenix, AZ, 1999, pp. 286-295.
27. Twidale, M. B., Randall. D. and Bentley, R. (1994). Situated evaluation for cooperative systems. Proceedings, CSCW'94, Chapel Hill, NC, 441-452
28. Viller S. and Sommerville I. Ethnographically Informed Analysis For Software Engineers, Int. J. Human-Computer Studies (2000)
[i] Not theoretical
[ii] Interpretivist: A view that there exists no ’single truth’ and reality is a social construction which one has to build using interpretations. Its methods have ideographic perspective, involving hermeneutics and subjective interpretation. Role of the researcher is of an involved researcher. (contrast this next footnote)
[iii] Positivist: A view that supports discovering truth. Its methods have nomothetic perspective; focused on a scientific approach, characterized by replication, and triangulation. Role of the researcher is of an objective reporter.
[iv] This is generic remark on all qualitative-based approaches including ethnomethodology. [6]
[v] Just to elaborate a little more: An indexical behavior or utterance is one whose meaning varies according to context. For example, 'That's very funny' normally means that something is funny. If it is said in a sarcastic tone, on the other hand, it means the opposite. The sociologist Harold Garfinkel uses the concept of Indexicality as one of the key assumptions of his school of ethnomethodology. He assumes, in other words, that in social life all behavior and discourse is theoretically indexical. It is the sociologist's job to provide the context such that the action or speech can be understood [12].
My name is Asim Ghaffar and I am from Pakistan and shaghab is my pseudonym. On this blog I will share thoughts/opinions/ideas with a hope that readers will educate me with comments.
Wednesday, March 23, 2005
Thursday, March 10, 2005
p2p Major Assignment
Third paper that we studied is "Novel Architectures for P2P Applications: the Continuous Discrete Approach". In this paper authors have talked about two architectures; one for constructing DHT and one for dynamic expander network. However for our presentation we emphasized solely on the first architecture which has one-dimensional universe i.e. a ring line. However, the first architecture also provides the base for the second architecture which has higher-dimension space i.e. plane.
Both architectures use the same approach which is to dynamically decompose a continuous space into discrete unit i.e. cell. Using the approach authors have first outlined a conceptual model for constructing dynamic data structures e.g. DHT. This conceptual model has a framework which they have titled "think continuously, act discretely". The idea is to visualize everything in continuous space but while do operations (e.g. join, lookup etc) in discrete way. First we will tell how network is constructed and then we will give example of lookup and join to elaborate how Distance Halving network would work
Construction is done, as mentioned as an approach earlier; i.e. by dynamically decomposing a continuous space into cells. Each cell corresponds to a processor. All the points in space between the current node and next node are handled by the current node. For example, let say there are two adjacent cells with value i and value j, where j > i and i, j are in [0, 1). Now all the values greater then i and less then j will be handled by i. This is same technique as used by some other structure overlay networks such as Chord, DKS etc. Note that the range is continuous hence each cell corresponds to a continuous sub-interval.
In continuous Distance Halving graph, each point x has two out-bounded pointers one pointing to point x/2 and second pointing to (x + 1)/2. For example, point 0.6 will be pointing to 0.3 and 0.8 similarly point 0.8 will be pointing to 0.4 and 0.9. In continuous graph there is only one in-bounded pointer that is from 2x (or 2x-1 is 2x >= 1). Hence 0.8 is pointed by 0.6 (1.6 -1) and 0.6 is pointed by 0.2. Hence, in continuous graph degree of each point is 3 i.e. 2 out + 1 in.
In discrete Distance Halving graph there are intervals, in general case an interval of length l is points to two intervals on left and right each of size l/2. Let say an interval starts at 0.6 and ends at 0.8; its left out-bounded interval would start from 0.3 (0.6/2) and will end at 0.4 (0.8/2) right interval will start from 0.8 and end at 0.9 – this is done by adding a 0.5 to 0.3 and 0.4 each. Important thing to note is that these left and right intervals may be covered by more then one cell each. For example, if there are adjacent cells at 0.3, 0.33, 0.37, and 0.41 then left interval is covered by three cells i.e. 0.3, 0.33 and 0.37. On average in discrete graph maximum degree is 6. Maximum degree is bounded by a smoothness which will be defined shortly.
When a new node wants to join it simply takes from its predecessor all the values that are between itself and its successor. Building upon the previous example, assume a new node k wants to join the network such that k is less then j and greater then i, where i and j are two adjacent nodes. Now, after joining, k will take responsibility for the interval that is between itself and j hence it will take from i all the nodes that are in k-interval[i].
In an ideal case each cell will be of same size however this case is too expansive[ii] to maintain so for practical purposes hence cells are allowed to grow within a variable range. Smoothness (ρ) is defined as the ratio between largest and smallest segment i.e. cell. For a discrete Distance Halving graph the maximal out-degree is at most ρ+2, and the maximal in-degree without the ring edges is at most 2ρ + 1. Smoothness of 1 means: that all cells are of same size. In this case, there will be 3 out-degrees and 3 in-degrees i.e. total degree is 6.
Discrete Distance Halving graph is isomorphic[iii] to De Bruijn graph or in other words Distance halving network has Deb Bruijn topology. Authors have mentioned that their construction method is inspired from De Bruijn. The one cosmetic resemblance one could note is that extreme ends have self-pointers. Extreme end in distance halving graph is the left most and right most node on the line while extreme end in De Bruijn node is the node with all zero and the node with all one.
Lookups are done in two ways and they are based on an interesting claim. Before telling the claim we will describe with example an interesting property. As mentioned earlier left and right interval is of half size. It’s intuitive to note that left of left will be one-fourth of original. For example, interval 0.6 to 0.8 will be halved to 0.3 to 0.4 when first left interval is taken and then it will be halved-again to 0.15 to 0.2 when left of left is taken. Same applies for right of right, left of right and right of left i.e. they all are one-fourth of the original interval. Generally speaking by keep on taking left and right in any possible random sequence interval will converge.
Now coming to claim, by interpolating the above mentioned property: lets assume that there are two cells x and y and the distance between them is d. If l(x) and l(y) are left of x and y, then based on the above property, distance between them will be half of the distance between x and y. Hence claim is that by taking any random sequence of left and right i.e. σt(x) and σt(y), interval will converge i.e. to a cell z where t is step and σt is prefix string of length t congaing left and right. e.g. lrll(x) is of t equal to 4.
For example we have cells at {0, 0.05, 0.1, 0.15… 0.90, 095} in space (0, 1]. Now take points 0.6 and 0.7. First left will be 0.3 and 0.35, and second left will be 0.15 and 0.175. In this example we converged to interval of cell at 0.15 by taking two left. Now, for the same example by taking two rights as well rr(0.6) = r(0.8) = 0.9 and rr(0.7) = r(0.85) = 0.925 one can reach convergence again, however, possibly to different cell i.e. in this case this time convergence took place at 0.9. We have given two convergences to show that any random sequence will work.
The above mentioned claim is used to look up a node y from x i.e. you first take a random sequence from x to reach a convergent point z then you back track on the path to z from y to reach y. For example, using the example in the paragraph before, 0.6 can reach 0.7 by taking this path 0.6 à 0.3 à 0.15 ~ 0.175 à 0.35 à 0.7. This kind of lookup is called Distance Halving Lookup. Greedy Lookup is the alternate option which is simply that: you take a sequence toward y from your current point until you converge at y. Example of greedy lookup for lookup of 0.7 from 0.6 in the same space as previous example is: rllr(0.7)[iv] is in 0.6. Greedy lookup results in same path while Distance Halving lookup results in, possibility of, multiple paths between cells hence Distance Halving Lookup is better for load balancing[v].
While preparing our presentation we also studied and discussed joining/leaving algorithms (to achieve smoothness) and dynamic caching for load balancing mentioned in section 3 and 4 however we will not add any more thing in this regard to keep this report short.
[i] K-interval mean the interval starting form k and ending up at k’s successor.
[ii] It expansive as when nth node will join we will have to change all n-1 previous nodes i.e. if we want to have all cells of same size.
[iii] The Distance Halving Network applies (continuous-discrete) approach to an infinite de Bruijn graph, where every point x in [0, 1) has edges to x/2, x/2 + 1/2 and 2x. [Ratajczak and Hellerstein, Deconstructing DHTs, 2003]
[iv] In greedy lookup rllr(0.7) = 0.85 -> 0.425 -> 0.2125 -> 0.60625 in coninuous space and rllr(0.7) = 0.85 -> 0.4 -> 0.2 -> 0.6 in discrete space
[v] Load is divided on different paths.
Both architectures use the same approach which is to dynamically decompose a continuous space into discrete unit i.e. cell. Using the approach authors have first outlined a conceptual model for constructing dynamic data structures e.g. DHT. This conceptual model has a framework which they have titled "think continuously, act discretely". The idea is to visualize everything in continuous space but while do operations (e.g. join, lookup etc) in discrete way. First we will tell how network is constructed and then we will give example of lookup and join to elaborate how Distance Halving network would work
Construction is done, as mentioned as an approach earlier; i.e. by dynamically decomposing a continuous space into cells. Each cell corresponds to a processor. All the points in space between the current node and next node are handled by the current node. For example, let say there are two adjacent cells with value i and value j, where j > i and i, j are in [0, 1). Now all the values greater then i and less then j will be handled by i. This is same technique as used by some other structure overlay networks such as Chord, DKS etc. Note that the range is continuous hence each cell corresponds to a continuous sub-interval.
In continuous Distance Halving graph, each point x has two out-bounded pointers one pointing to point x/2 and second pointing to (x + 1)/2. For example, point 0.6 will be pointing to 0.3 and 0.8 similarly point 0.8 will be pointing to 0.4 and 0.9. In continuous graph there is only one in-bounded pointer that is from 2x (or 2x-1 is 2x >= 1). Hence 0.8 is pointed by 0.6 (1.6 -1) and 0.6 is pointed by 0.2. Hence, in continuous graph degree of each point is 3 i.e. 2 out + 1 in.
In discrete Distance Halving graph there are intervals, in general case an interval of length l is points to two intervals on left and right each of size l/2. Let say an interval starts at 0.6 and ends at 0.8; its left out-bounded interval would start from 0.3 (0.6/2) and will end at 0.4 (0.8/2) right interval will start from 0.8 and end at 0.9 – this is done by adding a 0.5 to 0.3 and 0.4 each. Important thing to note is that these left and right intervals may be covered by more then one cell each. For example, if there are adjacent cells at 0.3, 0.33, 0.37, and 0.41 then left interval is covered by three cells i.e. 0.3, 0.33 and 0.37. On average in discrete graph maximum degree is 6. Maximum degree is bounded by a smoothness which will be defined shortly.
When a new node wants to join it simply takes from its predecessor all the values that are between itself and its successor. Building upon the previous example, assume a new node k wants to join the network such that k is less then j and greater then i, where i and j are two adjacent nodes. Now, after joining, k will take responsibility for the interval that is between itself and j hence it will take from i all the nodes that are in k-interval[i].
In an ideal case each cell will be of same size however this case is too expansive[ii] to maintain so for practical purposes hence cells are allowed to grow within a variable range. Smoothness (ρ) is defined as the ratio between largest and smallest segment i.e. cell. For a discrete Distance Halving graph the maximal out-degree is at most ρ+2, and the maximal in-degree without the ring edges is at most 2ρ + 1. Smoothness of 1 means: that all cells are of same size. In this case, there will be 3 out-degrees and 3 in-degrees i.e. total degree is 6.
Discrete Distance Halving graph is isomorphic[iii] to De Bruijn graph or in other words Distance halving network has Deb Bruijn topology. Authors have mentioned that their construction method is inspired from De Bruijn. The one cosmetic resemblance one could note is that extreme ends have self-pointers. Extreme end in distance halving graph is the left most and right most node on the line while extreme end in De Bruijn node is the node with all zero and the node with all one.
Lookups are done in two ways and they are based on an interesting claim. Before telling the claim we will describe with example an interesting property. As mentioned earlier left and right interval is of half size. It’s intuitive to note that left of left will be one-fourth of original. For example, interval 0.6 to 0.8 will be halved to 0.3 to 0.4 when first left interval is taken and then it will be halved-again to 0.15 to 0.2 when left of left is taken. Same applies for right of right, left of right and right of left i.e. they all are one-fourth of the original interval. Generally speaking by keep on taking left and right in any possible random sequence interval will converge.
Now coming to claim, by interpolating the above mentioned property: lets assume that there are two cells x and y and the distance between them is d. If l(x) and l(y) are left of x and y, then based on the above property, distance between them will be half of the distance between x and y. Hence claim is that by taking any random sequence of left and right i.e. σt(x) and σt(y), interval will converge i.e. to a cell z where t is step and σt is prefix string of length t congaing left and right. e.g. lrll(x) is of t equal to 4.
For example we have cells at {0, 0.05, 0.1, 0.15… 0.90, 095} in space (0, 1]. Now take points 0.6 and 0.7. First left will be 0.3 and 0.35, and second left will be 0.15 and 0.175. In this example we converged to interval of cell at 0.15 by taking two left. Now, for the same example by taking two rights as well rr(0.6) = r(0.8) = 0.9 and rr(0.7) = r(0.85) = 0.925 one can reach convergence again, however, possibly to different cell i.e. in this case this time convergence took place at 0.9. We have given two convergences to show that any random sequence will work.
The above mentioned claim is used to look up a node y from x i.e. you first take a random sequence from x to reach a convergent point z then you back track on the path to z from y to reach y. For example, using the example in the paragraph before, 0.6 can reach 0.7 by taking this path 0.6 à 0.3 à 0.15 ~ 0.175 à 0.35 à 0.7. This kind of lookup is called Distance Halving Lookup. Greedy Lookup is the alternate option which is simply that: you take a sequence toward y from your current point until you converge at y. Example of greedy lookup for lookup of 0.7 from 0.6 in the same space as previous example is: rllr(0.7)[iv] is in 0.6. Greedy lookup results in same path while Distance Halving lookup results in, possibility of, multiple paths between cells hence Distance Halving Lookup is better for load balancing[v].
While preparing our presentation we also studied and discussed joining/leaving algorithms (to achieve smoothness) and dynamic caching for load balancing mentioned in section 3 and 4 however we will not add any more thing in this regard to keep this report short.
[i] K-interval mean the interval starting form k and ending up at k’s successor.
[ii] It expansive as when nth node will join we will have to change all n-1 previous nodes i.e. if we want to have all cells of same size.
[iii] The Distance Halving Network applies (continuous-discrete) approach to an infinite de Bruijn graph, where every point x in [0, 1) has edges to x/2, x/2 + 1/2 and 2x. [Ratajczak and Hellerstein, Deconstructing DHTs, 2003]
[iv] In greedy lookup rllr(0.7) = 0.85 -> 0.425 -> 0.2125 -> 0.60625 in coninuous space and rllr(0.7) = 0.85 -> 0.4 -> 0.2 -> 0.6 in discrete space
[v] Load is divided on different paths.
Subscribe to:
Posts (Atom)