In this post, I will document a small reinforcement learning experiment where I trained an agent to play a Flappy Bird-like game. The main purpose is to record the experiments, failures, observations, and concepts so I can revisit and continue the project later.

Environment

• The game was implemented using pygame and wrapped as a Gymnasium environment.
• The bird has:
  • Fixed horizontal position.
  • Variable vertical position.
  • Vertical velocity.
  • Radius of 18px.
• Pipes have:
  • Horizontal position.
  • Gap center (gap_y).
  • Width of 70px.
  • Gap size of 180px.

Physics:

In this post, I will talk about public key cryptography, how encryption/decryption happens in asymmetric key cryptography, and how digital signatures and certificates are useful.

Public key cryptography

• Also, known as asymmetric key cryptography. Asymmetric because there are 2 keys - public and private.
• Public key is available to anyone in public. But the private key remains with the original owner.
• Can be used to encrypt/decrypt data or to verify the authenticity of the data(digital signatures).
• The thing to note is that public/private can be used interchangeably (they are similar in that sense) i.e. data encrypted by one can be decrypted by another. For the sake of convention, in this post, we will use the terms public key for encryption and private key for decryption.
• RSA is an example of one such cryptosystem.

Encryption and decryption

• In asymmetric key cryptography. The public key is available to the public.
• The act of encrypting the data involves using some cryptographic algorithm with inputs as the public key and data being encrypted.
• The end result is seemingly random-looking data. Obtaining original data from this random-looking data involves using the cryptographic algorithm with inputs as the private key and encrypted data.
• Since public keys are available to the public, the sender can encrypt the data which can only be decrypted by the receiver.

Digital signatures

• Digital signatures are generally used to verify the integrity of the data. Practically speaking it follows, that party A generates some data known as a digital signature for the actual data. And when sending the actual data this digital signature is also sent with it. Other parties now can actually verify that the received data is correct and is really sent by party A by using the digital signature.
• The way this works using public key cryptography is :
  1. The sender generates the digital signature(can be thought of as a process similar to encrypting) using its private key (using some crypto algo).
  2. The receiver now has this digital signature of the data, the data and, the public key of the sender. We have already discussed that the public and private keys are interchangeable in that data encrypted by one can be decrypted using the other.
  3. Due to this receiver can retrieve the data using the sender’s public key and the digital signature. If the sent data by the sender and retrieved data are the same, then the verification is successful, suggesting that the data was indeed sent by the sender.
• Practically, the same digital signature can be performed on the subset of the data (or even the hash of the data!) and we could still perform similar verification.

Digital certificate

• This is an application of digital signatures. Used to establish the identity of the owner(of the certificate) and also its public key. Digital certificates will be associated with a pair of public and private keys. The server/owner will have the private key and the public key will be distributed along with the digital certificate.
• A question arises, with just this information in the digital certificate, can some malicious party pose as another entity using a forged digital certificate? i.e. we have yet to establish/verify that the public key really belongs to the said owner.
• To solve this problem we have issuers of the digital certificate, and the issuer itself has its public/private key pair. And their job is to verify the ownership and sign the digital certificate using their private key. This issuer’s digital signature is also present in the digital certificate.
• To understand this end-to-end on how an end user can verify the digital cert, consider this flow :
  1. The user wants to verify the server A digital certificate. The certificate has server A public key, issuer A details, and issuer A digital signature.
  2. Assume that the user trusts issuer A and also has its public key. Then it can verify using the issuer’s digital signature that the server A digital certificate was indeed signed by the issuer thereby confirming if the digital certificate is valid.
  3. It can be clearly seen here that a chain of trust is established, that is to verify the digital certificate of server A we have to verify/trust the issuer’s digital signature.
• The issuer here acts as the Certificate Authority(CA). And the job of a CA is to verify the identities and issue digital certificates for the entities. In our case, Issuer A was the CA for server A digital certificate. What this really means is that if you trust a CA then you automatically trust certificates signed/issued by this CA!
• The process of signing a digital certificate by an issuer effectively means signing it using the issuer’s private key or using the issuer’s own digital certificate(both are the same technically, just different uses of language). FYI, the Digital certificate owner is also known as subject in technical terms.
• X.509 is one of the standards for public key certificates.

Digital certificate types

• Generally there are 3 types :

  1. Root certificate :
     • These certificates are at the top of the chain of trust and therefore are self-signed (i.e. signed using their own private key).
     • These are also trust anchors because the trust for these is to be assumed and we cannot verify or derive the trust for these.
  2. Intermediate certificate :
     • These are signed by the root certificate(same as root CA). e.g. issuer A in the above example.
     • To verify intermediate certificates, clients will use root CA cert public keys.
  3. Leaf certificate :
     • Signed by the intermediate certificate (same as intermediate CA).
     • These are terminal nodes i.e. these cannot be used to issue new digital certificates. (The entity owning this is not a CA!)
     • The role of intermediate CA is to delegate/proxy the role of signing from root CA.

• I am using CA and their digital certificates interchangeably here. Although the CA is the one actually owning its digital certificate (so technically not the same) the act of signing itself involves the CA digital certificate(or the private key).

