um yeah the talk the first talk of the session is return of the hidden number problem a widespread and novel key extraction attack on ecdsa and tca and it will be given by keegan rine. Alright thank you so yes I'm keegan rine this is the return of the hidden number problem. Now the return of the hidden number problem is an ecdsa and dsa side channel based key extraction attack so that means if you have some ecdsa implementation like a smart card or a server or an authenticator that creates ecdsa signatures this attack attempts to use side channels to recover that private key. The return of the hidden number problem uses an old technique that is solving the hidden number problem and it uses it to target a new part of the ecdsa and dsa signing process. This attack is also very common throughout this research I looked at 20 different open source implementations of ecdsa and dsa signing and I found that 11 of these libraries were vulnerable to this key extraction attack. Finally this attack is very efficient it's easy to understand it and it's easy to under uh to apply so throughout this talk I'm going to try to give you an intuition for how this attack works so that you will be able to spot this issue when exploiting other devices and be able to extract ecdsa and dsa keys of your own. So in order to understand the return of the hidden number problem it's important for us to understand the prior work on extracting keys from dsa and dsa implementations. So as a brief refresher for those who don't do side channel attack research we have the ecdsa equations here which compute signature r and s for a message m using private key x. Now the value k here is a per signature random value which is the nonce and all these computations are done modulo q which is a large prime frequently on the order of size 2 to the 256 for the examples we'll use in this presentation. Now I'm going to be a bit uh loose with the notation here uh and not always right when things are done modulo q uh but if you want to see the uh rigorous definitions then I'll refer you to the paper. So in these equations when we're calculating the signature r and s the attacker knows the values of everything except k which is the per signature random value and x which is the long term private key. So if the attacker uses a side channel attack to recover information about that nonce k they can use that partial information to figure information about the private key x and if they repeat this process for many signatures they can compile all that leaked information about x together and recover the full private key. Now more concretely uh I'll explain how the hidden number problem ties into this. So in a naive implementation when calculating the multiplication of k times g it's possible that a naive implementation would compute this product faster when k is small. So the attack can observe that that multiplication k times g happens quickly during the signature generation process and for that k is small. And now when I say small it's not absolutely small but it's relative to the size of the field. So if we have a field that's based on a 256 bit prime then k may be anywhere between 1 and 256 but the side channel may give us information that k is between 1 and 2 to the 250. So we get six bits of information about k but 2 to the 250 is still larger than any brute force attack that we could perform. So with this small amount of leakage about that nonce k we can rewrite the DSA equations as follows uh to show what k equals. So on the right hand side we have a bound which is based on that modulus q uh and the more bits that are leaked about k the tighter that bound gets. And then in the center we have a uh the private key x right here. So every uh equation that we derive from a signature has that private key x. We have a known multiplier which is based on the value of that signature and we have a known offset which is based on the signature and the message being signed. So if the attacker observes this side channel leakage uh for both the offset and the multiplier and they know this bound based on the side channel leakage they can construct this inequality and if they repeat this for several signatures they can construct several inequalities and then the goal is to be able to solve this system of inequalities which is possible using a lattice based reduction approach. So this sort of problem is known as the hidden number problem. In the important parts are we have that hidden number x which we're trying to recover, we have a known multiplier, we have a known offset and we have a known bound. So if we see something of this form that's going to be something that we're able to solve. So the way that these issues were patched because many of the prior attacks on DSA and ECDSA exploited the sort of non-sleakage is that that multiplication of k times g was hardened more countermeasures were added so that if information does not leak about k times g in the computation of r then you can't use that leaked information about k to recover the private key. Now with that in mind it's possible to see how the return of the hidden number problem differs and how that attack works. So we have the same ECDSA equations where the attacker still knows r, s, m and g but instead of targeting that multiplication in the computation of r we ignore that computation of r completely and we only look at the addition in the calculation of that signature component s. So we don't care about all of the countermeasures that were applied in this step, we're only looking at this addition right here. So when we look at the libraries and we see how they implement this addition it's done in a very straightforward way. So if you're trying to add two numbers modulo some other large number first you add the two numbers if it exceeds the modulus then you subtract out that modulus and then you return the final value. So this works if both of the arguments are reduced modulo q at the beginning and it is done very quickly. But since this is a side channel attack you should immediately jump to this conditional branch right here and know that a side channel attack will be able to recover if this branch is taken or not. So our side channel attack is going to be tuned to recover to see if this subtraction occurs or not. And note that if this subtraction occurs then we learn information about the arguments to this function. If that subtraction occurs then a plus b exceeds q. And that's all we need to know to be able to perform the return of the hidden number problem attack. So returning to the equations we are observing the calculation of m plus r times x. We're assuming that m and rx are both already reduced modulo q. And we're going to use a side channel to see if that addition wraps around. And there are many different side channels that we could use for this attack. I use a Flush and Reload attack on a cryptographic library but you could also use a power trace. You could use EM analysis. You could use pretty much anything as long as you learn whether or not this addition wraps around. So if this addition does not wrap around then we can take that equation, see that m plus rx is less than q and rewrite it as follows. And if we see that the addition does wrap around we can again rewrite the equations as follows. And once again I'm being a bit loose with the notation. But the thing that I want to point out is that we have a private value right here that we want to recover. We have a known multiplier which is based on the signature. We have a known offset. And we have a known bound. So this is just an instance of the hidden number problem. If we observe this process for many signatures and put this into a lattice and use that lattice to solve the hidden number problem we will recover the private key x. So it's very straightforward. And this attack has many benefits. For one it's very fast. So you only need about a few thousand signatures in order to be able to perform this attack. And the reduction happens very quickly in many cases under a minute. This information can also leak through many side channels as we've spoke about already. There's the flesh and road. There's all the memory cache. There's all the physical base side channels. Anything that can leak that one piece of information we'll be able to extract the private key. Another benefit is that the attacker is often in control of that message m that's being signed and they can tune that value in order to change what the bounds are. So if I go back to these equations we see that the bound is dependent on m. So if we choose m to be small, for example, around two to the 250 instead of two to the 256, then we can tune these equations so that when we observe the right condition of the modulus being subtracted out or not, we're going to be able to get more information about the private key x in these hidden number problem inequalities. This issue is also nice because we're able to detect it in a black box. So assuming we have some timing dependence on whether or not the subtraction occurs, we can create many signatures with a large m. So that's m where the leading bits are set. And since m is large, it's likely that when adding with the random r times x, that sum is likely to exceed the modulus q. So a large m is going to be more likely to have that wrap around that extra subtraction. A small m is similarly likely to not have that extra subtraction is likely to take less time. So we're able to collect many signatures using both large m and small m. We're able to do a statistical analysis to see if there is a timing difference between those two cases. And then if there is, then we can use a more powerful side channel attack to try to extract information about a single signature. Another benefit of this attack is that it sort of completely sidesteps all the power countermeasures. So many of the power countermeasures were target at that multiplication of k times g. But our attack does not care about that multiplication at all. It only depends on that one addition of m and rx. And the last benefit is that this efficient attack is common. So of those 20 libraries that are looked at, 11 were vulnerable. And it's likely that other libraries are vulnerable as well. So throughout this research, I did look at many implementations I'd like to just show you some of those implementations that I looked at. I started with this long list of different implementations, which I thought might be affected by this issue. They're just cryptographic libraries of some sort or another. And I think there are 30 sites up here. So I started by looking at which ones were open source and I excluded all the ones which were closed source just because I had to analyze these by hand and harness all these by hand is a lot faster to just look at the source code to see whether or not there was an issue. And all of the highlighted libraries here are closed source. Some of these libraries also just wrap the ECDSA or DSA implementation. So again, those libraries are not vulnerable because they just use a different implementation. And finally, a few of these libraries don't implement the DSA algorithm or ECDSA algorithm at all. There's no option to use those. So those are also not vulnerable. But we're left with these 20 libraries. Of these libraries, some of the implementations were entirely constant time. So that modular addition did not follow the pattern of A plus B, if that exceeds Q, subtract Q. These use a fully constant time implementation for that part of the code and are therefore not vulnerable to the attack. If you recall another requirement of the attack is that both the operands of that sum are already reduced modulo Q. M needs to be reduced modulo Q and Rx needs to be reduced modulo Q. And if it's not, then the attack won't work. So some of these implementations did not do that reduction modulo Q. So the attack doesn't work. But that means that all of these remaining attacks, all of these remaining libraries are vulnerable to the attack. And we can see some pretty prominent names. So there's OpenSSL, there's LibGCrypt, all of these libraries were vulnerable to this attack. So it's clearly widespread. It clearly affects a wide variety of implementations. And I'm sure there are many more closed source implementations out there, which are vulnerable as well. So the proof of concept attack that we applied in the paper was done against OpenSSL. But the source code for that attack is very configurable. It's easy to apply to any of these other libraries, as long as you can create an oracle that shows whether or not that extra subtraction occurred. And the last point that I want to leave you with is an example that I actually just found yesterday when I was looking through the code. So do you guys recognize this device? It's the 502 authenticator that we all got as part of CHES. And it turns out that 502 uses ECDSA keys to authenticate you to different web services. So if it's possible to extract that ECDSA key, you can impersonate someone without having to have physical control of their device. Fortunately, the firmware for this device is open source. So I was able to go through and find the actual implementation of the ECDSA signing. And we can see that the implementation is based on microECC. And it says that it's resistant to known side channel attacks. But it was also updated two years ago. So that's prior to this work. And I look through and I found the implementation of that modular addition that it uses for the ECDSA signature. And here's directly from the code what it is. And we can see that once again we have our operands left and right being reduced by a modulus. And we start by adding, we compare it to the modulus. And then if it exceeds the modulus, subtract it out. So a memory side channel attack would be able to detect whether or not this function is called. It would be able to tell that the extra subtraction occurred. And it would be vulnerable to this key extraction attack. So perhaps you use some sort of physical side channel as you're monitoring the execution. Or perhaps it's reliable enough to use timing. But it should be possible to recover ECDSA keys in this way. And now I do want to point out that this is outside of the threat model of these keys. These keys are only designed to resist online attacks. That's attacks where someone is, they only have access to a computer, they don't have physical access to your device. So the point is not that you should not use these devices. You still should use these authenticators. But the issue that I want to raise is that the vulnerability that's exploited by the return of the hidden number problem is widespread. Many things are affected by it. Many completely distinct and unique implementations are vulnerable to the same flawed pattern. So how many other close first implementations out there might be vulnerable to this pattern as well. So in conclusion, the return of the hidden number problem targets a different part of the ECDSA signature process than prior side channel key extraction work did. And this is how it's able to evade many of the counter pressures. This attack is also widespread. A large number of libraries were vulnerable to this key extraction. This attack is efficient. It only takes a few thousand samples and the analysis completes in around a minute. This issue is easy to both understand and exploit. And finally, I hope that you're able to look through ECDSA implementations and as you're developing new side channels, you're able to see if this attack will apply and if you're able to recover your own private keys. Thank you. Yeah. Thank you. Are there any questions? So if there are no questions, so it took quite some time until this attack has been developed. Do you think that there are more things hidden in ECDSA that we yet have to uncover? So I think so, and that kind of goes to the counter measures that were applied in response to this disclosure. So of those libraries that were affected, many of them did not use constant time field operations for that computation of S. And the counter measures that I recommended to these libraries were twofold. One of them was a blinding operation, which would prevent leakage from the specific addition. And the other was making the libraries constant time, which would protect against leakage in other parts of this computation, which involved the Private Key X. And almost universally, the libraries chose to implement only the blinding mitigation and not making the operations constant time. So I would not be surprised at all if a future attack will be able to use that lack of constant time implementation for those field computations in order to leak the Private Key again. Thank you. Thanks. So if there are no further questions, let's thank the speaker again.


