Thursday, April 28, 2011
Monday, April 25, 2011
Checkpoints are a technique for improving a program's fault tolerance by preserving the program's state. Checkpoints can be used to recover after a program crashes or used to save the state for later analysis. They are literally dumps from the program that are sufficient to reconstruct the program's current state.
Saturday, April 23, 2011
Const is a modifier in the C++ programming language that marks a variable as constant or un-modifiable. One of the primary uses of const is to simply have variables behave like constants. For example, this can be helpful in making complex equations readable. Another use of const is to prohibit a method from modifying data that is passed in by reference. This prevents intentional or unintentional side effects to that data.
Peter was frustrated. In his first seven months as an apprentice at the library of Alexandria he had never had a patron intentionally deface a scroll. Now it was happening almost every day.
Peter had noticed the first incident while re-shelving a scroll on building donkey-pulled carts. Half-way through the scroll one of the instructions was edited. The phrase "Secure with four nails." had been rewritten as "Secure with three nails (that is good enough)." How could someone do this? Peter knew that the perpetrator probably believed that they were being helpful and improving knowledge. But in reality, they were defacing the library's scrolls with their own opinions.
Peter decided to consult the master librarian.
"It is a sad day." agreed the librarian. "We need to find out who is doing this and ask them to stop."
"Ask them to stop?" cried Peter. "We need to do something more than just 'ask'. How about a lifetime ban from the library?"
The librarian shook his head sadly. "Perhaps." he agreed.
But after three more edited scrolls were found, Peter was too angry to wait. One night after work, he explained the problem to his friend Sarah. She had gone to high school with Peter and was now employed a few blocks over as a wizard's apprentice. She often grumbled dreadfully about the lack of interesting problems for apprentices in her field.
"Oh! Oh! I can help!" she claimed excitedly. She was visibly bouncing in her seat.
"How?" Peter asked suspiciously. He had had mixed luck with help from wizards in the past. In fact, he still remembered the incident that had left him without eyebrows for almost three months.
"I just learned the Const spell of immutability!" she proclaimed happily.
"Const spell of immutability?" asked Peter. This sounded like the type of spell that would end in disaster.
"Yes." answered Sarah. "The spell makes it so that you cannot edit written documents. It is usually used for things that you do not want changed, such as legal documents or poems."
"Sure. Poets sometimes ask us to cast the const spell on their poems, so that they are forced to stop fiddling with their work. This one poet was stuck tweaking on the same line for 10 years before we finally made the work constant. It actually happens more than you would believe."
"Oh… interesting." was all that Peter could think to say.
"Can I use it on your scrolls? Please? I am so bored. I could really use the practice." pleaded Sarah.
Peter fought back images of the library accidentally being destroyed by a rogue spell. He quickly agreed before he could think better of it.
That night Sarah spent the entire night wandering around the library casting her spell on the scrolls. It was a slow process. Peter sat behind the desk watching nervously. Nothing burned down or exploded, so he considered the night a victory.
As Sarah was finishing, Peter realized that there was a question that he had never asked.
"What happens if someone tries to modify the scroll?" he asked.
"They can't." answered Sarah.
"I know, but what stops them? A voice in the back of their mind? A forcefield? A stabbing pain?"
"Forcefield." answered Sarah. She sounded tired. Then again, she had been casting the same spell over and over for hours.
The next day Peter sat behind the main counter of the library, trying hard not to fall asleep. Then, he heard a man at a nearby desk muttering something loudly. Peter peered over at the man. The man was trying to write something on the scroll, but his hand was stopped inches from the paper. The man looked confused as he struggled to move the pen closer. Finally, the man shouted something at the paper and stormed out of the library. Peter smiled to himself; Sarah's const spell had worked.
Wednesday, April 20, 2011
Monday, April 18, 2011
Thursday, April 14, 2011
Packets are discrete units of data that are transmitted over certain types of communication networks. Packets can also contain metadata used to route, decode, and assemble the data. Large data payloads can be broken up and transmitted using multiple packets. The receiver can use the information in the packets to reassemble the full data on the other side.
Ann was traveling to the famed library of Alexandria. If any single location in the known lands held information about the coming darkness, it would be the library of Alexandria. Ann had heard the library described in a whispered reverent tone since she was a little girl. It was rumored to have almost 100,000 scrolls!
As she approached the great Mississoppoly river, she saw something that surprised her. The road traveled straight to the river's edge and stopped. There was no bridge. Ann saw a cluster of people and carts standing near the river's edge.
"Where is the bridge?" she asked.
An old man gave her careful look. "There is no bridge." he finally answered.
"But, how can I get across?" Ann inquired. The very core of her mission was threatened if she were trapped on the western side of the Mississoppoly.
"Ferries." responded the man.
"Fairies?" inquired Ann, scanning the air around her to see if there were any flying nearby. Ann loved fairies. They were such wonderful magical creatures. She had once met the Fairy King in the royal palace when he had come to visit her dad.
"Yep." said the man.
"But, I don't see any." responded Ann. At the same time, she was struggling to figure out how a fairy could help her cross the river. They could not exactly care very much. And, despite the stories, fairy dust was nothing more than sparkly dust that was almost impossible to get out of your clothes.
The man pointed out across the river at a few small boats slowly making their way across the river. A few were heading toward the opposite shore and a few were coming toward Ann.
"Oh. Ferries. I see." Ann was disappointed.
"It'll be 'bout a 2 hour wait." the man advised.
Ann nodded an acknowledgement and dismounted her horse. She led the horse over to a shady patch with long grass. While the horse chewed at the grass, Ann sat and watched the boats come in. The first boat to arrive held 8 crates of supplies. Two soldiers unloaded the boat, placing the crates on a a half empty train of carts nearby. As soon as they had finished, they returned to waiting against the last cart. Twenty minutes later, another boat arrived with 4 more crates of supplies and a third soldier. Together, the three soldiers moved the crates onto a cart. Ann was intrigued.
"Excuse me." she called. "What are you doing?"
The soldiers looked confused. "Shipping supplies." one of them answered as though it was the most obvious thing in the world.
"Yes. I understand that." agreed Ann. "But, why do you send them over different boats? Why not just ride one boat over?"
"Too much stuff." called the old man from behind her. "You can't fit all that on the boat."
"Then why not use bigger boats?" asked Ann.
"Ah. Right. Why did I never think of that?" laughed the old man, who Ann now realized was the ferry master. "Just use bigger boats."
Suddenly, his face got serious. "You know what big boats cost to run? Or how long they take to load and unload? I could end up holding up a tiny shipment for days while I am loading a bigger boat. And how big a boat should I get? No matter how big a boat I pick, someone will always have a bigger shipment to get across. No, no, no. Better to use packets."
"Packets?" asked Ann.
"Yes. That's the name of these here smaller boats. Sure, we have to split up some shipments to get them across, but it is a tradeoff. Sometimes we have a lot of little trips to make and the boats have some empty space. And sometimes we have bigger loads. But as long as we can break the loads up and put them on packets, I can get them across. It just means that someone has to wait at the other side for all the packets to arrive and then reassemble their shipment. "
"But what if you have a HUGE supply train?" asked Ann.
"Then I send a lot of packets across, don't I?"
"I guess so." agreed Ann. There was a simplicity to the system. "But doesn't a large shipment slow everything down?"
"The nice part about using many small boats is I can do multiple shipments in parallel. If I am shipping a hundred packets worth of wheat across the river and someone comes on their way to the hospital, I can send them off in parallel. That is one of the beautiful things about using a lot of small boats. I do not need to finish loading one huge boat before starting the next. I can have multiple streams of shipments going on at once. Of course, there is some per-boat overhead; you need to get it into the dock in the first place. So, really tiny boats would be too much coordination."
Ann had to admit that the system did sound flexible. She remembered hearing that her brother had to wait for three days before his first ocean voyage, because it took that long to load the boat. She could not imagine such delays being feasible for a river crossing.
"And they just go back and forth all day?" she confirmed.
"Mostly. Although there is a little more to it than just the cargo and the boat. The captains can get instructions to travel upstream or downstream a bit - to different landings, you know. There are four on this side and three on the other. This particular landing gets most of the traffic, because of the road."
"Are there any south of here? Closer to Alexandria?" inquired Ann.
"Sure. I can send a packet to the landing at Gretock. It is a nice, little, basket-weaving village. Might save you a few hours if you are on your way to Alexandria. It will still be about a two hour wait though."
Ann was thrilled. She continued to watch the small boats flow in-to and out-of the landing for the next two hours. Then, when her turn arrived, she happily boarded one of the boats and continued on her journey.
Tuesday, April 12, 2011
Saturday, April 9, 2011
Thursday, April 7, 2011
Peter had been in line for two hours when he felt the tap on his shoulder. He felt a pang of fear as he looked behind him. Terrible Todd glared angrily back. Then again, Terrible Todd always looked angry to Peter.
Terrible Todd was best known for his recent performance at the annual Alexandria area rock throwing contest. He was the first candle maker's apprentice to win the main event. His winning throw used a two hundred pound rock and the reverberation could be felt two miles away. Unofficially, he was also known for being a mean bully.
"Hi Todd." Peter meekly greeted him.
Todd grunted back and motioned Peter out of the way. Peter held firm. He refused to give up his place in line. Season ticket sales for the East Alexandria soccer team started in an hour. This year Peter was determined to get premium season tickets. He had his heart set on midfield.
"I am sorry, Todd. I was here first." Peter explained.
Todd looked Peter up and down. Then, with a louder grunt, Todd picked up Peter, turned, and set him down behind himself.
"Hey!" Peter cried, but Todd was already tapping the shoulder of the next person in line.
Peter fumed. This was not fair. Why should Todd get to go in front simply because he was larger? There were principles to these things.
As Peter ranted silently in his own head, he watched Todd slowly work his way up the line. One person at a time, Todd swapped places with smaller people. Todd’s advance was only halted when he reached Wren, the muscular blacksmith.
Then Peter felt another tap on his shoulder. Turning, he saw Big Jim. With a sigh, Peter stepped to the side and let Jim go ahead. Like Todd, Big Jim worked his way forward through the line. To Peter's pleasure Jim even moved in front of Todd to take the spot behind Wren.
￼Now Tiny Mike stood behind Peter. Peter tried to glare at Tiny Mike, making it clear that Mike was not moving ahead. Mike did not even try.
This process continued for the next hour. Every time a larger person found themselves waiting behind a smaller person, there was a polite tap on the shoulder and a switching of positions. Each time Peter moved back in the line he felt a little more demoralized. He was not a big person, and thus he found himself unable to swap with anyone. By the end of the hour the entire line was sorted by size, and Peter was near the back. Discouraged, Peter left the line and returned to the library.
￼As Peter sulked behind the library's counter, he remembered that now tickets were also available by pigeon message. He hurriedly filled out the form, requesting "Best Available". The pigeon flapped away, carrying Peter's only hope for reasonable seats. Ten minutes later, the pigeon returned with a confirmation of second-row, mid-field. Peter was thrilled. He must have gotten his tickets before even Big Jim.
That day Peter learned two important lessons. First, bubble sort is great for bullies. Second, standing in line was not worth it in the age of near-instantaneous pigeon-based ordering.