You might ask what you mean by ‘What is Wi-Fi?’:confused: - I connect my device to the WiFi network and boom I am accessing the internet. Well, I held this abstraction for quite some time and the time had come to delve into a lower abstraction, because why not, there is no harm in knowing some background details. For the sake of not losing my mind, I wouldn’t dive into super lower-level details nor I have looked into them :smiley:. But this should at least give you an understanding of how ‘WiFi’ operates.

Table of contents

1. Streaming algorithm and sketching algorithms
2. Count Distinct problem
3. Hyperloglog(HLL)
4. HLL improvements
5. Demo

Streaming and sketching algorithms

• Algorithms for data streams that examine data a few times and have low memory requirements.
• Storing individual elements is not possible in data streams as in most cases the size is enormous.
• We try to get approximate or “good enough” estimates while storing the “sketch” of the data(i.e some representation of data) but not the data itself. The “sketch” size should be much less than the data size.
• In short, we are doing a tradeoff between accuracy and memory.

Count Distinct problem

• Finding the number of unique/distinct elements in a multiset(set with repeated elements).
• e.g., unique visitors to a website and unique IP addresses through a router.
• Simple solution to this could be to keep a map of every element and its count. The main drawback of this approach is the storage of the map, as in the worst case, it is O(n).
• A sketching algorithm could prove helpful for this case as, in most cases, we would not care about 100% accuracy.

Hyperloglog(HLL)

Sketching algorithm designed to solve the count-distinct problem within acceptable error rate. Described in the paper “HyperLogLog: the analysis of near-optimal cardinality estimation algorithm”, published by Flajolet, Fusy, Gandouet and Meunier in 2007. Improvements were proposed in “HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm”, published by Stefan Heulem, Marc Nunkesse and Alexander Hall.

Table of contents

1. Spark aggregation Overview
2. TypedImperativeAggregate[T] abstract class
3. Example

Spark aggregation Overview

• User Defined Aggregate Functions can be used. But are restrictive and require workarounds even for basic requirements.
• Aggregates are unevaluable expressions and cannot have eval and doGenCode method.
• Basic requirement would be to use user defined java objects as internal spark aggregation buffer type.
• And, passing extra arguments to aggregates e.g aggregate(col, 0.24)
• Spark provides TypedImperativeAggregate[T] contract for such requirement (imperative as in expressed in terms of imperative initialize, update, and merge methods).

TypedImperativeAggregate[T] abstract class

case TestAggregation(child: Expression) 
  extends TypedImperativeAggregate[T]  {

  // Check input types
  override def checkInputDataTypes(): TypeCheckResult

  // Initialize T
  override def createAggregationBuffer(): T

  // Update T with row
  override def update(buffer: T, inputRow: InternalRow): T

  // Merge Intermediate buffers onto first buffer
  override def merge(buffer: T, other: T): T
 
  // Final value
  override def eval(buffer: T): Any 

  override def withNewMutableAggBufferOffset(newOffset: Int): TestAggregation 

  override def withNewInputAggBufferOffset(newOffset: Int): TestAggregation 

  override def children: Seq[Expression]

  override def nullable: Boolean

  // Datatype of output
  override def dataType: DataType

  override def prettyName: String

  override def serialize(obj: T): Array[Byte] 

  override def deserialize(bytes: Array[Byte]): T 
}

Example

• case class Average holds count and sum of elements and also acts as internal aggregate buffer.
• Aggregate takes in a numeric column and an extra argument n and return avg(column) * n.
• In SparkSQL this will look like :

SELECT multiply_average(salary, 2) as average_salary FROM employees

• Spark alchemy’s NativeFunctionRegistration is used to register functions to spark.
• Aggregate Code :

import com.swoop.alchemy.spark.expressions.NativeFunctionRegistration
import org.apache.spark.sql.SparkSession
import org.apache.spark.{SparkConf, SparkContext}
import org.apache.spark.sql.catalyst.InternalRow
import org.apache.spark.sql.catalyst.analysis.TypeCheckResult
import org.apache.spark.sql.catalyst.expressions._
import org.apache.spark.sql.catalyst.expressions.aggregate.TypedImperativeAggregate
import org.apache.spark.sql.types._

import java.io.{ByteArrayInputStream, ByteArrayOutputStream, ObjectInputStream, ObjectOutputStream}


case class Average(var sum: Long, var count: Long)