Good morning everyone. Welcome to day 9 of our workshop. Today we are going to cover several topics. The first topic is big data and after that we will move on to transactions and a little bit of concurrency control. And today afternoon the lab is on big data. In particular we will be using the Hadoop software to perform map reduce programming. Today's lab on Hadoop will be running on individual machines. You will just be running Hadoop locally on one machine. But exactly the same thing can also be configured to run on thousands or tens of thousands of machines which is how things are done in the real world when there are really big data needs. There are of course, smaller data and big data needs which may run on 20 40 machines but these things scale up to tens of thousands of machines. So, that brings us to what is all this noise about big data. So, first what is big data and is it really new what is different from what was there before? Maybe it is not all the different but there is a lot of hype these days because there is a lot of demand a need for processing very large amounts of data which are well beyond the scope of a single machine. So, what we are going to do is look at the map reduce paradigm and first cover the concepts and then talk about specific implementation called Hadoop which you will be using in the lab today. And then we will move on to briefly look at other aspects of big data including big data storage system. So, what is the map reduce paradigm and why is it needed. So, like I said first of all what is big data there is always been a need for processing large volumes of data which are beyond the scope of something which can be done on a single machine. Now, the need for this was felt by only a few big companies many in fact I would say 2 decades back or more 2 and a half decades back. There were a few very large companies which were gathering enough data that they needed to worry about how many machines to run this on you know one machine 2 machines are not going to cut it they had to run computations on literally hundreds of machines. So, there was a company formed back then called Teradata and even before that there were parallel database research projects from the university of Wisconsin and from the university of Tokyo both of which showed how the normal relational operations can be nicely parallelized across many machines. So, the underpinnings were laid back then in the mid 1980s. The project took off around probably 1983 or so quite a long time back almost 3 decades back. And in the late 80s this company called Teradata was launched and it initially had a few very big customers like Walmart who you have heard of which is probably the biggest retail firm in the world. Back then it was more USA centric, but even then they had literally hundreds of major shops across the US and terabytes of data which in that era was even more scary than it is today. Today a terabyte is something which you have on one disk on your machine in that era your typical disk was you know maybe 100 megabytes if you pushed it. So, then you are talking of 10,000 disks and they were talking of terabytes with tens of thousands of disks. So, in that era parallel databases started growing, but the customer base was relatively small and it had a steady growth which exploded in the late 1990s when the web exploded. So, what is the influence of the web? There were lots of people going online and doing things. Now, what were the things they were doing? It started off with just going and looking at web pages, but soon e-commerce grew. So, they were buying things on the web website like Amazon and these days you have Flipkart in India. They were also running search queries on the web in that era even before Google there were many very successful search companies. There is a company called Alta Vista another called Inktome. You may not hear about them anymore, but they were very successful search companies and there was Yahoo and there was Hotmail any number of websites they are collecting a lot of data and this data was stored in log files primarily. So, they were not using relational databases to store this kind of data. Relational databases were never designed to handle this kind of volume that they were experiencing. They were not really fast enough. It was a lot faster to have a large number of machines parallely writing stuff into local files log files whenever something happened and then you collect the log files and do interesting stuff with them. Analyze them to see what you should be doing. For example, an analysis of queries on search engine might help it decide whether it was doing the right thing where people getting the answers they wanted or were they searching repeatedly with slightly different keywords because they were not getting the answers. Where people searching for certain products maybe shopping website would want to make sure that things which people frequently search for are available. There is enough choice available that particular product may not be stocked, but the search might tell it that maybe we should be stocking it. So, there is a lot of use for taking these web logs and making business decisions based on them. This is more or less where the whole big data paradigm started, but there were many more uses. So, if you look at Google how was it going to build its web search index? So, that is a big index out there. It is an enormous index because it induces billions of web pages. Each web page has thousands of keywords. So, it has trillions of keywords in that index. Clearly that index cannot be sitting on one machine. It has to be partitioned across probably thousands of machines and it has to be very fast in order to respond to query, but also you have to build that index and building that index itself has to be done in parallel. Now, there was no database which could handle these kinds of things. So, the initial versions of these parallel systems were built by hand. So, what does I mean built by hand? Every time people wanted to do new thing they would have to code up a system which would, let us assume we are running Linux machines. They would SSH to a large number of machines, startup processes on those machines which would participate in that job and then when the job is done those processes would quit. So, this is hand coded parallel system and this is how the early systems were built. If you wanted to build parallel web crawl and web indexing system, this is how it would have been built in the early days. Parallelism was already there, but hand crafted parallelism. But after some time people realized that this was there was a lot of pain to doing these things.  It is not a small task, it is a which is running across many machines, but from a human view point it is a simple task and you do not want to have such high overheads for doing a simple task. The second thing is that when you have a large number of machines, there are failures. I think machines die and if you are having a thousand machines, the probability that one of the machines will be dead to start with is already there and then as after you start a computation, there is a significant probability that one of the machines will die or it may not die, but one of the machine may be very slow because something is wrong. Somebody has got a process running on that machine which is uncontrolled and the machine is not able to service your requests. So, it can be very slow which is more or less as good as dead in this context. So, you have to deal with failures such as these and how do you deal with it? Conceptually, you can say if a machine is dead, run that whatever it was supposed to do somewhere else, but somebody has to do all these things. They have to maintain the infrastructure. Somebody has to paint the buildings, lay the roads, clear the sewers when they are clogged. All that is part of the infrastructure. We cannot take it for granted and the map reduced paradigm is basically something which provides a nice high level view hiding all these lower level infrastructural details from the user. So, map reduced is a paradigm for reliable, scalable, parallel computing. That is the very first bullet in this slide. It abstracts issues of distributed and parallel environments from the programmer. Now, you might think that map reduced was introduced with the growth of big data, but no it is not. By the way, I think I gave you the impression that big data equals to web logs, but it is not. There is a lot of other big data out there, not just the web logs. Web logs were the motivating factor in the recent rise of big data, but you could just as well argue that transactions which Wal-Mart executed long ago were the big data of that era and they are still pretty big even now. Phone calls which you know, every time you make a phone call, a log is created. So, back then the US phone company AT&T had one of the biggest logs of phone calls and that was big data too. Today, our Indian phone companies have probably far bigger big data of call logs than any US company. So, the tables have turned today. So, coming back, there is a lot of different kinds of big data, some of which are very old in terms of the motivating things, some of which are new. So, parallelism correspondingly is a very old idea. It is you know, at least 40, 50 years old now, the idea of parallelism and this particular paradigm called MapReduce was introduced I think in the 1960s, if I am not mistaken. And it came from Lisp, which was also language introduced in the early 1960s, late 50s when it started, development was started. So, back then this paradigm was introduced and Google used this paradigm to build a very nice system, MapReduce implementation and that fired the imagination of everybody else and Hadoop is an open source clone of the Google MapReduce. Now, when I say parallel system, you know, you have to figure out where to store data. Now, one way is to store data locally on each of thousands of machines, but what if a machine dies? What about the data which is on that machine? How do you get access to that data? The machine is dead, the data is gone. You cannot afford that. So, you need redundancy. With rate systems, how did we achieve redundancy? We stored a copy of the data on another disk. So, if one disk died, the data was still available, but if that disk is within a machine, if the whole machine dies, you are in trouble. What do you do? So, if you look at businesses which use rate systems extensively, they buy very expensive storage systems which have multiported rate controllers, very reliable hardware, they have internal parallelism if something fails, some other part of the machine takes over. So, they have a lot of features built in to provide very high availability, but these are expensive and you cannot scale these up to thousands or tens of thousands of machines. So, the way this was done in the context of the modern big data was to first build what are called distributed file systems. So, this is a file system which runs across potentially thousands or tens of thousands of machines. It could be as small as even 20 machines and the idea is that if you store data on this distributed file system, it is stored redundantly across many machines. What I mean by redundantly? If I have a particular disk block, a block of a file, it is not just stored on one machine, it is stored on at least two and typically three machines, three is kind of the default. If two machines fail, you might lose data. So, three is viewed as giving better reliability, good enough reliability. So, each file block is stored on let us say three machines. So, if two machines die, it is the third one will still be available. If three machines die, yes, then you do not have access to data. So, now you need to know if you open a file on this distributed file system, it provides the same file system interface as any other file system NFS for example. It provides an interface to open a file, read, write to the file and so on because the file system has to take care of all the details of replication. So, if I want to read a file, what happens in file system like Google file system, which again was copied in the Hadoop file system. Hadoop is the open source version of the Google file system. There are others too. What happens is the same block is stored in three places. There is a master which tells the client. Supposing I open a file, there is a master which tells me here are the blocks in the file that you ask for and here are the places where that block is stored. These are the machines which store these blocks. So, now I can go to any of these machines and read the blocks. If I go to one of the machines and it is dead, I cannot reach it. I can always go to another machine and read the block from there. So, the death of one or two machines will not prevent me from reading data. If I want to update data in an existing file, I have to go write all the copies of that block. If I want to add a block to a file, I have to tell the master. The master will say that here are the machines which will store copies of your new block and then I have to go store the block in all those files. So, all those actions are done by the client. The master merely tells the client where all the data should be stored. In other words, the master keeps the metadata, that is, what are the files, where are the blocks of the file stored and so forth. Well, the actual data is parallelized across all the machines that are participating in the file system. So, that is conceptually how a distributed file system works. Practically speaking, you can open a file from any of thousands of machines and regardless of where the data is stored, the file system will fetch the block and return it to you and will let you write to a block or append to a block. So, that is the underpinning of all parallel processing. Like I said, if you do not have it in a distributed file system, you have to manage the replication. In fact, if you go back before the Google file system era, which is about now, about maybe 14 years or so old, before that what did people do? Parallel databases existed for a very, very long time. So, these old parallel databases did not have a file system, but they instead stored data on their own and they did the replication themselves. So, you would have many machines and there is a parallel database. There is a system which managed all these machines and it would decide which machine stored copies of what parts of the data and it would do exactly the same thing, except it was not a file system. It was a database. So, you do not have to worry about files, you have to worry about relations and you have to worry about how to partition a relation. So, let me show a slide here, shows the following. You have a relation R, a relation S and what has been done is it has been partitioned. Now, we have seen a slide almost exactly like this in the context of hash join. The idea there was you partition the relation such that each piece fits in memory, at least S naught, S 1, S 2, so on, those fit in memory. Here the goal is different, here also the partitioning is done. In this case it was for a join, but in reality the partitioning is done up front. Here I am showing a whole relation S is, but it is actually stored partition. So, it is already broken up into pieces R naught, R 1, R 2, R 3 and stored across many machines. So, I have not shown the partitioning here, but imagine that R itself is already partitioned on something and now if I want to access R, I have to access all the partitions. Now, if I want to do a join in parallel, what happens here, this step here, if you can see the most pointer here is essentially called repartition. It is stored partition in some way and in order to do the join, I want to partition it on the join attributes. This is exactly what we did for hash join, but now the goal is parallelism and the partitioning is across different machines. So, each of these R naught, R 1, R 2, R 3 is going to be on a different machine. So, there are lot of machines in the system and the data is broken up across all these machines. In this case the partitioning is done on the join attribute and similarly S is also partition on the join attribute. After we have done this, in the case of hash join if you recall, what did we do? We said we can join R naught with S naught and we do not have to join R naught with any other partition. So, this machine can do the join, processor P naught can do the join of R naught S naught. Similarly, R 1, S 1 are sent to processor P 1 and it can do the join of R 1, S 1 and so forth. The key thing to note is that processor P naught, P 1, P 2, P 3 and so on can run in parallel. There is no need for them to talk to each other after the partitioning has been done. So, first you may do some repartitioning, then you do the join locally on each machine and then you might take the results, store it locally and then you might repartition the result to do something else. So, this is a small example of parallel join. So, we have shown you two things here. One is parallel storage. I did not show you the details, but relations would be stored partition in some way and on top of that I did a parallel join. I can also do other operations. For example, if I want to do aggregation, I can do the same thing. I would first break up the relation on what attributes. There is no S naught here, just R. So, this right half of the figure can be ignored. Just take the left half. I would take R and partition it on what attributes? I would partition it on the group by attributes. We saw this. If you wanted to do aggregation, you can sort on the group by attributes or you can partition on the group by attributes and do the aggregation locally on each machine. If I partition R on the group by attribute, what do I get? All the R tuples for a particular group will land up in R naught. All the R's for another group may land up in R 2, but the important thing to notice because I have partitioned on a group, everything in one group will land up in the same place. Now, that leaves the question of how do you do the partition? So, let me go to the white board and explain this briefly. How to do partition? One of the simple ways of doing it is called range partitioning. In range partitioning, I create a partitioning vector which looks like this. Let us say I am partitioning numbers and I have a range partitioning vector which says 10, 33, 47. It has to be sorted 66 and let us say 83. So, essentially this is going to say that anything less than 10 goes to partition, let us say P naught and P 1 has things which are between 10 and 30. So, P naught is less than 10, let us say and P 1 is 10 less than or equal to let us say I am partitioning on some group by column G, let us say. 10 less than or equal to be less than 33. Similarly, P 2 is 33 less than or equal to that group by column value less than 47 and so forth. Finally, I have P 3 is 47 to 66, P 4 will be 66 to 83 and P 5 will be greater than or equal to 83. So, those are the partitions I get with this range partitioning vector. So, the basic idea is that I will break up the tuples in this relation based on the G value. Supposing, I have a relation with the group by attribute G and some other attributes let us say X and Y. So, if G is 95, where will it go? It will go to the last partition P 5, it will go to that processor. So, these are the processors, 6 processors are there. If I have another one with let us say 50, where will it go? It will go to this one P 3, because it is in that range. So, I will take the tuples of the relation and partition them across this. Now, R might itself be stored partition in some way may be arbitrary just in the order in which tuples were received, it might be stored in some machine. So, a repartitioning involves having a number of machines, I have a number of machines which store the data and a number of machines to which the data needs to be sent in order to do group by or join or whatever. So, each machine might send data to all the other machines. Similarly, this might send data to all the other machines and so forth. This would send data similarly to all the machines. So, there is a lot of data movement anytime I need to repartition data, but this is required step for this kind of parallel processing. So, this idea of doing parallel processing for relational operation, I have just shown you join and group by, but you can do this for all the other operations. Sorting can also be done in parallel, hashing can be done in parallel. So, pretty much everything can be easily parallelized. I am not getting into the details, but it is not too hard. There is a detailed description in chapter 18 of the book on parallel processing. So, coming back, map reduce is based on somewhat similar paradigm and I will show you the details coming up, but before that let me motivate map reduce going as a paradigm which goes beyond just purely relational data. So, supposing we have a log file like this. This is a simplified version of a web servers log. So, what does it say? On this date at this time somebody access this file slide dir slash 11 dot ppt. Maybe this is a log for a book website and it has this information. Actually, it has a lot more information. It tracks which IP did the request come from what was the referring page and there are a bunch of other stuff which we have removed to simplify the example. So, now I have all these log files and I want to do some analysis. So, here is a very simplified example of an analysis. I want to know how many times each of the files in this directly. By the way, there are obviously many other files on the website. Not all of them are in slide disk. Some of them may be in other directories. So, my goal here is find how many times each of the files in slide dir directory was accessed in this range of dates from January 1st 2013 to January 31st 2013. So, I need the date field. So, how do I do this? Given that you know my suppose for the book site there is just one machine and the logs are pretty small. So, it is not really an issue for our book site, but supposing you were you know Yahoo or you know one of the newspaper company and so on. You have lots and lots of machines which are serving data and each of them has a copy of the log file. So, you may have thousands or tens of thousands of log files and each of those log files may have some relevant data. Now, if I run a sequential program collecting all those log files doing it one log file at a time, it might take forever if I have very big website. Now, one option is to load all these log files into a parallel database and then run this query. It is a very simple query. It is just a select query followed by a group by because I want to know how many access for each file. Select on the date group by on the file name sorry select on two things. Select on the date and on the prefix of the file name. I only want accesses to files which are in slide directly. So, there are two selects on date and this prefix followed by a group by on this file name and the aggregation is count. How many times each of them was accessed? So, count aggregates. So, it is a very simple SQL query. Easy to parallelize. Parallel databases handle this kind of query very well, but the issue here is that loading it into a database is expensive and parallel databases were expensive at that time too. So, people prefer to build their own parallel system to do this. You can build your own custom parallel program for just this one task, but now if you want to do a second task again you have to do all of that very expensive. The map reduced paradigm provides a clean way of doing this. So, let me explain what the paradigm provides and then how it is implemented. So, this was inspired from the map and reduced operations which were initially proposed for languages like LISP. So, when back when they were proposed parallelism was not really goal. The goal was to be able to declaratively specify certain operations which could be done on lists. So, you map that is you apply a function to each element of a list and reduce would combine it across many elements of a list. Now, soon people realized that that paradigm was very nice for parallel processing and indeed it was used back in that era for parallel processing. The Google people realized that this is a good paradigm for their work too. So, let us see what this paradigm does. In this paradigm the user has to provide two functions, map and reduce. The user defines these functions. The user also has to provide some other in configuration information, what is the input, where does the output go and so forth. So, we will see all that later, but assuming the data is already available the user provides two functions. Map takes a key and a value and it returns a list of key value values. Reduce takes a key value and a list of values and reduce returns a single value. So, if you look at reduce it is like a group by operation. What it has done is it has grouped all the values output by map. Map is like you know taking some input and creating a number of tuples. k 1, v 1 are the values in the tuples. k 1 is essentially the group by attribute, v 1 are the remaining attribute. What reduce is doing is once the grouping has been done all the values in a particular group are made available to the reduce function. So, the reduce function parameters are a key that is a group and the list v 1 is a list of all the values in that group and the job of the reduce function is essentially to do the aggregation and it returns the aggregate value. That is intuitively what the reduce function does and map can function gives this input to the group by from whatever input it has. It may take files and then generate this that is a typical use. So, for our example the one which we just saw how many times each file is accessed. We will assume that the system takes a file like this and breaks it up into records. So, each line is a record. The system does not know the format of the internal format of the record, but it has been told that each line is a record. So, the system will break up files into lines and calls the map function with the value of each line. So, the key is typically the file line number and the name is also available, the file name if required and the value is the contents of that line. So, that is those are the parameters to the map function and what does the map function do? It is going to return key value pairs. The key of eight outputs is not the line necessarily the line number. In our case we will see what it is. So, here is our map reduce example for the line for the motivating example we just saw. So, what is the map function doing? It is taking a key and a record. The key is the line number, the record is the contents of one line. I am going to break that line into three attributes. So, I have string attribute three. So, I am breaking up the record into tokens based on the space character. So, I have not shown how to do this, but in Java there are simple tokenization functions which can break up a line into multiple fields. So, essentially on this data the first field will be the date because there is space after date. The second field will be the time and there is a space after that. So, the third field will be the file name here. So, I have broken it up into date, time and file name from attribute 0, 1 and 2. Now, what the map function does? This is pseudo code. If the date is between January 1st and January 31st, 2003 and the file name starts with slide there. It calls a function called emit file name comma 1. That 1 is just something that is initial count which will get added up later. The file name is the group by value. I want to find the count per file name. So, it is emitting a number of these and these are collected together and we will see an example coming up. They are collected together. So, there are many log files and the map function is being called in parallel on many machines on different records. The output of the map function on each machine is collected together and then some sorting is done in parallel and the result of all that parallel sorting is that the records for a particular file name are all brought together and the reduce function is called for each file name. Now, this also runs in parallel and I will show you how in just a moment, but the for a given file name there are many different things emitted here. I mean it is actually many copies of the same thing. The same file name will be emitted with the value 1 many, many times. Every time it is accessed this will be emitted. So, when all of those are collected together you get this string key which is the file name and a record list which is basically a long list containing just the value 1 many times and what does that do? The reduce function it takes the key as the first thing with the key and stores it in the file name and then for each record in record list count equal to count plus 1. It is just counting how many entries are there in this list that is exactly the number of times the file was accessed and at the end it outputs file name comma count. So, it has computed the aggregate count and it is emitting the file name which is the group by attribute and the count value and this again is done in parallel on many different file names and the outputs are all collected together and returned to the user. So, here is a diagram which shows what is going on. There are the map inputs that is key value. In our case the key is the line number and the value is the line content. The map function takes this and outputs these. In our case the map function simply returned the file name and the count 1 just one thing, but in general you can each input map record can result in many outputs. We will see that coming up. Now, all of these are done essentially in parallel across many machines and each machine is going to generate a number of such key value pairs. Now, they have to be partitioned and all the key values let us say R k 1 that is reduce key 1 that particular value is generated here it is also generated here. So, both of those have to be collected here. In this case the reduced values were R v 1 and R v 7 and may be more. So, the reduce function is called with the list R v 1, R v 7 and may be other things. Similarly, R k 2 reduce key 2 was generated here and also here. So, if you look here reduce key 2 has the associated list R v 8 and R v whatever I have something. So, that is there. So, this step also requires a lot of repartition because these are done on many machines reduce key 1 is going to be on one of the machines. So, all the things with reduce key 1 have to land upon this machine. This reduce key 2 may also be on the same machine. So, all the things with reduce key 2 land upon this machine, but reduce key 7 may be on another machine. So, everything with reduce key 7 has to come to this machine. Now, how do we do that? If you see a white board we saw exactly how to do that. This is what we did we had a range partition. So, we had different values and they land up in different partitions. So, the map reduce paradigm does range partitioning on the reduce key. So, that one machine will be responsible for a given range of key. So, machine 0 has all the keys with value less than 10. This one has between 10 and 33 and so forth. Now, here these are numbers in our example they are not numbers they are file name, but the same principle holds. We have may be an alphabetical sorting and partitioning on file name alphabetical ranges. I think this is a good point to take question before we move into another map reduce example. So, let us take questions. Dronacharya. Hello sir, am I audible? Yes, please go ahead. Sir, my question is how do we handle security constraints related to big data? Security constraints on big data. So, that is a completely different topic. There are issues in privacy who is allowed to see what and there are that is a complex issue. So, let us not get into that at this point, but yes it is a serious issue. For example, this is a company called America online which used to be one of the biggest internet companies long ago. It is now a fraction of its old size, but that company decided to release some search logs thinking it will help researchers. And it turned out that the search logs had enough information to identify which person had issued which query. It turns out most people do a search on their name sometime or the other. I am sure all of us have done that. It also turns out that most people query their locality. They want to see what is nearby. So, if you look for queries that mention pin code or place names, they would have that query. So, although it was supposed to be anonymous, they found out they could actually track down which person had issued which queries in many cases and that led to a big mess. The person was actually a very nice person who thought he will help the research community by releasing search logs got fired from the company as a result. It was very unfortunate. It was a nice guy. I think it was an Indian incidentally, but that is life. So, there are security issues, but that is not our focus here. If you have any other question, please go ahead. Sir, next question is can you brief us about briefed big data analytics? Yeah, big data analytics. So, essentially what we are doing is describing the infrastructure for big data analytics. Big data analytics is basically running more complex queries on big data and what I am doing now is laying the groundwork to understand how the map reduce paradigm works. On top of this, you do many things. You can write queries which are equivalent of SQL queries which are used in OLAP system. OLAP is online analytical processing. Here it is not quite online, but similar queries can be executed on big data. That is one kind. Another part of analytics is data mining. So, there are data mining algorithms have been coded to run on the map reduce platform. So, you can do data mining on large volumes of data. So, these are all part of it. So, I am not going to be able to cover the upper layers, details of analysis and data mining, but my goal is to familiarize you with the lower layers so that you know what is going on and then you can go read up on your own about the upper layer, the actual analysis part. Does that answer your question? Okay. Thank you. Thank you, sir. You can take a question from some other speakers. We have Om Institute, Hariyana. Yeah. Good morning, sir. My question is what is the difference between integer value and string field in indexing? What is the preferred data type for indexing? Okay. The question is on indexing integers versus strings. We all know about type systems in programming languages and databases also have types and you can index integers, you can index strings. It does not matter. You know, the type is a function of the data that you are modeling. If you have a salary field, it had better be an integer or a numeric. If you have a name, it cannot be an integer. It had better be a string field and you can index either one. It does not matter. B plus trees do not depend on the type as long as the type provides a very simple function, which is a comparison function. So, more specifically, B plus trees depend on having a total ordering on values of whatever type it is indexing. So, integers are totally ordered. That is, given any two integers, I can see if an integer is less than another. Similarly, strings are totally ordered on alphabetical order. Given two strings, I can compare them alphabetically and say if one is less than the other, of course, they may be equal. There are certain other domains which do not permit this kind of total ordering. For example, if I have spatial data and I have latitude-longitude, there are ways to force this into an order. For example, I can say first sort on latitude, then on longitude. This is a very artificial ordering. I can still use it in some cases, but in general, it is not meaningful to order it like this. First latitude, then longitude. So, there is no physical notion of ordering of points in a two-dimensional space. They have lat-long coordinates, but you cannot order them totally in any meaningful way. So, you can order them artificially and then answer certain queries such as what item is at exactly this coordinate. You can answer that, but if you want to find what is near this coordinate, you cannot do it. And that is where R trees come in. If you do not have a single total ordering, that is okay. R trees will allow multiple attributes each with its own ordering. So, latitudes are ordered, longitudes are ordered, and R trees can be built on two dimensions like that. So, that is the difference between a B plus tree and an R tree. Thank you, sir. My next question is, how does the size of the index affect performance? The B plus tree's height is logarithmic in the size, and in fact, for all practical sizes, the height of a B plus tree would be maybe four or five at most. So, you know, it functions pretty well even on very large data. The only issue is that if you have extremely large data, you probably have extremely large number of queries too. So, you might have to partition the B plus tree for efficiency of querying. And in fact, there are parallel versions of B plus trees which are used in this big data system. It turns out that it is a very simple solution actually. The solution is, just like we range partition the data, we also range partition the index. What I mean is, if you think of a B plus tree, let me show a diagram. If you think of a B plus tree, it is a tree, but if you see the details, there is a node with a number of children, maybe hundreds of children. So, what you do is, for example, you can store each of these children on a different machine. And this root node, its partitioning is available, it is copied on every machine. Of course, if it is updated, you have to update all the copies. So, now, if I want to search for a key value on a particular machine, I have a copy of this root node locally. So, I know which child to go to. Now, these children are stored on different machines. So, I will actually send a request to that particular machine, which holds maybe I have to go to this child. So, I find out which machine has this child, and I send a request to that machine. That machine will have the subtree there, and it will do the rest of the querying for me. Now, if you partition at one level, maybe you can have hundreds of machines, but if you typically the partitioning may be done at the second level. So, this whole thing, the first two levels, you keep a copy at each machine. And so, you know given anything, where do I go to? And so, here at this level, there may be say, 10,000 nodes at this level for very large data. And this 10,000 nodes can be stored over 10,000 machines, or maybe they will be stored over 1000 machines, maybe 10 nodes per machine, roughly. So, I keep a mapping of which node is at which machine. So, I can actually do querying on this B plus 3 in parallel. I can also do inserts and updates in parallel. There is some extra work to be done, but these systems can handle that. The exact details of how they do it, there are actually differences. So, maybe if time permits, I will discuss this at the end of the big data session. We have Mon Zion. Please go ahead, we can hear you. Sir, we have heard that MapReduce suits only for homogeneous environments like cluster. How far it is efficient in heterogeneous environments? And if it is not much efficient, how does Google manage in its cloud implementation? So, to explain that question to others, MapReduce paradigm breaks up tasks into many small pieces. And thus some part of the job on a number of different machines. In fact, it is not true that MapReduce works only on homogeneous environments. What do I mean by that? So, I want all the machines to run the same kind of software. So, if I am running, how do all the machines should run Java? That is really all that I need. I do not need all the machines to be of the same speed. So, in fact, how it is done is that the map tasks can be broken up. So, it is possible for the Hadoop system to take into account the speeds of different machines and give a fewer number of tasks to some machines and more tasks to other machines. Conceptually, it is straightforward. Maybe early implementations were not good at it. But even then, if a machine was slow, so already when a machine may be identical hardware, but at runtime, you may find it is slow. So, it is not homogeneous. And the MapReduce paradigm can deal with this.  So, it can work in environments where machines are not homogeneous. Does that answer your question? Yes, sir. Thank you. Thank you. We will go to another center. We have Bharatiya Vidyapit, Navi Mumbai. Hello. Sir, can we use object-oriented database to store big data? Object-oriented databases to store big data. Not really. I do not know of any object-oriented massively parallel system. So, the key thing is that for parallelism, you need to do a lot of partitioning. The system has to understand the attributes on which partitioning is done. So, I am not aware of any object-oriented databases. So, object-oriented database that supports it. Now, in the MapReduce paradigm, you can do whatever you want in the map and reduce function. So, if your input are objects and you want to run function on those objects, you are welcome. The paradigm does not constrain you. All it needs is these keys on which it does the partitioning. So, as long as you provide the keys, you can have a parallel object-oriented system built on top of MapReduce. Any follow-up questions? Yes, sir. Sir, how we get the big data sample? How to get big data sample? Big data sample? Yeah. So, I am not sure what you mean by sample. I think what you mean is, how can we get a bit of big data to run something on? So, supposing you want to do, see, any data can potentially be big. But if your focus is on log files or something like that, how do you get access to log files? There are sources on the web which provide log files or you can create artificial things of your own. There is effort going on to create benchmarks for big data. If you take traditional relational data, there are several benchmarks which are widely used. So, there is something called, let me use the white board. There is something called the TPC series of benchmarks which were designed for relational data. Many people who are working on big data take these benchmarks and use them as the source for benchmarking big data. Because it is relational data, you can run MapReduce, you can do whatever you want on the same data. So, there is a series of TPC benchmarks of which the relevant ones are TPC-H. Then there is something called TPC-DS and some others. So, these are things which are currently used. There are some older ones also. So, these are things which are popularly used even for benchmarking big data system. But many people say that this is not representative of real world big data. So, there is an active community working on benchmarking of big data system. There is a workshop which runs I think twice a year now. Last year it was in Pune actually. It is an international workshop. So, there are benchmarks coming up and if you search for them, I am sure you will find several big data benchmarks available on the web. They are not accepted as standard yet. The workshops are trying to evolve towards standard for this. But if you are just looking for data to try out on your own, yes, there are plenty of data sets available. You just have to search on the web. We have MIT University, Haryana. Please go ahead. You can hear you. Sir, how can you see behind the scene work in the MapReduce program? What is actually happening? Hello, sir. Yeah. How can we see behind the scene work when you are executing the MapReduce program? How can you see what is happening behind the scene? How can you see what is happening behind the scene? That is not something you can see easily. There may be some consoles for Hadoop which give you some idea. But the good thing is you do not quite need to see what is going on behind the scenes. It is not exactly declarative, but the parallelism part of it is, you know, it is not controlled by you. The system does it. As long as you have written your original MapReduce program properly, if it works on a single system, unless you have done something weird, it should give you exactly the same result when it is run on a parallel system. When I say something weird, I mean something like global variables which are accessed by the map function or the reduce function. Those will cause trouble if you move it on to a really parallel platform. But as long as you stick to a function which do not use global variables, which only take the parameters which are passed to the map and reduce function and do stuff only with those, nothing else, they will work exactly as, you know, they will give you the same result in a parallel environment. Now, how exactly things are parallelized? I am going to explain it to you, but if your question is, can you observe it? You know, I do not know if I have not seen any platforms for doing this, but it is likely that there are some platforms which will let you do this. Please, Shankaracharya. Hello, good morning, sir. How can we reduce duplicate for analysis in big data? How can you reduce duplicate? If by reduce, you mean the reduce function. The reduce function will get duplicates as input, just like any aggregate function. There will be duplicates, that is not an issue. If your point is, you have duplicate inputs which you want to remove before you do analysis because the duplicates are meaningless, that is a different issue. So, if there are exact duplicates, the equivalent of select this thing, the reduce function can take multiple copies and replace it by a single copy. So, the first instance of the map reduce can remove the duplicates and then you can do your analysis afterwards. But if it is not exact duplicates, then life is a bit harder. For example, in data warehousing, there are often duplicate records, meaning things which belong to the same address, but the address has been written a little differently in each input. But they are actually duplicates. So, how do you do approximate matching of addresses to remove duplicate addresses? So, that is an issue which I think was discussed, something similar to the Aadhar duplicates on biometric, which was briefly discussed yesterday. So, now how can you do such duplicate elimination of approximate duplicates in parallel? I think there has been work on it. I am not familiar with the details. I know there has been work on it, but I am not familiar with the details. Did that answer your question or was it something else? Thank you, sir. So far, what I showed you is a simple map and reduce function and the schematic flow of keys across the map and reduce function. Now, I want to show you one more example of map reduce and then we will see how this is parallelized. So, now let us take a different problem which does not look like a database problem at all. In fact, it is not, which is given a large number of documents, count the number of occurrences of each word in this collection of documents. So, how would you do this in parallel? I think the intuition should be obvious. You want to divide the documents among workers. Workers meaning there are many computers doing this task. You divide the documents among these. Each worker will parse the document, break it up into tokens to find all the words in that document and the map output function would output word count pairs. That is this word occurs so many times in this document. Now, you partition the word count pairs across workers based on the word. So, this is the grouping so that the particular word occurs obviously in many documents. So, all of those come together at one task for doing the reduce and the reduce function adds up the word counts for each word. So, as an example here, given the, this particular function, one particular input 1 up any, 2 up any, hot cross 1. That is a document. What is the map task output? In this case, we have even simplified the work of the map task even more. The map task is outputting the following. 1 1 time, a 1 time, penny 1 time, 2 1 time, a 1 time. Now, you will notice that a has already come. The map function could have output a 2, meaning a has occurred 2 times, but that requires a little bit of extra work at the map function. We could have done it, but we do not actually need to because the counts will get added later. So, it is outputting a 1 twice. And then, penny once again, again penny has occurred twice, but it is outputted 2 separate times, hot 1, cross 1, and burn 1. So, that is the map function. Now, this similar thing would be done for each document. In this case, supposing this is the only document, then the reduce function would have got like, let us say 1 occurs only once. The reduce function would be called once with a key 1 and the list being just that 1 copy of 1 and it will output 1 with the count of 1. Now, for the word a, the list will have 2 items, which is 1 and 1. And the reduce function will just add up these numbers and get you 2. Similarly, the reduce function would be called with the word penny with the list having 1 and 1 and it will add it up to get 2 and so forth. So, this is the final output of the reduce function. This is the toy example, of course. Now, here is the pseudo code for the word count. So, the map takes 2 strings, input key and input value and then, image for each word w in the input value, it image w comma 1. Now, note that the 1 is in quotes because I am outputting a string. This is a very simplified function. The reduce function gets an output key and an iterator on intermediate values. Earlier, I was talking of lists. This is getting closer to the Hadoop paradigm, where instead of a list, I have an iterator. If you are not familiar with iterators, iterator is the construct on which you can do next or in the current versions of Java, you can write a for loop like this. For each v in intermediate values, intermediate values is the variable of type iterator. So, I can say for each v in this, in current Java, the syntax is a little different, but conceptually this is what it is. And now, v gets bound to each element of this list or set. And what is this reduce function doing? It is parsing int v because this was a string. It is converting it to an integer type and adding it up to result and finally, it outputs result. That is the pseudo code. I will show you the parallel processing and then I will come back to the Hadoop implementation. So, what is happening in the actual implementation is the input files are broken up into partitions. Why? Because some of the files may be very big. So, a big file may be broken into a number of smaller pieces. Now, these partitions are mapped to different map tasks. So, I have a number of map tasks running on n different machines. Now, where are these inputs stored? They are stored on a distributed file system and different partitions of different files are given to different map tasks. So, here I have shown partition 1 going to map 1, 2 going to map 2. Maybe these two were pieces of one big file. Partition 3 may be one file by itself that is sent here, 4 is sent there and so forth. Now, the use of program consisting of a map and reduce function is taken by the map reduce master and it sends a copy of the map function to each map task here. So, each map task has a copy of the map function. So, in Hadoop, it is a java jar file which is sent to all the map tasks and the master also tells each map task, which partitions are assigned to it. So, the map task will actually read the partitions from the distributed file system. So, the file system is just sitting idle, I mean it is not idle, it is not active meaning it can be asked to give a part of a file, it will give that part of a file. So, the master has told map task 1 that these are the files and pieces of the files in some cases that you have to process. So, the map task 1 will go fetch the files or pieces of files which it has to process, apply the map function and the output which are intermediate files, it will sort locally. So, all the outputs of map tasks which it ran, it will sort. This is part of the overall sorting and then it will partition these to the reduce task. How is this partitioning done? This is going to be a range partitioning. So, that range is available to each of the map tasks. So, it is going to range partition the keys to these reduced tasks. Now, I have shown n map tasks and m reduced tasks. So, these are parameters to the map reduced jobs which tell it how many map tasks should run, how many reduced tasks should run. That depends on how expensive is the map task and how expensive is the reduced task. If the map task is very expensive you would have more copies, maybe less copies of the reduced tasks. So, this range partitioning is used to send things locally. So, now each reduced function has pieces of each map output coming in. It is going to merge all a piece. How does it merge it? Well, we already saw how to do a multi-way merge yesterday. So, it is going to merge all this to create a merged list and then locally it is going to call the reduced functions on each key value and its output is going to be written to a file. So, if there are m reduced tasks there are m output files. So, this is what is going on behind the scenes.


