Delta propagation’s view-update problem

In reactive programming, the “push” implementation can take several forms of one node (computation) passing along a directed edge (a path from one node to another) some change information to another node. Two forms of change information that can be passed is:

Complete node state
Delta propagation

A node could pass the complete node state to the next node. The node receiving the complete state of the previous node could then use this information to compute its own new state. This is a straight-forward implementation, but it can be inefficient if the next node doesn’t need the complete state of a previous node to compute its own state.

To optimize, one could use delta propagation which only passes along the changed data of a node. This would be enough for the next node to compute its new state depending on the exact implementation.

The view-update problem occurs when a program needs to maintain the state of nodes while updating their states upon an update in data. Updates in data should only affect nodes where there is a path from the node which has a change in its data and connected nodes. In a directed acyclic graph with nodes connected with directed edges, the view of nodes passed the node with the change should be updated.

Here is an example:
node A -> node B
node B -> node C
node B -> node D

If there was an update in node B, then node views for C and D should be updated ¹

The view-update problem is often described within the context of databases since relational database management system maintain different levels of views of its data. There is the external level where an end-user of a database would interact with to get data. There is the lowest level where the actual data is stored on physical hardware (disks, tape, SSDs). In between these two levels is the conceptual level which is relevant to the database software coordinating the two levels.

Each of these levels maintain their own view of the data. The external level is more interested in the data and less interested in how the data is stored on the hardware. This results in the database view-update problem. The hardware could be optimized by creating better indexes of the data or by replacing it with a faster technology. The external level should not need to know of this hardware update to generate its own view of the data.

1: For the sake of example, node A does not need to be the cause of the change in node B.

What is a runtime?

In programming, a problem have different phases in its overall lifecycle. Depending on the specific programming language, the program may require compiling. The phase when a program is compiling is called the compile time. Similarly, when a programming is executing or running this phase is called the execution time or runtime.

During a program’s runtime there may be errors. These are called runtime errors. Examples of runtime errors are dividing my zero, attempting to read a file on a file system that does not exist, and making a request to a website which does not exist.

What is compiling?

Compiling a computer program uses another computer program, a compiler, to transform/translate a program’s source code into another compiled form. The source code is typically written in a high-level programming language and the output code in another programming language.

The level of abstraction of the output code determines whether the process is called compiling or transpiling. When a program source is written in a high-level programming language and is transformed into a low-level programming language it is called compiling. When a program source is written in a high-level programming language and is transformed into another similarly abstracted level of programming language it is called transpiling.

Compiling: the Go programming language
Transpiling: the TypeScript programming language

High-level programming language

A high-level programming language is a programming language which abstracts away some of the details needed to program a computer. A computer requires such components as a processor, memory, and storage. These low-level components can be programmed directly, but most often they are not important when one is interested in programming a high-level program such as a web application for instance. To minimize the details a programmer must consider when writing a program, a programmer can select a high-level programming language to take care of the low-level details automatically.

There may be ways to access the lower-levels while programming in a high-level programming language, but this comes later on in a program’s life. Typically when programming with a high-level programming language at least in the beginning, one is interested in accomplishing some goal with little interest in the underlying details of how a computer is ran. There may be a time when these details become important such as when one wants program to go faster. This may mean increasing the speed at which a unit of work can be performed or the number of units of work can be performed in a duration of time.

Examples of high-level programming languages are: Javascript, Python, Ruby, PHP

Graph Sinks

A graph comprises of nodes and edges. The nodes can connect to another node when an edge connects the two. The edge can be directed or directional in that it describes a starting node and an ending node. The graph with nodes and directed edges is called a directed graph.

When a directed graph has a node with no outgoing edges, perhaps it has only other nodes connected to it via directed edges, the node can be said to be a graph sink.

An example is the following graph:
A -> B
A -> C
B -> C

The node C has only ingoing edges with no outgoing edges.

Transitive closure

Apart of learning more about Reactive programming, I came across the term Transitive Closure which has roots in Mathematics. Below I set out to decompose the concept into smaller concepts to clarify understanding.

A “set” is a strict list of elements. For example, set X can be a list of numbers {1,2,3}. An element, or number in this case, is said to be a member of the set X if it is found in set X. The number 1 has membership in set X.

Let’s also define another set Y to be {4,5,6}.