case class AvgTest(
                  child: Expression,
                  nExpression : Expression,
                  override val mutableAggBufferOffset: Int = 0,
                  override val inputAggBufferOffset: Int = 0)
  extends TypedImperativeAggregate[Average]  {

//  private lazy val n: Long = nExpression.eval().asInstanceOf[Long]
  def this(child: Expression) = this(child, Literal(1), 0, 0)
  def this(child: Expression, nExpression: Expression) = this(child, nExpression, 0, 0)

  override def checkInputDataTypes(): TypeCheckResult = {
    child.dataType match {
      case LongType => TypeCheckResult.TypeCheckSuccess
      case _ => TypeCheckResult.TypeCheckFailure(s"$prettyName only supports long input")
    }
  }

  override def createAggregationBuffer(): Average = {
    new Average(0, 0)
  }

  override def update(buffer: Average, inputRow: InternalRow): Average = {
    val value = child.eval(inputRow)
    buffer.sum += value.asInstanceOf[Long]
    buffer.count += 1
    buffer
  }

  override def merge(buffer: Average, other: Average): Average = {
    buffer.sum += other.sum
    buffer.count += other.count
    buffer
  }

  override def eval(buffer: Average): Any = {
    val n: Int = nExpression.eval().asInstanceOf[Int]
    ((buffer.sum*n)/(buffer.count))
  }

  override def withNewMutableAggBufferOffset(newOffset: Int): AvgTest =
    copy(mutableAggBufferOffset = newOffset)

  override def withNewInputAggBufferOffset(newOffset: Int): AvgTest =
    copy(inputAggBufferOffset = newOffset)

  override def children: Seq[Expression] = Seq(child, nExpression)

  override def nullable: Boolean = true

  // The result type is the same as the input type.
  override def dataType: DataType = child.dataType

  override def prettyName: String = "avg_test"

  override def serialize(obj: Average): Array[Byte] = {
    val stream: ByteArrayOutputStream = new ByteArrayOutputStream()
    val oos = new ObjectOutputStream(stream)
    oos.writeObject(obj)
    oos.close()
    stream.toByteArray
  }

  override def deserialize(bytes: Array[Byte]): Average = {
    val ois = new ObjectInputStream(new ByteArrayInputStream(bytes))
    val value = ois.readObject
    ois.close()
    value.asInstanceOf[Average]
  }
}

• Driver code :

object TestAgg {
  object BegRegister extends NativeFunctionRegistration {
    val expressions: Map[String, (ExpressionInfo, FunctionBuilder)] = Map(
      expression[AvgTest]("multiply_average")
    )
  }
  def main(args: Array[String]): Unit = {
    val conf = new SparkConf().setMaster("local[*]").setAppName("FirstDemo")
    val sc = new SparkContext(conf)
    val spark = SparkSession.builder().appName("Demo").config(conf).getOrCreate()


    BegRegister.registerFunctions(spark)
      val df = spark.read.json("src/test/resources/employees.json")
      df.createOrReplaceTempView("employees")
      df.show()
      /*
      +-------+------+
      |   name|salary|
      +-------+------+
      |Michael|  3000|
      |   Andy|  4500|
      | Justin|  3500|
      |  Berta|  4000|
      +-------+------+
       */
      val result = spark.sql("SELECT multiply_average(salary) as average_salary FROM employees")
      result.show()
    /*
      +--------------+
      |average_salary|
      +--------------+
      |          3750|
      +--------------+
     */
      val result1 = spark.sql("SELECT multiply_average(salary, 2) as average_salary FROM employees")
      result1.show()
      /*
      +--------------+
      |average_salary|
      +--------------+
      |          7500|
      +--------------+
     */
      val result2 = spark.sql("SELECT multiply_average(salary, 3) as average_salary FROM employees")
      result2.show()
      /*
      +--------------+
      |average_salary|
      +--------------+
      |         11250|
      +--------------+
      */
  }
}

• Here, nExpression represents our n argument. Other lines are self-explanatory.

Table of contents

1. Overview
2. Trees
3. Rules
4. Expression
5. CodegenFallback
6. Example of spark native function using Unary expression

Spark Catalyst Overview

• Core of Spark dataframe API and SQL queries.
• Supports cost based and rule based optimization.
• Built to be extensible :
  • Adding new optimization techniques and features
  • Extending the optimizier for custom use cases
• At core it uses trees
• On top of it various libraries are written for query processing, optimization and execution.

Trees

• Trees in Catalyst consists of node objects.
• Node - type and zero/more children
• E.g If Literal(v: Int), Attribute(name: String), Add(l: TreeNode, r: TreeNode) are simple node types then x+(2+5) can be represented as Add(Attribute(x), Add(Literal(2), Literal(5))).

Table of contents

1. Intra pod communication
2. Inter pod communication
3. CNI plugin
4. Pod to service communication

Intra pod communication

When pod is created,

1. It is assigned to a node.
2. A network namespace is created for it(i.e all of that pod’s containers belong to that namespace),
3. IP is assigned to it.

For every pod in the cluster there is pause container running in the background. The pause container creates and holds network namespace for that pod.

Introduction

During my GSoC, I worked on App Store improvements project for ns-3 organization. GSoC was my first programming experience outside personal projects and I thoroughly enjoyed the experience. I had an awesome opportunity to work for the ns-3 organization. My mentors abhijithanilkumar, mishalshah and adeepkit01 were extremely responsive, helpful, and understanding. I would also like to thank tomh sir - the ns-3 Organization Admin for his help and suggestions.

Project outline

Project Goals : To develop a Jenkins server and add necessary updates to ns-3 AppStore to check on-demand if available, uploaded or updated apps/modules/forks to AppStore build and pass tests successfully for the given ns-3 versions and display that information on AppStore. And to improve the AppStore by addressing the existing issues.