Good afternoon. My name is Mark Jason Gilbert. I'm Professor of World History at Hawaii Pacific University, and I'll be your host today on Global Connections. Our guest is Rick Romer, an art director and designer, very famous within Hawaii. Distinctively, he was the art director, set director of films, theaters, and television in Hawaii for many, many years, most importantly, was the director or art director or designer for many film, theater, and television shows produced locally. And we're going to talk a lot of those because they range from magnum PI to lost. In fact, we might have a picture of lost up here. You can give an idea of the kind of work that he has done. Rick, hi. Hi, Mark. This is going to be fun because your career is so long, and it's so very interesting. How many hours do we have today, Mark? I think we'll do fine with what we have. Normally when we start one of these kinds of interviews off, we ask, you know, how you got interested in the field. I know you came to the University of Hawaii, and that was an area in which you got your degree. I actually have no formal training in film or television. I was a MFA in theater, stage design, lighting design, and spent eight and a half years at Diamond Head Theater. And because of the proximity of the theater to the film studio, it was pretty soon I was building or creating things that they didn't have time or in some cases even know how to build. So Higgins Bridge on the River Kwai was me in my toothpicks. Yes, I always remember that because it's so distinctive. And you made three models of it. Well, beginning, middle, and an end. So there's always a thrill. I mean, I'm not a performer of any kind. But when you see something that you personally have created on the screen, you do kind of get a little bit of thrill out of it. I have to admit. And this actually, just for those who are interested in becoming designers, this opportunity actually came from a dinner where someone mentioned your name. Oh, yeah. This was, I call it my Lana Turner Schwab's drugstore moment, even though that supposedly never really happened. And I wasn't wearing a tight sweater either. Not that that would have worked. But Buck Henshaw, who was the set decorator on all 12 years of Hawaii Five, all the original founding member of the set decorators union in LA, and the first three years of Magnum PI needed some help at one point. And that was sort of my entree into beginning to help. And then eventually I needed to get into the union, which I did. And just things fell into place. And was there, is there working on Magnum PI, actually, for a very long time? Was there a kind of singular moment or set direct set decorator challenge? Every day, every day was a challenge. Every script was a challenge. But at the same time, looking back on it, I didn't know how good we had it. There were so many places we could rent from, and there were so many more sources than exist today. But it was just a different time. And getting to work with people like Jackie Cooper and, I can't even think of, I mean, famous actors who became television directors later in their life. And Magnum PI was a top 10 TV show for many years. And maybe again, who knows? But yeah, there is really hard to say any one defining moment, one special set. It was just a daily challenge that I met and had a great crew and worked with really great people. But the business has changed a lot since then. The power that the set decorator had in those years is pretty much, you're now, it's the production designer. Television has gotten a lot closer to being like film than remaining how it was in those days. So a lot of changes. A lot of changes, yeah. You know, I remember, I've seen a still of Higgins' apartment at the estate in Magnum PI. And, you know, you look at it and you see that this must be where Higgins lives, this old British experienced officer. And, you know, production designers, set designers, set decorators, they all have to make sure that that's a space in which the actor actually would live, don't they? Well, I call it telling the story. And set decorating is telling a story. I actually created that set. A lot of people give me credit for when I started on Magnum, it was the fourth season, so all of the permanent sets had been created. But when they would throw in a new set like Higgins' bedroom or his girlfriend, Agatha, her home, even his living room, I got to create that. And when I say create, basically they gave me the walls, and then I made it into what it became. And in those days, I would meet directly with the director, independent of the art director, but obviously working in collaboration with and be able to have the creative, I don't want to say freedom, but freedom within what it is that I put on the set as long as I told the story and reinforced the character, which is really what set decorating is. And, you know, while you were working after or during, after when you worked on Magnum, you had a, was it two years working on Shake and the Fat Man when they were filming in Hawaii? Oh, it was way more than that. It was like two years in Hawaii, two years in LA. And the way we found out our show was canceled in LA is that Steven Spielberg had, was going to be using our soundstage for a movie he was going to make about dinosaurs. And we all thought dinosaurs, well, it was the first Jurassic Park, so obviously he lasted a lot longer. Well, people have been canceled for a lot less. Oh, yeah. Well, I had a show pretty much run its course and strangely never syndicated by the creators of the show, the Viacom, the biggest syndicators. But that was again, another really popular top 10 TV show that unfortunately kind of has been forgotten except for Bill Conrad. But it was it was a big show. It was a good show. And I got to work in LA for two years. And what was that like? I mean, you've lived for a long time. Well, it was like I called LA the land of conspicuous consumption because anything you could ever imagine was there and you could rent it. And the prop houses, the size of Macy's were common. And it was mainly, I mean, I have the ability to shop for multiple sets at the same time, just kind of file it away. And I had a great time. I was a kid in a candy store. I mean, we don't have any resources like that and probably never will in Hawaii just because of the volume that is done there. But that it was a great experience. We believe it or not, Diagnosis Murder was a spin off of Jake and the Fat Man and ultimately obviously more popular. But I was offered that show, but it was it was moving to Denver. I'd been gone for two years, Hawaii's my home. So I came back and I'm glad I did and I'm still here and I'm still working.  It was great to work with to a real pro and still is still going. Still going. Yeah. Yeah. Do you ever, you know, because of the way production, TV, film, theater production goes, did you ever have an actor who wanted to contribute to what you had done to his thing?  No, that would have been more from the would have probably gone through the director. I did have a lot of actors who wanted to buy things off the set at great discount, which could sometimes be arranged and other times not. But yeah, I actually had very little interaction with the actors, unless it was somebody like Carol Burnett or Frank Sinatra or somebody I wanted to just happen to hang around and watch. Usually by the time the actors were on the set, I was already on to the next one. As soon as the director accepted, you know, what we had done, we were out of there because there's always the next set, my next set. But if it's a really special set, or if it's somebody with an actor who I've always enjoyed or wanted to see more of, could delay a little bit. That's really interesting. Do you, when you mentioned a little bit earlier that things have changed in terms of set design, set decoration, etc., why is that? Well, a real obvious one is technology. We're sitting in front of a green screen that the viewer may be seeing the Eiffel Tower or the Parthenon or anything they want to put back there. And for example, on Y5O right now, they can do three and four moves a day because they're hauling around digital cameras and much smaller lighting equipment. In the old days, when they had film cameras and needed all these, you know, heavy equipment and generators, moving at all was usually a big deal because while you're moving, you're not filming and when you're not filming, you're not making money, so it all translates to that. So the action in films is television. When you look at something like a Magnum PI episode and it's not airing here, but on occasion and when it does, it seems kind of slow moving. 1983, 1984, MTV changed the way we film things. Two seconds is kind of a long shot now. It's one second, half a second, things happening, cars exploding, running into a room. Clear, clear, clear and they run out. Some set decorator had to create a whole set for McGarrett to run into and say clear and run out of the set. And so you have a lot more activity, you have a lot more action and that's what people want. And so that has changed. My working relationship, I have actually the first person from Hawaii to get into the art director's guild working at a level that I would now tell the set decorator what I wanted to see, what my vision was. When I started, it was my vision, but it's changed. Responsibility has changed, the amount of detail has changed, high definition TV, you're seeing labels on things. Clearance, I could hang any picture I wanted on a set and now unless you can clear that picture, meaning get the person who has the rights to it, which is not you, just because you own the picture doesn't mean you have the rights to it. And if you don't have the rights or you can't get the rights, you can't hang the picture. So it adds a lot more, there are now full-time clearance people as part of the crew who do nothing but clear images or clear backgrounds so that they don't get sued. And so there's a whole world of things that we didn't even think about back then. And so yeah, it's changed quite a bit. You mentioned casually that if you had an opportunity to see an actor at work or get to talk to them a minute, did you ever have an opportunity to bring someone onto a set in a background or something like that? My sister happened to be visiting me and it was her birthday and we were filming a big scene with Sawyer on Lost and it was at Bob's Big Boy that we had made into a Iowa diner and I talked to the person who places the extras. She was a good friend of mine at a second AD and she put my sister in a location that she was guaranteed to be seen a lot.  Well, she wasn't cut and she was there and she was right next to Josh Holloway and she had a great time. It was a very memorable birthday and more people saw her that day than probably saw Olivia on the stage in his entire career. I mean, that show is hundreds of millions of people all over the world. I remember once since the White Pacific University, it's on 4th Street Mall, it's downtown campus and I went into class for a couple of hours and I saw them setting up the street from the shot and when I came back outside it was Bangkok with all the signs and I think you've mentioned this to me earlier, the idea of wrapping the bottoms of the palm trees so they look like a walnut or... Oh, yeah, there actually is more of the art department than set decorating but they're what they call skins that they can put over things to make them into other things. And of course, you're limited as to how high that skin is that you can actually see. But yeah, we, downtown Hawaii was London. It's been, I can't even think of all the locations. You know, Big Ben chiming over 4th Street on another episode. It was fun to see what they would add to what we had already done. But yeah, we turned a lot of places into other things and that's part of what Art Direction does is if you were to ask me what is Art Direction, it's basically everything you see on the screen except for the actor. It's what's in the room, what's behind them, what they interact with, the doors they open and of course you're not officially watching that but it interacts with the actor and the actor is casting and hair and makeup and wardrobe in terms of breaking down what departments are involved with them. But the art department is, it's a big department and it can range from creating a set from scratch in a studio to modifying an existing set on location and anything in between. So it's a pretty wide department. Just for the fun of it, the descendants was filmed in Hawaii and they made a big point of using actual locations. So if a goat was tethered to the lawn and was eating the grass, it stayed in the frame, so to speak. Do you ever have a favorite scene set in Hawaii or something that was of particular interest to you? Because again, Hawaii, for example, in Los, they turned the subterranean satellite city hall underneath King Street and they turned the steps down to it into a London subway. Which was probably just a sign and us telling you that it was the London subway and then you of course accept it because yeah, no, it's hard to, I mean literally thousands of sets to have. If I had to pick one, it would probably have been, I think it was the second season I had done of Magnum, which would have been the fifth season and I was able to furnish the Cook Spalding House, which later became the contemporary art museum, furnish it one more time. I had a huge budget and it was starring a relatively unknown actress playing the good sister and the bad sister named Sharon Stone. Oh, that's right. Yeah, that was something. You could kind of tell she was going to go someplace, but so she did. But to see that house that was so magnificent, furnished one more time before it was turned into a museum, that was pretty proud of that. And of course, the other issue I guess I should mention is by the time I was doing 5.0, I would say anywhere from 60 to 80 percent of what we did on a set was not seen at all. You simply did it because you didn't know where they were going to film. And whereas back on Magnum, we had directors who would say, I'm only going to see from here to here. And you could trust them. And later, if they said that, they'd come in and say, no, we're going to see over here. No, no, and it's not dressed. So that also has changed. It's just different. You give them 360 ceiling floor, everything. And so it's more costly, but it's just how it is. We'll come back after this short break. Aloha. My name is John Wahey. And I used to be a part of all the things that you might be angry at. I served in government here and may have made decisions that affects you. So I want to invite you in. I want to invite you in to talk story with me and some very special guests every other Monday here at Talk Story with John Wahey. Come on in, join us, express your opinion, learn more about your state, and then do something about it. Aloha. And welcome back to Global Connections. We're talking to Rick Romer, designer, set designer, art decorator in Hawaii for many, many years, working on everything from Magnum PI to Lost. And we were talking about individual experiences that you might have had. Later on, we'll talk a little about the career of a set designer, set decorator, and your own work more recently, working as a designer. But I'm always curious. I saw the first episode of Lost in real time, so to speak. And that plane crash was pretty impressive. It was downright scary. Tell us something about that. Well, a little bit of background on that. We had three pilots being done that year, and Lost was the last one. I had actually done North Shore, and we'd even started the we were on episode one. They really wanted me on Lost, and I turned them down three times. I said it's a plane crash. I don't know, bodies and burned luggage. But as it turned out, it was especially that first season without a lot of the network and corporate involvement that later resulted on that show. It was just an amazing experience. And actually studying debris fields, it kind of got into, but actually the way JJ Abram shot the pilot, it was pretty much, I call it my haul and dump theory of set decorating, where you simply haul everything and dump it, and they pull out what they want for each shot. Even though we had these things all we thought figured out, things were created basically for every shot. And of course, we had that big hulking plane in the background, the burning one on Mokolia Beach, and we had the fuselage was in Heiakea in the jungle. It was a real plane. It was cut into pieces and shipped over here. And we had to move it at one point when flooding occurred during the winter season, which actually prompted the script to say they're going to be moving out of the plane, which the show was kind of fluid. I mean, they literally did make a lot of it up as they went along. So our moving of out of the plane into the jungle as it were upon Police Beach was kind of caused by the fact that it was a surf in Hawaii and they didn't fight mother nature. They went with it and it became part of the story. There's an interesting issue, which is, what about this kind of job today? Well, today, again, things have changed a little bit. More and more the films that are coming over here pretty much bring everybody with them. They bring at least through the decorator, maybe even the lead man, all comes from LA. And it's primarily because these people have worked together before. And I understand that if I was going to go to Des Moines and do a feature, I'd kind of wonder, well, who am I going to find in Des Moines? Well, as it turns out, there might be some good people, but not knowing that ahead of time, you might feel more comfortable bringing people that you've worked with. And that's kind of how things have been going. So I have actually been doing more. I just art directed a national supercuts commercial, a great, pretty famous director. You kind of have to wear a lot of different hats in Hawaii. You can't just say I'm a set decorator or I'm an art director. You want Christmas decorations, I'll do them. You want a big party, I'll do it. I've been creative director for a local events company. And it's all part of the same world. It's design, it's creating. And I find it all just as interesting. And you certainly can't get stale. You have to keep reinventing yourself, reinventing your work. And you don't really have a look. Your look is, well, what look do you want? And that's the look you get. So you don't want to be too tied to, you know, you only do this or you only do that. And in Hawaii, you can't be because you're doing so many different things all the same time. So it's one of the challenges and also one of the things I enjoy most is that I get to do a lot of different things here. And if I'd stayed in LA, I'd be, you know, one of 200 other set decorators or 500 art directors or whatever. So the tradeoff is, you know, it's a few lean times here and there, but it's kind of how it is. And you just do something else. That's all. Well, recently you did a little work on Lion King? Oh, that's a whole, that's a whole nother career. But something that's kind of funny how it happened. I worked in theater for more than 10 years in lighting and set design. And for some reason, the only work I've had here, professional work, has been as a dresser on everything from Lion King. I forget 150 some performances over a five month period. Les Mis, Phantom of the Opera, and just basically anything that's come to Blaisdell, even an occasional opera. And it's a connection with theater that I in some ways never really had because usually by the time the show opened, again, I was on the next one. I wasn't there every night. But it's a discipline. It's a whole different mindset. It's really not creative, per se, because you're doing exactly the same. In fact, creativity is strongly discouraged. You do exactly the same thing you do every night in exactly the same order. And if something else happens, then you kind of go with it. But occasionally things would happen. It's live theater. But I love, it's still my little theater heart working backstage. I still enjoy it, although it really has literally nothing to do with film and television. But I'm fortunate that I usually wind up getting the leads, which is I'm honored to be working with the level of some of those people. And they expect and demand a little more. And I give it to them. So it's a challenge. I love challenges. So it's another aspect of what I get to do in Hawaii. That's great. Well, we have two images to look at just as we come to the close of the program. One of them is the McGarrett's home. There we are. There we are, which because of some distant connection to the people who owned it, I actually went to a party there once. And before it, I think just as FIBO was revived. Well, this was an interesting challenge because it was an existing home. And they had chosen it for the pilot. And I don't get to say anything like he's the cop, but he's got a house on the beach. They always have houses on the beach. So anyway, we furnished it according to the vision of the director primarily, whose favorite color was brown as it turned out to be. But so when the series went, and I started as the set decorator, filming there, pretty much every episode required that we went into their home. We packed up all of their things, we brought in all of our things, and we had to repack up all of you know, it was a several day process. And about halfway through, well, I'm not halfway through, maybe five or six episodes into season one, they said, let's build a duplicate of their of their living room on our soundstage, which was then at the advertiser building. So it was an interesting thing because some of the objects in the on the set belonged to the owner, which we couldn't use. And so we found, I don't know that anybody really noticed that there was kind of a little shift in things at one point in the show. But we built a duplicate of the house and got to make doorways a little wider that were a little inconvenient to get equipment through and make a few little changes. But and then actually started adding rooms. We added a kitchen that the kitchen in the house was way too small to film. Actually, I remember that kitchen very well. It was very small. Yeah, it's like a 50s kitchen. Well, it was like a 30s kitchen, but maybe remodeled in the 50s. But yeah, it was the joys of September. Right, right. In our direction. We've been talking to Rick Romer, and we enjoyed it. I certainly did. I hope you did. Please watch for global connections every Thursday at one o'clock. And thank you very much for your attention and thank you, Rick, for being with us today. Thank you, Mark. Great. Okay.