2 elements can be paired together to represent a list. The numbers 1 and 2 is a list of 2 elements or a pair. In addition to defining what elements are included and how many elements are in the list, the order can be specified. We can order 1 to be first and 2 second, or we can order 2 to be first and 1 second. In Mathematics, this list usually is written via a tuple, more specifically a 2-tuple to specify that there are only 2 elements, by arranging the elements in a specific order within "( )" Parenthesis. The tuple is a limited or finite ordered list able to contain an arbitrary number of elements. The lists described above can be written as two 2-tuples or ordered pairs; (1,2) and (2,1).

Multiple ordered pairs can be grouped in a relation which represents elements within an ordered pair are related. In this example, the specific relation is a binary or 2-place relation. The word “binary” indicates or involves the quantity of two. This is typically found in Computer Science to mean the Binary numbers 0 and 1; On or Off.

Here is a binary relation for the sets X and Y denoted by the letter R.
R = {(1,4), (1,5), (5,1)}
“1 is related to 4“. “1 is related to 5“. “5 is related to 1“.

Notice there are only 3 ordered pairs in this binary relation. This is a subset of the Cartesian product of the sets X and Y. The Cartesian product is a set of all combinations of all the elements in the sets. The full Cartesian products of sets X and Y is

X * Y = {1,2,3} * {4,5,6} = {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)} Y * X = {4,5,6} * {1,2,3} = {(4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (6,1), (6,2), (6,3)}

With the ordered pairs and binary relation defined, the word transitive can be explained. The transitive relation means by knowing the two relationships of some elements, a third relationship can be established. If we said a is related to b and b is related to c, then the relationship a is related to c can be established.

A more concrete example can be the following. John is friends with Jane. Jane is friends with Fred. There is a transitive relation between John and Friend since they both share the friend Jane in common.

The second word in Transitive Closure is Closure. In Mathematics, a set can be said to be closed or exhibit the Closure property when some operation or procedure done on a set only strictly outputs members already in the set. In the context of sets and binary relations, the relevant operation or procedure can be finding the relations of elements in a set.

Let’s now pull all of this together along with continuing with the previously defined set X, set Y, and the binary relation R.

set X = {1,2,3} set Y = {4,5,6} R = {(1,4), (1,5), (5,1)}

We see “1 is related to 4“. “1 is related to 5“. “5 is related to 1“. Looking at the two relationships “5 is related to 1” and “1 is related to 4“, we can establish a new transitive relation “5 is related to 4“. No other transitive relations can be established. This new pair (5,4) can be added to the ordered pairs in R. Since R is a strict set, we’d have to define a new set which includes the new ordered pair. The new set can be written as

R' = {(1,4), (1,5), (5,1), (5,4)}.

Since no other ordered pairs are necessary to represent all the relations of the numbers in the original R set, we have found the transitive closure of the binary relation R.

The formal definition of a transitive closure is:

In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive. Wikipedia

This was an explanation of the concept Transitive Closure using underlying concepts.

For more resources, I found this video helpful in understanding Transitive Closures since it explains the concept further with a graph: Transitive Closure Video.

Let me know your thoughts or whether there are any inaccuracies in the explanation.

Amazon Dash Button and Raspberry Pi Scripting

At home, I have several Amazon Dash Buttons throughout the house with a Raspberry Pi listening for clicks. I mainly use these buttons to track whether I have completed a specific task near the Amazon dash button. For example, I have have a button in my bathroom I click when I have flossed my teeth at night. Clicking this button would then mark the corresponding daily task completed.

Below is the script I use to mark a task done (some details omitted).

from scapy.all import *
import requests
# it takes a minute for the scapy sniffing to initialize, so I print this to know when it's actually ready to go
 print('Init done.')

USER_ID = ""
API_TOKEN = ""

mac_address_to_task_data = {
 "40:b1:cd:24:e2:1d": ("task_id", "task_name"),
 "18:74:fd:eb:82:17": ("task_id", "task_name"),
 "38:f7:3d:ca:32:dd": ("task_id", "task_name")
}

def execute_task(task):
 url = "https://task-management-app.com/tasks/%s/%s" % (task[0], "up")
 headers = {
   "x-api-user": USER_ID,
   "x-api-key": API_TOKEN,
 }
 requests.post(url, headers=headers)
 print "Executed '%s'" % task[1]

def detect_button(pkt):
 if pkt.haslayer(DHCP):
   if pkt[Ether].src in mac_address_to_task:
     task_data = mac_address_to_task.get(pkt[Ether].src)
     execute_task(task)
   else:
     print "Unknown: " + pkt[Ether].src

sniff(prn=detect_button, filter="(udp and (port 67 or 68))", store=0)

For more info, then check out this blog post on hacking the Amazon Dash Button which helped in getting started with this.